Argument de la diagonale de Cantor

L'argument de la diagonale, ou argument diagonal fut découvert par le mathématicien allemand Georg Cantor (1845-1918) et publié en 1891. Il permit à ce dernier de donner une deuxième démonstration de la non-dénombrabilité de l'ensemble des nombres réels, beaucoup plus simple, selon Cantor lui-même, que la première qu'il avait publiée en 1874, et qui utilisait des arguments d'analyse, en particulier le théorème des segments emboîtés. L'argument diagonal fut exploité dans un cadre plus général par Cantor dans le même article pour son théorème sur la cardinalité de l'ensemble des parties d'un ensemble.

L'argument diagonal s'applique à une relation ou une fonction (éventuellement partielle) à deux arguments sur un même domaine E, ou, ce qui revient au même, à une fonction qui à chaque élément de E associe une fonction définie sur E. Il utilise de façon essentielle la diagonale de E × E : l'ensemble des couples (x, x) pour x dans E, d'où l'appellation.

Il a été adapté pour de nombreuses démonstrations. Des paradoxes qui ont joué un rôle dans la fondation de la théorie des ensembles comme le paradoxe de Russell (inspiré du théorème de Cantor) mais aussi le paradoxe de Richard s'appuient sur le raisonnement diagonal. Le théorème d'incomplétude de Gödel l'utilise pour un lemme essentiel. La théorie de la calculabilité en fait grand usage, à commencer par le problème de l'arrêt. L'argument diagonal est ainsi devenu un classique de la démonstration en mathématiques.

On peut s'appuyer sur le développement décimal des réels. À partir d'une énumération de réels distincts, l'extraction de la n-ième décimale du n-ième réel permet de construire un nouveau réel qui n'était pas dans l'énumération. Les décimales peuvent être présentées sous forme d'un tableau semi-infini à deux entrées dont la n-ième ligne comprend la liste des décimales du n-ième réel. La liste des décimales extraites se lit sur la diagonale, d'où l'appellation argument de la diagonale.

Un développement décimal d'un réel est une suite de chiffres. L'argument est en fait valable pour une énumération de suites d'entiers. Il est d'ailleurs légèrement plus simple dans ce dernier cas, puisque le problème de la double représentation des décimaux ne se pose pas.

La non dénombrabilité des réels

Pour démontrer que $\mathbb{R}$ est non dénombrable, il suffit de démontrer la non dénombrabilité du sous-ensemble [0,1] de $\mathbb{R}$, donc de construire, pour toute partie dénombrable D de [0,1], un élément de [0,1] n'appartenant pas à D.

Soit donc une partie dénombrable de [0,1] énumérée à l'aide d'une suite r = (r₁, r₂, r₃, ... ). Chaque terme de cette suite a une écriture décimale avec une infinité de chiffres après la virgule (éventuellement une infinité de zéros pour un nombre décimal), soit :

r_i = 0 , r_i1 r_i2 ... r_in ...

On construit maintenant un nombre réel x dans [0,1] en considérant le n chiffre après la virgule de r_n. Par exemple, pour la suite r :

r₁ = 0 , 0 1 0 5 1 1 0 …

r₂ = 0 , 4 1 3 2 0 4 3 …

r₃ = 0 , 8 2 4 5 0 2 6 …

r₄ = 0 , 2 3 3 0 1 2 6 …

r₅ = 0 , 4 1 0 7 2 4 6 …

r₆ = 0 , 9 9 3 7 8 1 8 …

r₇ = 0 , 0 1 0 5 1 3 0 …

…

Le nombre réel x est construit par la donnée de ses décimales suivant la règle : si la n décimale de r_n est différente de 1, alors la n décimale de x est 1, sinon la n est 2. Par exemple avec la suite ci-dessus, la règle donne x = 0 , 1 2 1 1 1 2 1 …

Le nombre x est clairement dans l'intervalle [0, 1] mais ne peut pas être dans la suite ( r₁, r₂, r₃, ... ), car il n'est égal à aucun des nombres de la suite : il ne peut pas être égal à r₁ car la première décimale de x est différente de celle de r₁, de même pour r₂ en considérant la deuxième décimale, etc.

La non unicité de l'écriture décimale pour les décimaux non nuls (deux écritures sont possibles pour ces nombres, l'une avec toutes les décimales valant 0 sauf un nombre fini, l'autre avec toutes les décimales valant 9 sauf un nombre fini) n'est pas un écueil au raisonnement précédent car le nombre diagonal x ne peut être décimal, puisque son écriture décimale est infinie et ne comporte que les chiffres 1 et 2.

La preuve de Cantor

Dans l'article de 1891, où il introduit ce raisonnement, Georg Cantor construit à partir de toute énumération de suites de deux caractères distincts m et w une nouvelle suite, qui ne comporte également que m et w et qui n'était pas déjà énumérée. Le raisonnement est exactement celui décrit ci-dessus pour les réels, simplifié du fait que l'on n'a que deux chiffres — on peut prendre 1 et 2 pour m et w — et que cette fois-ci, comme on traite directement des suites, il n'y a plus de problème de double représentation.

La preuve se généralise de façon évidente au cas des suites d'éléments d'un ensemble à plus de deux éléments (fini ou infini).

