L’argument diagonal : ℝ n’est pas dénombrable

On a su énumérer les rationnels, qui sont pourtant partout denses sur la droite : entre deux d’entre eux il y en a toujours un troisième, et cela ne les a pas empêchés de tenir dans une suite. L’expérience suggère qu’avec assez d’astuce, on énumérerait aussi les réels. Cantor a montré en 1874 qu’il n’en est rien, et sa seconde démonstration, celle de 1891, tient dans un tableau. Elle ne fabrique pas un nombre manquant par hasard : elle le construit exprès, chiffre par chiffre, pour qu’il diffère de chacun de ceux qu’on prétendait avoir tous écrits.

L’article poursuit la série Aux fondations. Il fait suite à « Dénombrable : ℕ, ℤ et ℚ ont le même nombre d’éléments », dont il reprend la définition et le lemme sur les parties de ℕ, et il conclut le raisonnement ouvert par le paradoxe de Russell, dont le procédé est ici repris pour lui-même.

1. Ce qu’il faut avoir sous la main

Dans notre ouvrage sur les fondations des mathématiques, un nombre réel n’est pas une écriture décimale : c’est une coupure de Dedekind, c’est-à-dire une partie $r$ de $\mathbb{Q}$ qui est non vide et distincte de $\mathbb{Q}$ , dont tout élément est strictement inférieur à tout rationnel qui n’y est pas, et qui n’a pas de plus grand élément. Chaque réel est donc un élément de $\mathcal{P}(\mathbb{Q})$ , et c’est l’axiome de compréhension qui fait de $\mathbb{R}$ un ensemble — le lecteur du recensement des axiomes reconnaîtra le procédé.

L’écriture décimale vient ensuite, et l’ouvrage la construit sans ambiguïté : pour $x\geq 0$ , il pose $u_{n}=\lfloor 10^{n}x\rfloor/10^{n}$ , de sorte que

$\displaystyle u_{n}\leq x<u_{n}+\frac{1}{10^{n}}\qquad\text{pour tout }n.$

Les chiffres $a_{n}$ de la partie décimale se lisent sur cette suite, et l’inégalité de droite est stricte. Cette stricte inégalité n’est pas un détail : elle interdit les écritures qui se terminent par une infinité de neuf. L’ouvrage a donc déjà choisi, pour chaque réel, une écriture décimale et une seule, celle par défaut. C’est exactement la précaution dont la démonstration qui suit a besoin.

2. Le théorème, et sa démonstration

