Que démontre l'argument diagonal de Cantor ?

Il démontre que les nombres réels entre 0 et 1 sont indénombrables : aucune liste, aussi ingénieusement construite soit-elle, ne peut contenir tous les réels de cet intervalle. Il y a tout simplement plus de réels qu'il n'y a de positions dans une quelconque liste.

Que signifie « indénombrable » ?

Un ensemble est dénombrable si l'on peut associer à chacun de ses membres un nombre naturel (1, 2, 3, ...) sans rien laisser de côté. Les entiers naturels, les entiers relatifs et même les rationnels sont tous dénombrables. Les réels ne le sont pas : ils sont trop nombreux pour être placés dans une telle correspondance biunivoque.

Pourquoi ne peut-on pas simplement ajouter le nombre manquant à la liste ?

On peut, mais l'argument diagonal s'applique alors à nouveau à la nouvelle liste plus longue et produit encore un nombre manquant. L'argument fonctionne pour toute liste, aussi longue ou ingénieusement arrangée soit-elle, donc il n'y a aucun moyen de compléter la liste.

Pourquoi évite-t-on les chiffres 0 et 9 lors du changement ?

Certains réels ont deux représentations décimales : 0,4999... et 0,5000... désignent le même nombre. Si tu changes un chiffre en 0 ou 9, tu pourrais atterrir accidentellement sur l'«autre nom» d'un nombre déjà présent dans la liste. Éviter 0 et 9 contourne cette subtilité et garde la démonstration propre.

Les rationnels sont-ils aussi indénombrables ?

Non. Les rationnels sont dénombrables : on peut lister systématiquement toute fraction p/q et attribuer à chacune un indice entier naturel, sans rien omettre. L'argument diagonal de Cantor vise les réels, pas les rationnels.

L'argument diagonal de Cantor : pourquoi les réels ne peuvent pas être listés

Suppose que quelqu'un te tende une liste. C'est une liste infinie, et cette personne prétend qu'elle contient tous les nombres réels entre 0 et 1. Pas un échantillon, pas une sélection : chacun d'eux, indexé proprement comme r1, r2, r3, et ainsi de suite, s'étirant indéfiniment.

La réponse de Georg Cantor, en 1891, fut la suivante : quelle que soit la liste que tu me tends, je peux lire un nombre qui ne s'y trouve pas. La construction prend environ trente secondes à décrire. La conséquence a mis des décennies à être absorbée par les mathématiciens, car elle signifie que l'infini existe en plus d'une taille.

Compter et lister

Avant le mouvement diagonal, il est utile d'être précis sur ce que « dénombrable » signifie. Un ensemble est dénombrable si l'on peut attribuer à chaque élément une étiquette entière naturelle unique : un premier élément, un deuxième, un troisième, et ainsi de suite, sans rien laisser de côté. Les entiers naturels sont dénombrables par définition. Les entiers relatifs aussi (on les liste comme 0, 1, -1, 2, -2, ...) et même les rationnels, bien que lister toutes les fractions nécessite un astucieux motif en zigzag.

L'argument de Cantor montre que les réels entre 0 et 1 sont genuinement différents : aucun étiquetage n'existe, quoi qu'on essaie. Ce n'est pas un échec d'imagination. C'est une démonstration que la tâche est impossible.

Supposons que la liste existe

L'argument est une démonstration par l'absurde. On commence par accorder à l'adversaire tout ce qu'il veut : supposons qu'une liste complète de tous les réels dans (0, 1) existe réellement. On écrit chaque nombre sous forme de développement décimal infini.

La liste pourrait commencer ainsi :

r1 = 0,14159265...
r2 = 0,73205080...
r3 = 0,00000000...
r4 = 0,27182818...
r5 = 0,91415926...
...

Chaque entrée continue indéfiniment. La liste continue indéfiniment. Et, par hypothèse, tout réel entre 0 et 1 apparaît quelque part dedans.

Regarde maintenant ce qui se passe quand tu lis la diagonale.

Lire la diagonale

Regarde le premier chiffre décimal de r1, le deuxième chiffre décimal de r2, le troisième de r3, et ainsi de suite. Dans l'exemple ci-dessus, ces chiffres diagonaux sont : 1, 3, 0, 2, 9, ...

Tu construis maintenant un nouveau nombre, appelons-le d, chiffre par chiffre. La règle : pour chaque chiffre diagonal, choisis un chiffre différent, en évitant délibérément 0 et 9.

r₁	.	1	4	1	5	9
r₂	.	3	3	3	3	3
r₃	.	5	0	0	0	0
r₄	.	7	1	8	2	8
r₅	.	6	0	2	5	9
new	.	2	4	1	3	8	…

Each highlighted digit sits on the diagonal. The new number changes every one of them (1 3 0 2 9 becomes 2 4 1 3 8), so it cannot equal any row in the list.

Les chiffres diagonaux sont 1, 3, 0, 2, 9. En appliquant la règle, on obtient 2, 4, 1, 3, 8. Donc d = 0,24138...

