dénombrabilité de S_N

ahmad3 · February 2007

Bonjour

L'ensemble des permutations de $\N$ est-il dénombrable ?

Yop0 · February 2007

Soit $A$ un sous-ensemble de $\N$. Je lui associe une permutation $\sigma_A$ de $\N$ de la manière suivante. Pour tout entier naturel $n$ :
1) si $n$ appartient à $A$ je pose $\sigma_A(2n)=2n+1$ et $\sigma_A(2n+1)=2n$ ;
2) sinon, je pose $\sigma_A(2n)=2n$ et $\sigma_A(2n+1)=2n+1$.

Cela me donne une application de l'ensemble des sous-ensembles de $\N$ dans l'ensemble des permutations de $\N$ ($A \mapsto \sigma_A$).

On constate que cette application est injective. Cela permet de conclure (l'ensemble des sous-ensembles de $\N$ étant non dénombrable).

Le tout sauf bévue et sans relecture, comme d'hab...

corentin · February 2007

Malheureusement, l'ensemble des parties de $\N$ n'est pas dénombrable, puisque équipotent à $\{0,1\}^{\N}$ (mettre en bijection les parties avec leur indicatrice, c'est à dire les fonctions de $\N\rightarrow \{0,1\}$, on peut aussi dire que l'ensemble des parties d'un ensemble n'est jamais équipotent à cet ensemble, d'après un th de Cantor je crois).
D'ailleurs, les permutations de $\N$ ne sont pas dénombrables: à toute partie de $\N$ contenant plus de deux éléments, on associe une permutation cyclique sur cette partie.
Ca nous donne une injection d'un ensemble indénombrable (car les parties de $\N$ contenant un seul élément forment un ensemble évidemment dénombrable) dans les permutations.
Enfin je suis pas certain de ma preuve, mais je suis à peu près sur que les permutations sont indénombrables.

gb · February 2007

corentin> Tu dis :
"à toute partie de $\N$ contenant plus de deux éléments, on associe une permutation cyclique sur cette partie"
Si cette partie est l'ensemble des entiers pairs, quelle est cette {\it permutation cyclique} ?
Il me semble que tu dois considérer des parties finies, et tu es immédiatement soumis à la question (je suis pire que PJH) : l'ensemble des parties finies de $\N$ est-il dénombrable ?

Yop0 · February 2007

Corentin : je ne comprends pas ton problème (j'ai une injection d'un ensemble non dénombrable dans l'ensemble des permutations, cela montre la non dénombrabilité de l'ensemble des permutations).

Par ailleurs, mêmes remarques que gb, et vu que l'ensemble des sous-ensembles finis de $\N$ est dénombrable...

corentin · February 2007

Oui, j'ai dit n'importe quoi. Je dois avoir un gros problème, ça fait plusieurs fois que je lis exactement l'inverse de ce qui est marqué dans un message.
Mon raisonnement est d'autant plus minable que l'ensemble des parties finies de $\N$ est dénombrable, vu qu'il s'écrit comme l'union pour $k\in\N$ des ensembles à k élément, qui sont tous dénombrables...

GG · February 2007

bonjour,
on a aussi "l'argument diagonal" :
si l'on a une suite (f_n) de permutations de N, on construit une permutation p = (a₁,b₁)(a₂,b₂). ... avec b_i <> f_i(a_i), les a_i,b_i tous distincts, et p n'est pas l'un des f_i

P.S. à noter que l'argument de Yop est plus fort, car il montre directement que card(S(N)) = card(P(N)) = card(N^N) = 2^aleph0

pB0 · February 2007

En résumé, et en généralisant : pour tout cardinal infini $n$, on a $2^n=n!$

ahmad3 · February 2007

Merci pour vos réponses

mais que signifie n! lorsque n est un cardinal infini ?

pB0 · February 2007

C'était une devinette sous-entendue. Ma réponse (a priori, il n'y a pas unicité de la réponse) est : pour tout cardinal n, on note n! le cardinal de l'ensemble des permutations d'un ensemble de cardinal n.

dénombrabilité de S_N

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 17