Dénombrabilité de l’ensemble des permutation 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 dérangements d’une permutation.

On rappelle qu’un dérangement est "l’inverse" d’un point fixe, c’est à dire si $\sigma \in \mathfrak{S}(\mathbb{N})$, alors l’ensemble des dérangements 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.