Exercice 48

1. Supposons par l'absurde qu'une telle suite $(A_{n})$ existe, et considérons la partie $$D = \{n \in \mathbb{N} \mid n \notin A_{n}\}.$$ C'est une partie de $\mathbb{N}$, donc il existe $m \in \mathbb{N}$ tel que $D = A_{m}$. Alors $$m \in D \Longleftrightarrow m \notin A_{m} \Longleftrightarrow m \notin D,$$ ce qui est absurde. $$\boxed{\text{Aucune suite de parties de } \mathbb{N} \text{ ne contient toutes les parties de } \mathbb{N}.}$$ La partie $D$ est construite pour différer de chaque $A_{n}$ au moins en un point, l'entier $n$ lui-même : c'est l'argument diagonal de Cantor (1891).

2. D'après l'exercice 19, tout entier $n \geqslant 1$ s'écrit de façon unique $n = \sum_{j \in J_{n}} 2^{j}$, où $J_{n}$ est une partie finie non vide de $\mathbb{N}$. Posons $F_{0} = \varnothing$ et $F_{n} = J_{n}$ pour $n \geqslant 1$. Soit $F$ une partie finie de $\mathbb{N}$. Si $F = \varnothing$, alors $F = F_{0}$. Sinon, l'entier $n = \sum_{j \in F} 2^{j}$ est au moins égal à $1$, et l'unicité de l'écriture donne $J_{n} = F$, c'est-à-dire $F = F_{n}$. $$\boxed{F_{n} = \text{ensemble des exposants de l'écriture de } n \text{ en base } 2 \text{ convient.}}$$ Par exemple, $13 = 2^{3} + 2^{2} + 2^{0}$ donne $F_{13} = \{0\,,2\,,3\}$. Chaque partie finie apparaît même exactement une fois dans la suite.

3. Les deux raisonnements reposent sur la même construction autoréférente. Dans le paradoxe de Russell, on considère l'ensemble des $x$ tels que $x \notin x$ ; ici, l'ensemble des $n$ tels que $n \notin A_{n}$, l'indice $n$ jouant le rôle de l'objet qui « s'appartient ». Dans les deux cas, on aboutit à une équivalence du type $m \in D \Leftrightarrow m \notin D$. $$\boxed{\text{Même argument diagonal : chez Russell, il interdit un ensemble ; ici, il interdit une suite.}}$$

À retenir : les questions 1 et 2 montrent qu'il y a « beaucoup plus » de parties de $\mathbb{N}$ que de parties finies de $\mathbb{N}$. Le chapitre 2 donnera un sens précis à cette comparaison, et généralisera l'argument diagonal à un ensemble $E$ quelconque et à $\mathcal{P}(E)$.