Ivan Shishkin, Rye (1878)

Discussions

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

0 messages

Back to problem

Solution

Solution by FiniteField · FR

On va s’inspirer de l’argument diagonal de Cantor pour montrer qu’il n’existe pas de surjection N→S(N).\mathbb{N}\to \mathfrak{S}(\mathbb{N}). Soit φ ⁣:N→S(N)\varphi\colon\mathbb{N}\to \mathfrak{S}(\mathbb{N}) et montrons que φ\varphi n’est pas surjective en construisant un élément σ\sigma de S(N)\mathfrak{S}(\mathbb{N}) qui n’est pas dans l’image de φ.\varphi. Commençons naïvement : pour nous assurer que σ≠φ(0)\sigma\neq \varphi(0) on peut tout simplement poser σ(0)∈N∖{φ(0)(0)}\sigma(0)\in\mathbb{N}\setminus\left\{\varphi(0)(0)\right\} puis, plus généralement σ(n)∈N∖{φ(n)(n)}\sigma(n)\in\mathbb{N}\setminus\left\{\varphi(n)(n)\right\}. Ce faisant on est bien assuré que σ∉im⁡φ\sigma\notin\operatorname{im}\varphi mais rien ne garantit que σ\sigma soit injective ou surjective. On va alors forcer l’injectivité en posant σ(n)∉N∖{φ(n)(n),σ(0),…,σ(n−1)}\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≠j,i\neq j, disons i<ji<j alors σ(j)∈N∖{σ(i)}\sigma(j)\in\mathbb{N}\setminus\left\{\sigma(i)\right\} donc σ(j)≠σ(i).\sigma(j)\neq \sigma(i). Cependant rien ne nous assure qu’elle est surjective, par exemple ajouter la condition ∀n∈N,σ(n)≠0\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
∀n∈N,σ(n)=min⁡(N∖{φ(n)(n),σ(0),…,σ(n−1)}).\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 N.\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 (φ(n)(n))n∈N(\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) ⁣:H(m)\colon"m∈im⁡σm\in\operatorname{im}\sigma".
    Initialisation. Soit n∈Nn\in\mathbb{N} tel que φ(n)(n)≠0\varphi(n)(n)\neq 0 alors σ(n)=0\sigma(n)=0 ou alors il existe déjà k≤n,σ(k)=0k\leq n, \sigma(k)=0. Dans tous les cas 0∈im⁡σ.0\in\operatorname{im} \sigma.
    Hypothèse de récurrence. Soit m∈Nm\in\mathbb{N} tel que ∀m′≤m,H(m′)\forall m'\leq m,H(m') vraie.
    Hérédité. Soit n∈Nn\in\mathbb{N} tel que {0,…,m}⊆{σ(0),…,σ(n−1)}\left\{0,\dots,m\right\}\subseteq \left\{\sigma(0),\dots,\sigma(n-1)\right\} et φ(n)(n)≠m+1\varphi(n)(n)\neq m+1 alors σ(n)=m+1\sigma(n)=m+1 ou bien ∃k≤n,σ(k)=m+1.\exists k\leq n, \sigma(k)=m+1.
    Dans ce cas on a construit σ∈S(N)∖im⁡φ\sigma\in\mathfrak{S}(\mathbb{N})\setminus\operatorname{im}\varphi donc φ\varphi n’est pas surjective.
  2. Si (φ(n)(n))n∈N(\varphi(n)(n))_{n\in\mathbb{N}} constante égale à mm à partir d’un certain rang. On pose Sm={σ∈S(N)∣σ∣{0,…,m}=id⁡{0,…,m}}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 S({ n∈N∣n≥m })\mathfrak{S}(\set{n\in\mathbb{N}\mid n\geq m})
    est injective. Mais par hypothèse {σ∈im⁡φ∣σ(m)=m}\left\{\sigma\in\operatorname{im}\varphi\mid \sigma(m)=m\right\} est fini donc φ\varphi ne peut être surjective.

No messages yet.