Exercice 26

1. Il suffit de montrer que $\beta : (a,b) \mapsto 2^{a}(2b + 1)$ est une bijection de $\mathbb{N}^{2}$ sur $\mathbb{N}^{*}$, puis de retrancher $1$.

• Surjectivité. Soit $m \in \mathbb{N}^{*}$. L'ensemble des entiers $a$ tels que $2^{a}$ divise $m$ contient $0$ et est majoré par $m$, car $2^{a} \geqslant a$ ; il a un plus grand élément $a$. Le quotient $m / 2^{a}$ est alors impair, de la forme $2b + 1$.

• Injectivité. Si $2^{a}(2b + 1) = 2^{a'}(2b' + 1)$ avec $a < a'$, on divise par $2^{a}$ : un entier impair serait égal à un entier pair. Donc $a = a'$, puis $b = b'$.

2. C'est vrai pour $r = 1$. Si $\sigma_{r} : \mathbb{N}^{r} \to \mathbb{N}$ est bijective, l'application $\mathbb{N}^{r+1} = \mathbb{N}^{r} \times \mathbb{N} \to \mathbb{N}$, $(x,n) \mapsto \beta'\big(\sigma_{r}(x), n\big)$, où $\beta'$ est la bijection de la question 1, est une composée de bijections. $$\boxed{\mathbb{N}^{r} \text{ est équipotent à } \mathbb{N} \text{ pour tout } r \geqslant 1.}$$

3. On décale la suite $\big(\frac{1}{n}\big)_{n \geqslant 1}$ d'un cran, comme les clients de l'hôtel de Hilbert : $$\boxed{h(x) = \begin{cases} \dfrac{1}{n + 1} & \text{si } x = \dfrac{1}{n},\ n \in \mathbb{N}^{*} \\[2mm] x & \text{sinon} \end{cases}}$$ Le réel $1 = \frac{1}{1}$ n'est pas atteint, et chaque $\frac{1}{m}$ avec $m \geqslant 2$ a l'unique antécédent $\frac{1}{m - 1}$ ; les autres réels sont fixes. L'application $h$ est donc une bijection de $[0\,,1]$ sur $[0\,,1[$.

4. Raisonnons par l'absurde, et soit $\sigma : \mathbb{N} \to \mathbb{N}^{\mathbb{N}}$ une bijection ; on note $u^{(n)} = \sigma(n)$. On définit la suite $v$ par $v_{n} = u^{(n)}_{n} + 1$. Pour tout $n$, $v$ diffère de $u^{(n)}$ en son terme d'indice $n$ : la suite $v$ n'est pas atteinte par $\sigma$. $$\boxed{\mathbb{N}^{\mathbb{N}} \text{ n'est pas équipotent à } \mathbb{N}.}$$ C'est l'argument diagonal du théorème de Cantor, démontré dans le cours pour $\mathcal{P}(E)$ : on modifie la $n$-ième suite à la $n$-ième place.