Éviter 0 et 9 est une précaution petite mais nécessaire. Certains réels ont deux représentations décimales : 0,4999... et 0,5000... désignent le même point sur la droite numérique. Changer un chiffre en 0 ou 9 pourrait te faire atterrir sur l'« autre nom » d'un nombre déjà dans la liste, ce qui brouillerait l'argument. En restant dans la plage 1 à 8 pour chaque chiffre changé, tu garantis que d n'a qu'un seul développement décimal, et la comparaison ci-dessous est propre.

Le nouveau nombre diffère de chaque entrée

Voici le résultat.

d diffère de r1 au premier chiffre décimal

Le premier chiffre de d a été choisi pour différer du premier chiffre de r1. Donc d n'est pas égal à r1. Ils diffèrent en position 1.

d diffère de r2 au deuxième chiffre décimal

Le deuxième chiffre de d a été choisi pour différer du deuxième chiffre de r2. Donc d n'est pas égal à r2. Ils diffèrent en position 2.

d diffère de rn au n-ième chiffre décimal, pour tout n

Par construction, le n-ième chiffre de d diffère du n-ième chiffre de rn. Puisque deux nombres ayant un chiffre différent en une quelconque position sont inégaux, d n'est pas égal à rn, pour aucun n que tu nommes.

C'est le mouvement diagonal : d a été conçu pour entrer en conflit avec chaque entrée de la liste, précisément à l'endroit où chaque entrée est la plus exposée, sa propre position diagonale.

d est un réel entre 0 et 1, et pourtant il n'est pas dans la liste

Le nombre d = 0,24138... est clairement un réel dans l'intervalle (0, 1). Mais nous venons de montrer qu'il diffère de r1, de r2, de r3, de chaque entrée. Si la liste était complète, d devrait apparaître quelque part dedans. Il n'y est pas. Donc la liste n'est pas complète.

La contradiction est nette : nous avons supposé que la liste était complète, et nous avons produit un réel qui ne s'y trouve pas. L'hypothèse doit être fausse. Aucune liste complète des réels entre 0 et 1 ne peut exister.

Ce que cela dit vraiment

Les mathématiciens disent que les entiers naturels ont la cardinalité aleph-zéro (écrit avec la lettre hébraïque aleph : le premier cardinal transfini). Les réels ont une cardinalité strictement plus grande, parfois écrite c ou 2 à la puissance aleph-zéro. L'argument de Cantor est ce qui établit que ces deux infinis ne sont pas de la même taille.

Cela fut profondément controversé quand Cantor le publia. Certains collègues rejetèrent le résultat comme une curiosité ou une erreur. Ce n'est ni l'un ni l'autre. Il est au fondement de la façon dont les mathématiciens pensent aux ensembles, à la cardinalité et à la structure de la droite réelle, et il est directement lié aux questions de ce qui peut et ne peut pas être calculé (voir aussi la démonstration du théorème de Goodstein pour un autre cas où quelque chose de prouvablement vrai bute contre les limites des systèmes formels).

Pourquoi la diagonale fonctionne

Ce qui rend l'argument élégant, c'est sa spécificité. Tu ne devines pas un nombre manquant et tu ne fais pas appel à une intuition vague sur la grandeur des réels. Tu lis exactement quelles positions de la liste chaque entrée contrôle, puis tu construis un nombre qui échappe à chaque entrée précisément à cette position.

La liste elle-même te dit où regarder. Chaque entrée de la liste te donne une coordonnée, son propre chiffre diagonal, et la construction transforme ces coordonnées en un nombre que la liste ne peut pas contenir.

La simplicité est trompeuse. Il n'y a rien ici qui nécessite de savoir quoi que ce soit sur les entrées de la liste. Peu importe quels nombres s'y trouvent, dans quel ordre, ni comment ils ont été choisis. L'argument est universel : prends n'importe quelle liste de réels, et la construction diagonale produit un réel qui ne s'y trouve pas.

Le zen de tout cela

L'argument diagonal de Cantor s'inscrit dans une longue tradition de résultats mathématiques qui semblent ne pas devoir fonctionner. Tu fixes la démonstration et tu attends le truc, l'hypothèse cachée, l'endroit où la logique glisse. Il n'est pas là. La démonstration est exactement aussi simple qu'elle en a l'air.

Ce qu'elle te demande d'accepter est plus étrange que la démonstration elle-même : que « infini » n'est pas une destination unique. Les entiers et les réels sont tous deux infinis, mais ils sont infinis de façons catégoriquement différentes. L'argument diagonal est la ligne de démarcation.

Pour ressentir plus profondément comment les collections infinies peuvent se comporter de façon étrange, la structure des décimales infinies est un bon endroit où regarder ensuite, ou comment fonctionnent les limites quand des suites approchent une valeur indéfiniment sans l'atteindre. L'argument diagonal appartient à la même famille : un regard précis et patient sur ce qui se passe à la frontière de l'infini, là où l'intuition a besoin d'une démonstration pour rester honnête.

L'infini n'est pas une seule chose. C'est la nouvelle. L'argument qui la délivre tient sur une demi-page.