$\mathfrak{S}(\mathbb{N})$ dénombrable ?

On va s’inspirer de l’argument diagonal de Cantor pour montrer qu’il n’existe pas de surjection $\mathbb{N}\to \mathfrak{S}(\mathbb{N}).$ Soit $\varphi\colon\mathbb{N}\to \mathfrak{S}(\mathbb{N})$ et montrons que $\varphi$ n’est pas surjective en construisant un élément $\sigma$ de $\mathfrak{S}(\mathbb{N})$ qui n’est pas dans l’image de $\varphi.$ Commençons naïvement : pour nous assurer que $\sigma\neq \varphi(0)$ on peut tout simplement poser $\sigma(0)\in\mathbb{N}\setminus\left\{\varphi(0)(0)\right\}$ puis, plus généralement $\sigma(n)\in\mathbb{N}\setminus\left\{\varphi(n)(n)\right\}$. Ce faisant on est bien assuré que $\sigma\notin\operatorname{im}\varphi$ mais rien ne garantit que $\sigma$ soit injective ou surjective. On va alors forcer l’injectivité en posant $\sigma(n)\notin\mathbb{N}\setminus\left\{\varphi(n)(n),\sigma(0),\dots,\sigma(n-1)\right\}$. Une fonction $\sigma$ construite ainsi est injective. En effet, si $i\neq j,$ disons $i<j$ alors $\sigma(j)\in\mathbb{N}\setminus\left\{\sigma(i)\right\}$ donc $\sigma(j)\neq \sigma(i).$ Cependant rien ne nous assure qu’elle est surjective, par exemple ajouter la condition $\forall n\in\mathbb{N}, \sigma(n)\neq 0$ est parfaitement compatible avec nos critères et fournit un élément $\sigma$ non surjectif. On va alors poser
$$\forall n\in\mathbb{N},\sigma(n)=\min\left(\mathbb{N}\setminus\left\{\varphi(n)(n),\sigma(0),\dots,\sigma(n-1)\right\}\right).$$Une telle application $\sigma$ est bien définie car le minimum porte systématiquement sur une partie non vide de $\mathbb{N}.$ On sait déjà qu’une telle application $\sigma$ n’est pas dans l’image de $\varphi$ et qu’elle est injective. Pour conclure on va distinguer deux cas.

1. Si $(\varphi(n)(n))_{n\in\mathbb{N}}$ n’est pas constante à partir d’un certain rang. Dans ce cas on montre par récurrence (forte) la proposition $H(m)\colon$"$m\in\operatorname{im}\sigma$".
   Initialisation. Soit $n\in\mathbb{N}$ tel que $\varphi(n)(n)\neq 0$ alors $\sigma(n)=0$ ou alors il existe déjà $k\leq n, \sigma(k)=0$. Dans tous les cas $0\in\operatorname{im} \sigma.$
   Hypothèse de récurrence. Soit $m\in\mathbb{N}$ tel que $\forall m'\leq m,H(m')$ vraie.
   Hérédité. Soit $n\in\mathbb{N}$ tel que $\left\{0,\dots,m\right\}\subseteq \left\{\sigma(0),\dots,\sigma(n-1)\right\}$ et $\varphi(n)(n)\neq m+1$ alors $\sigma(n)=m+1$ ou bien $\exists k\leq n, \sigma(k)=m+1.$
   Dans ce cas on a construit $\sigma\in\mathfrak{S}(\mathbb{N})\setminus\operatorname{im}\varphi$ donc $\varphi$ n’est pas surjective.
2. Si $(\varphi(n)(n))_{n\in\mathbb{N}}$ constante égale à $m$ à partir d’un certain rang. On pose $S_m=\left\{\sigma\in\mathfrak{S}(\mathbb{N})\mid \sigma_{|\left\{0,\dots,m\right\}}=\operatorname{id}_{\left\{0,\dots,m\right\}}\right\}$ qui est de cardinal infini par exemple car en bijection avec $\mathfrak{S}(\set{n\in\mathbb{N}\mid n\geq m})$
   est injective. Mais par hypothèse $\left\{\sigma\in\operatorname{im}\varphi\mid \sigma(m)=m\right\}$ est fini donc $\varphi$ ne peut être surjective.