On en déduit donc que l'ensemble des suites infinies de 0 et de 1 n'est pas dénombrable. Or celui-ci correspond à l'écriture binaire des réels dans [0,1]. Cependant l'écriture binaire des nombres dyadiques n'est pas unique, et si l'on veut adapter le raisonnement aux réels, rien n'assure que le réel diagonal construit ne soit pas dyadique : son développement binaire pourrait très bien se terminer par une infinité de 0 ou par une infinité de 1.

Cantor ne détaille pas l'argument, mais il sait par ailleurs que l'ensemble des réels dyadiques est dénombrable, et que la réunion de deux ensembles dénombrables est dénombrable. Il peut donc en déduire (de façon plus indirecte que dans le raisonnement indiqué ci-dessus) que l'ensemble des réels entre 0 et 1 n'est pas dénombrable.

Cantor a utilisé l'argument de la diagonale pour démontrer que pour tout ensemble S (fini ou infini), l'ensemble des parties de S, noté généralement P(S), est « strictement plus grand » que S lui-même. En d'autre termes, il ne peut pas exister de surjection de S vers P(S), et donc pas non plus d'injection de P(S) dans S. Ce résultat est aujourd'hui connu sous le nom de théorème de Cantor.

Pour cela, il nous suffit de montrer que, pour toute fonction f de S dans P(S), on peut construire un ensemble qui n'est pas dans l'ensemble image de f. En effet, soit l'ensemble A des éléments x de S tels que x n'appartienne pas à f(x). S'il existait un élément a de S tel que f(a)=A, On aboutirait à une contradiction aussi bien dans le cas où a appartient à A, que dans le cas contraire. L'ensemble A n'appartient donc pas à l'image de f : celle-ci ne peut être surjective.

Voici une version plus « imagée » de cet argument, dans le cas où S est l'ensemble des entiers naturels :

«  Soit un cahier comportant autant de pages que l'on veut. On numérote chaque page, et, sur chacune d'entre elles, on écrit un ensemble d'entiers (tous différents), de telle sorte à ne jamais écrire deux fois le même ensemble.
On dit qu'un nombre N est ordinaire si l'ensemble écrit à la page N ne contient pas N ; dans le cas contraire, on dit que N est extraordinaire. Supposons que l'on ait écrit sur ce cahier tous les ensembles possibles. La question est : à quelle catégorie appartient l'entier sur la page duquel on a écrit l'ensemble des nombres ordinaires ?  »

Dans le cas dénombrable, cette dernière forme de l'argument diagonal est identique à celle du paragraphe précédent, où l'on montrait que l'ensemble des suites de deux éléments n'est pas dénombrable : il suffit de choisir un élément pour « appartient », l'autre pour « n'appartient pas ». L'argument diagonal utilisé pour le théorème de Cantor ne diffère donc de celui pour les suites que parce qu'il est utilisé pour un ensemble S quelconque, au lieu de l'ensemble des entiers naturels. On l'adapte d'ailleurs directement pour montrer que l'ensemble des fonctions de S dans un ensemble quelconque à plus de deux éléments n'a pas même cardinalité que S.

Le raisonnement diagonal est constructif (on dit aussi effectif). C'est tout à fait clair dans le cas des suites, si chacune des suites de l'énumération est engendrée par un procédé calculatoire, on a un procédé pour calculer la suite diagonale. Cela signifie que l'on peut théoriquement calculer autant de termes de la suite que l'on souhaite, les seules limites sont matérielles, temps et puissance de calcul.

Le raisonnement diagonal donné pour les réels reste bien également constructif. Supposons qu'une suite (r_i) de réels entre 0 et 1 nous soit donnée effectivement par des développements décimaux : on dispose d'un algorithme qui peut calculer, étant donné deux entiers i' et n la n*-ième décimale d'un même développement de* r_i. Alors le procédé diagonal permet bien de calculer un réel n'appartenant pas à cette suite (et même une infinité dénombrable de réels tous distincts, en reportant à chaque étape le réel diagonal en tête de liste, ce qui décale les diagonales). On l'adapterait facilement pour une suite dénombrable de réels en général.

Le caractère effectif du raisonnement diagonal en a fait l'un des fondements de la théorie de la calculabilité, autant pour les résultats de non-existence que sont les démonstrations d'indécidabilité algorithmique, à commencer par la preuve de l'indécidabilité du problème de l'arrêt, que pour des résultats d'existence, comme les théorèmes de point fixe de Kleene.

Sous une forme très proche de ces théorèmes de point fixe, il est également un argument essentiel du premier théorème d'incomplétude de Gödel (qui est un résultat d'indécidabilité logique) : en l'occurrence le lemme qui permet de montrer l'existence d'une proposition qui entraîne sa propre non-prouvabilité, et qui est d'ailleurs souvent appelé lemme de diagonalisation.

La démonstration ci-dessus montre que l'ensemble des nombres réels est « strictement plus grand » que l'ensemble des nombres entiers. On peut se poser la question de savoir s'il existe un ensemble dont la cardinalité est strictement plus grande que celle de $\mathbb{N}$ mais strictement plus petite que celle de $\mathbb{R}$. L'hypothèse qu'il n'y en a pas, due à Cantor, est appelée hypothèse du continu.

De même la question de savoir s'il existe un ensemble de cardinalité comprise strictement entre card(S) et card(P(S)), pour un ensemble S infini quelconque, conduit à l'hypothèse du continu généralisée.