Dénombrabilité de l’ensemble des permutations de $\mathbb{N}$

Cherchons intuitivement quelle pourrait être la solution:
Pour construire une permutation $\sigma$ de $\mathbb{N}$ :

• Pour $0$, on a une infinité de choix
• Pour $1$, on a encore une infinité de choix (toutes les valeurs sauf $\sigma(0)$).
• Pour $2$, encore une infinité de choix, et ainsi de suite.
  Chaque entier $n$ offre une infinité d’options indépendantes (ou presque). Le nombre total de "trajectoires" possibles pour la suite $(\sigma(0), \sigma(1), \sigma(2), \dots)$ grandit à la manière d’un arbre dont chaque nœud a une infinité de branches. On chercherait donc plutôt à montrer que cet ensemble n’est pas dénombrable.

Pour cela, procédons par l’absurde en supposant l’ensemble des permutations $\mathfrak{S}$ dénombrable: si on réussit à construire une surjection de $\mathfrak{S}$ dans un ensemble non dénombrable, alors il y aura une contradiction. L’avantage de cette technique est que nous n’avons pas à construire une bijection.

Une idée à avoir pour construire cette surjection serait de caractériser les permutations: on pourrait par exemple considérer les points fixes ou bien les supports d’une permutation.

On rappelle qu’un support est "l’inverse" d’un point fixe, c’est à dire si $\sigma \in \mathfrak{S}(\mathbb{N})$, alors l’ensemble des supports de $\sigma$ est $\{k\in\mathbb{N}, \sigma(k)\neq k\}$.

On construit donc, en notant $S=\{\{k\}, k \in \mathbb{N}\}$ l’ensemble des singletons de $\mathbb{N}$:
$$\Phi: \begin{cases} \mathfrak{S} \longrightarrow \mathcal{P}(\mathbb{N})\setminus{S} \\ \sigma \longmapsto \{k\in\mathbb{N}, \sigma(k)\neq k\}\end{cases}$$Vérifions la surjectivité de $\Phi$:
Soit $A \in \mathcal{P}(\mathbb{N}) \setminus S$:

• Si $A = \emptyset$, $\Phi(\text{id}) = \emptyset = A$.
• Si $A$ contient au moins 2 éléments,
  Si $A$ fini, $A=\{a_{1},...,a_{p}\}$, on définit le cycle $\sigma: n \mapsto \begin{cases} a_{n+1} \text{ si } \exists k\in\{1,...,p-1\}, n=a_{k}\\ a_{1} \text{ si } n=a_{p} \\ n \text{ sinon}\end{cases}$ , tel que $\Phi(\sigma)=A$
  Si $A$ infini, il est dénombrable comme partie de $\mathbb{N}$, il existe donc une bijection $b: \mathbb{Z} \to A$, et on note $a_{k}=b(k)$ pour tout $k$ entier, alors $A=\{a_{k},k\in\mathbb{Z}\}$.
  On définit la permutation $\sigma: n \mapsto \begin{cases} a_{k+1} \text{ si } \exists k\in\mathbb{Z}, n=a_{k}\\ n \text{ sinon}\end{cases}$, tel que $\Phi(\sigma)=A$

On retire les singletons car si $A \in S$ ($A$ est un singleton), aucune permutation ne peut avoir $A$ pour support car un unique élément ne peut pas être dérangé seul.

Il ne manque plus qu’à savoir si $\mathcal{P}(\mathbb{N})\setminus{S}$ est dénombrable ou non. Intuitivement, $S$ est dénombrable et $\mathcal{P}(\mathbb{N})$ ne l’est pas, il y a donc peu de chances que retirer un ensemble dénombrable à un ensemble non dénombrable le rende dénombrable.

Montrons alors que $\mathcal{P}(\mathbb{N})\setminus{S}$ n’est pas dénombrable par l’absurde:
Supposons $\mathcal{P}(\mathbb{N})\setminus{S}$ dénombrable, alors $(\mathcal{P}(\mathbb{N})\setminus{S}) \cup S = \mathcal{P}(\mathbb{N})$ est dénombrable (car $S$ est dénombrable), ce qui est contradictoire.
Donc $\mathcal{P}(\mathbb{N})\setminus{S}$ n’est pas dénombrable.

