R n'est pas dénombrable

Énoncé

Théorème de Cantor. L'ensemble $\mathbb{R}$ n'est pas dénombrable.

Autrement dit, il n'existe aucune bijection de $\mathbb{N}$ sur $\mathbb{R}$ : l'infini des réels est strictement plus grand que celui des entiers. Cantor publie ce résultat en 1874, puis en donne en 1891 la démonstration devenue célèbre, l'argument diagonal.

Il suffit de traiter l'intervalle $\left[0 \,;\, 1\right[$, car s'il n'est pas dénombrable, $\mathbb{R}$ qui le contient ne l'est pas davantage.

L'argument diagonal

Raisonnement par l'absurde. Supposons $\left[0 \,;\, 1\right[$ dénombrable. Il existe alors une énumération $x_0, x_1, x_2, \ldots$ de tous ses éléments. Écrivons le développement décimal propre de chacun, en notant $a_{n,k}$ le $k$-ième chiffre après la virgule de $x_n$ :

Rang	Développement décimal	Chiffre diagonal
$0$	$0{,}\mathbf{1}\,4\,1\,5\ldots$	$a_{0,0} = 1$
$1$	$0{,}7\,\mathbf{1}\,8\,2\ldots$	$a_{1,1} = 1$
$2$	$0{,}5\,7\,\mathbf{7}\,2\ldots$	$a_{2,2} = 7$
$3$	$0{,}3\,0\,1\,\mathbf{0}\ldots$	$a_{3,3} = 0$

Construction du réel fuyant. On fabrique un nombre $y$ de $\left[0 \,;\, 1\right[$ en imposant à son $k$-ième chiffre décimal $b_k$ d'être différent de $a_{k,k}$ :

$$b_k = \begin{cases} 5 & \text{si } a_{k,k} \neq 5 \\ 4 & \text{si } a_{k,k} = 5 \end{cases}$$

Sur l'exemple, $y = 0{,}5545\ldots$

Contradiction. Le réel $y$ appartient bien à $\left[0 \,;\, 1\right[$. Pourtant, pour tout $n$, il diffère de $x_n$ à la $n$-ième décimale, donc $y \neq x_n$. L'énumération, censée contenir tous les éléments, en oublie un : elle n'existe pas. L'intervalle $\left[0 \,;\, 1\right[$ n'est pas dénombrable, ni $\mathbb{R}$.

Pourquoi les chiffres $4$ et $5$

Ce choix n'est pas cosmétique. Un même réel peut avoir deux développements décimaux, comme

$$0{,}4999\ldots = 0{,}5000\ldots$$

Si l'on autorisait les chiffres $0$ et $9$ dans la construction, le nombre $y$ obtenu pourrait coïncider avec un $x_n$ malgré des développements différents, et l'argument s'effondrerait. En n'employant que $4$ et $5$, on évite toute suite se terminant par une infinité de $0$ ou de $9$ : le développement de $y$ est propre, et la comparaison chiffre à chiffre est licite.

La forme générale : le théorème de Cantor

Le même argument, appliqué aux fonctions indicatrices, donne un résultat bien plus fort :

Pour tout ensemble $E$, il n'existe aucune surjection de $E$ sur l'ensemble $\mathcal{P}(E)$ de ses parties.

Démonstration. Soit $f : E \to \mathcal{P}(E)$. Posons $D = \left\{\, x \in E \;:\; x \notin f(x) \,\right\}$. Si $D$ avait un antécédent $d$, alors $d \in D \iff d \notin f(d) = D$, ce qui est contradictoire. L'ensemble $D$ n'a donc pas d'antécédent, et $f$ n'est pas surjective.

En partant de $\mathbb{N}$, on obtient ainsi une suite strictement croissante d'infinis : il n'y a pas de plus grand cardinal.

Piège classique

Objecter « il suffit d'ajouter $y$ à la liste ». C'est mal lire le raisonnement : on ne construit pas un nombre manquant dans une liste particulière, on montre que toute énumération en oublie un. Ajouter $y$ produit une nouvelle énumération, à laquelle le même procédé appliquera aussitôt un nouveau nombre fuyant.