Argument de la diagonale de Cantor - Définition

Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs est disponible ici.

L'argument de la diagonale de Cantor est une démonstration du mathématicien allemand Georg Cantor de la non-dénombrabilité de l'ensemble des nombres réels.

Cette démonstration est la deuxième écrite par Cantor au sujet de la non-dénombrabilité de $\mathbb{R}$ . La première démonstration n'utilise pas le développement décimal d'un nombre réel. Elle a été adaptée pour de nombreuses démonstrations et l'utilisation de l'argument diagonal est ainsi devenu un classique de la démonstration en mathématiques.

Description

Au lieu de démontrer que $\mathbb{R}$ est non-dénombrable, on va par commodité considérer le sous-ensemble [0,1] de $\mathbb{R}$ et construire, pour toute partie dénombrable D de [0,1], un élément de [0,1] n'appartenant pas à D ; on aura ainsi prouvé que [0,1] ne peut être dénombrable.

Donnons-nous donc une partie dénombrable de [0,1] énumérée à l'aide d'une suite $r = (r i) = {r 1, r 2,..., r i,...}$ . Chaque terme de cette suite a une écriture décimale avec une infinité de chiffres après la virgule (une infinité de 0 pour un nombre décimal), soit :

r_i0 = 0 , r_i1 r_i2 ... r_in ...

Construisons maintenant un nombre réel x dans [0,1] en considérant le n^ième 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 …

…

Les décimales que nous considérons sont celles se situant sur la diagonale. On définit les chiffres composant x de la façon suivante : si le n^e chiffre de r_n est différent de 1, alors le n^e chiffre de x est 1, sinon le n^e est 2. Par exemple avec la suite ci-dessus, on a 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 le premier chiffre après le point décimal de x est différent du premier chiffre après la décimal de r₁, de même pour r₂, etc. donc x n'est pas élément de la suite r_i.

Conclusion : l'intervalle [0, 1] n'est pas dénombrable et a fortiori $\mathbb{R}$ ne l'est pas non plus.

Cantor a utilisé une forme généralisée de l'argument de la diagonale pour démontrer le théorème de Cantor : pour tout ensemble S, 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). En effet, s’il existe une telle surjection f de S sur P(S), on peut considérer l'ensemble A des éléments x de S tels que x n'appartienne pas à f(x). Comme A appartient à P(S), il existe, du fait de la surjectivité de f, un élément a de S tel que f(a)=A. On aboutit à une contradiction aussi bien dans le cas où a appartient à A que dans le cas contraire.

Voici une version plus " accessible " de cet argument :

" 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 ? "

Des raisonnements analogues ont été utilisés pour prouver l'existence ou la non-existence de certains objets en mathématiques. Par exemple, la preuve du problème de l'arrêt utilise essentiellement l'argument de la diagonale.

Cette démonstration 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}$ et strictement plus petite que celle de $\mathbb{R}$ . L'hypothèse qu'il n'y en a pas 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)) conduit à l'hypothèse du continu généralisée.