On pourrait noter que ce résultat est en fait généralisable, comme on l’avait intuité:

$$\text{Si E non dénombrable et } F \text{ dénombrable, alors } E \setminus{F} \text{ non dénombrable}$$

Pour conclure: Si $\mathfrak{S}$ était dénombrable, alors son image par $\Phi$ qui est $\mathcal{P}(\mathbb{N})\setminus{S}$ serait dénombrable, ce qui est contradictoire.
Donc $\mathfrak{S}$ n’est pas dénombrable.

:::On suppose connue la relation d’ordre sur les cardinaux (et Cantor Bernstein).

Soit $f$ l’application de $P(\N)$ dans $S_{\N}$ qui à une partie $A$ de $\N$ associe le produit des transpositions à supports disjoints $(2n,2n+1), n\in A$. On vérifie que l’application $f$ est injective. Donc le cardinal de $S_{\N}$ est supérieur ou égal au cardinal de $P(\N)$ (définition de l’ordre sur les cardinaux). Le cardinal de $P(\N)$ est égal au cardinal de $\R$. Le cardinal de $\R$ est strictement supérieur à celui de $\N$ (théorème de Cantor, ie $\R$ n’est pas dénombrable). Donc $S_{{\N}}$ n’est pas dénombrable (en fait on a montré un résultat plus fort : $S_{\N}$ a au moins la puissance du continu).

:::Sans connaissance sur l’ordre sur les cardinaux.
Lemme. Il n’existe pas d’injection entre $\R$ (ou toute partie non au plus dénombrable de $\R$, ou tout ensemble en bijection avec $\R$) et $\N$.
Supposons le contraire et soit $j$ une telle injection. Alors $\R$ est en bijection avec $j(\R)$, et toute partie de $\N$ est au plus dénombrable, donc $j(\R)$ est au plus dénombrable, donc $\R$ est au plus dénombrable, ce qui contredit le théorème de Cantor.

On rappelle que $\R$ est en bijection avec $P(\N)$. Supposons que $S_{\N}$ soit dénombrable. Alors $f(P(\N))$, qui est une partie non finie de $S_{\N}$, est dénombrable (on utilise ici que toute partie de cardinal infini de $\N$ (ou toit ensemble en bijection avec $\N$) est dénombrable). D’après le lemme, on a alors une contradiction. Conclusion : $S_{\N}$ n’est pas dénombrable.

:::

Notons $2^\N$ l’ensemble des listes infinies à valeurs dans $\{0,1\}$ ; le sous-ensemble $C$ des listes constantes à partir d’un certain rang est dénombrable, donc $\bar C=2^{\N}-C$ n’est pas dénombrable.
A toute $f\in\mathcal S_{\N}$ on associe la liste $u=\big(f(n) \mod 2\big)_{n\in \N}=f\mod 2$ ; $f\mapsto u$ surjecte ainsi $\mathcal S_{\N}$ sur $\bar C$ qui n’est pas dénombrable ; donc $\mathcal S_{\N}$ n’est pas dénombrable.

Une preuve possible que $f\mapsto u$ surjecte $\mathcal S_{\N}$ sur $\bar C$

Pour antécédent de toute suite $u\in\bar C$ on peut par exemple proposer $f:\N\rightarrow\N$ définie par
$$f(n)=(2s_{n}-1)u_{n} + 2(n-s_{n})(1-u_{n}) {\rm\ avec}\ s_{n}=\sum_{i=0}^{n}u_{i}$$On a
a) $f\mod 2=u$
b) $f$ est bijective car elle entrelarde les entiers impairs qu’elle positionne là où il y a des $1$ dans $u$ et les entiers pairs là où il y a des 0 dans $u$ : Vérifiez si vous n’y croyez pas que la liste
$u=$$(0, 1,1,0,0,0,1,0,1,0,0,...)$ produit $f=(0,1,3,2,4,6,5,8,7,10,12...)$

ou rédigez proprement une récurrence : $f(0)=u_{0},f(1)=u_{1}$ et entre deux "1" (resp. "0") successifs séparés par un nombre quelconque de "0" (resp. "1") dans la suite $u$, la valeur de $f$ augmente de 2.