Théorème (Cantor, 1891). L’intervalle $[0,1[$ n’est pas dénombrable. Autrement dit, aucune application de $\mathbb{N}$ vers $[0,1[$ n’est surjective.

Preuve. Soit $f:\mathbb{N}\rightarrow[0,1[$ une application quelconque. Écrivons chaque $f(n)$ au moyen de son écriture décimale par défaut :

$\displaystyle f(n)=0,a_{n,1}a_{n,2}a_{n,3}\dots\qquad\text{avec }a_{n,k}\in\{0,1,\dots,9\}.$

Construisons un réel $b$ en choisissant ses chiffres un à un : pour chaque $n\geq 1$ , posons

$\displaystyle b_{n}=\left\{\begin{array}{rcl} 5 & \text{si} & a_{n,n}\neq 5, \\ 6 & \text{si} & a_{n,n}=5, \end{array}\right.\qquad\text{et}\qquad b=0,b_{1}b_{2}b_{3}\dots$

Le nombre $b$ appartient bien à $[0,1[$ : ses chiffres valent tous $5$ ou $6$ , donc l’écriture ne se termine ni par une infinité de neuf ni par une infinité de zéros, et elle est l’écriture par défaut du réel qu’elle désigne. Or, pour chaque $n$ , le $n$ -ième chiffre de $b$ diffère du $n$ -ième chiffre de $f(n)$ par construction. Deux réels dont les écritures par défaut diffèrent en un rang sont distincts ; donc $b\neq f(n)$ , et ceci pour tout $n$ . Le réel $b$ n’est pas dans l’image de $f$ , qui n’est donc pas surjective. $\quad\Box$

Le passage de $[0,1[$ à $\mathbb{R}$ ne demande rien de plus : si $\mathbb{R}$ était dénombrable, sa partie $[0,1[$ le serait aussi ou serait finie, puisque toute partie d’un ensemble dénombrable est finie ou dénombrable. Elle n’est ni l’un ni l’autre. Donc $\mathbb{R}$ n’est pas dénombrable.

3. Le seul endroit où l’on peut se tromper

La démonstration est célèbre, et sa version rapide contient souvent une faille que l’on corrige ici d’avance. Un même réel peut admettre deux écritures décimales : $0{,}4999\dots$ et $0{,}5000\dots$ désignent le même nombre. Si l’on se contentait de dire « je change le $n$ -ième chiffre », on pourrait fabriquer une écriture différente d’un nombre pourtant déjà énuméré, et la démonstration ne prouverait rien.

Deux précautions lèvent la difficulté, et l’une comme l’autre suffit. La première est celle de l’ouvrage : ne considérer que l’écriture par défaut, ce qui ôte toute ambiguïté. La seconde est celle du choix des chiffres : en n’employant que des $5$ et des $6$ , on reste loin des deux écritures concurrentes, qui ne diffèrent que par des queues de neuf ou de zéros. Ce n’est pas une coquetterie de rédaction : sans cette précaution, l’argument est faux.

4. Le même argument, sans décimales

Les chiffres ne sont qu’un vêtement. Débarrassé d’eux, l’argument devient un théorème d’une généralité bien plus grande, et sa démonstration tient en trois lignes.

Théorème de Cantor. Pour tout ensemble $X$ , aucune application $f:X\rightarrow\mathcal{P}(X)$ n’est surjective.

Preuve. Posons $D=\{x\in X\mid x\notin f(x)\}$ , qui est une partie de $X$ par l’axiome de compréhension. Supposons $D=f(d)$ pour un certain $d\in X$ . Alors $d\in D$ équivaut à $d\notin f(d)$ , c’est-à-dire à $d\notin D$ : contradiction. Donc $D$ n’a pas d’antécédent. $\quad\Box$

On aura reconnu, mot pour mot, la construction de Russell — avec $f(x)$ à la place du second $x$ . La parenté n’est pas anecdotique : c’est le même procédé, employé deux fois à des fins opposées. Chez Russell, il détruit un axiome trop généreux ; ici, il démontre un théorème. Appliqué à $X=\mathbb{N}$ , il donne directement que $\mathcal{P}(\mathbb{N})$ n’est pas dénombrable, sans parler de virgule ni de chiffre.

5. Trois conséquences immédiates

Les irrationnels ne sont pas dénombrables. Si $\mathbb{R}\setminus\mathbb{Q}$ l’était, $\mathbb{R}$ serait la réunion de deux ensembles dénombrables, donc dénombrable. Au sens du nombre d’éléments, presque tous les réels sont irrationnels — alors que le lycée ne sait en nommer que deux ou trois.
Il existe des nombres transcendants. Les nombres algébriques — racines d’un polynôme à coefficients entiers — forment un ensemble dénombrable ; il reste donc des réels qui n’en sont pas. Cantor a ainsi établi leur existence sans en exhiber un seul, alors que Liouville avait dû en construire un à la main trente ans plus tôt. C’est l’exemple canonique d’une démonstration non constructive.
Il y a au moins deux infinis. Celui de $\mathbb{N}$ , et celui de $\mathbb{R}$ . Le théorème de Cantor en donne même une infinité : $X$ , $\mathcal{P}(X)$ , $\mathcal{P}(\mathcal{P}(X))$ , et ainsi de suite, chacun strictement plus grand que le précédent.

6. La question qu’on ne peut pas trancher

Une fois établi qu’il y a strictement plus de réels que d’entiers, une question se pose d’elle-même : y a-t-il quelque chose entre les deux ? Existe-t-il une partie de $\mathbb{R}$ qui ne soit ni dénombrable, ni en bijection avec $\mathbb{R}$ ? Cantor a conjecturé que non, et il y a consacré les dernières années de sa vie sans aboutir. On sait aujourd’hui pourquoi : la question ne peut pas être tranchée dans ZF. C’est l’objet de l’article à paraître « Corrigé, et l’hypothèse du continu », après l’exercice « Dénombrable ou non ? » qui met le procédé diagonal à l’épreuve sur dix ensembles.

La construction de $\mathbb{R}$ par les coupures de Dedekind occupe la section 3.7 de Discours formel sur les mathématiques pour le secondaire, Volume I, et la représentation décimale des réels, avec les valeurs approchées par défaut et par excès, celle des suites réelles. L’argument diagonal n’y figure pas : il est construit ici sur ces deux acquis.

Formalis Mathematica

Rigueur et formalisme au cœur de l’apprentissage et de l’enseignement des mathématiques

L’argument diagonal : ℝ n’est pas dénombrable

1. Ce qu’il faut avoir sous la main

2. Le théorème, et sa démonstration

3. Le seul endroit où l’on peut se tromper

4. Le même argument, sans décimales

5. Trois conséquences immédiates

6. La question qu’on ne peut pas trancher

3 réflexions sur “L’argument diagonal : ℝ n’est pas dénombrable”

Votre commentaire Annuler la réponse.

1. Ce qu’il faut avoir sous la main

2. Le théorème, et sa démonstration

3. Le seul endroit où l’on peut se tromper

4. Le même argument, sans décimales

5. Trois conséquences immédiates

6. La question qu’on ne peut pas trancher

Partagez :

Similaire

3 réflexions sur “L’argument diagonal : ℝ n’est pas dénombrable”

Votre commentaire Annuler la réponse.