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

:::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.

:::