Argument de la diagonale de Cantor

L'exemple ci-dessous utilise deux des ensembles infinis les plus simples, celui des nombres naturels et celui des fractions positives. L'idée est de montrer que ces deux ensembles, N {\displaystyle \mathbb {N} } et Q + {displaystyle \mathbb {Q^{+}} } ont la même cardinalité.

Tout d'abord, les fractions sont alignées dans un tableau, comme suit :

1 1 1 2 1 3 1 4 1 5 ⋯ 2 1 2 2 2 3 2 4 2 5 ⋯ 3 1 3 2 3 3 3 4 3 5 ⋯ 4 1 4 2 4 3 4 4 4 5 ⋯ 5 1 5 2 5 3 5 4 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{cccccccccc}{\tfrac {1}{1}}}&&{\tfrac {1}{2}}&&{\tfrac {1}{3}}&&{\tfrac {1}{4}}&& {\tfrac {1}{5}}&\cdots \\\\&&&&&&&&&&&\\{\tfrac {2}{1}}}&&{\tfrac {2}{2}}&&{\tfrac {2}{3}}&&{\tfrac {2}{4}}}&&{\tfrac {2}{5}}&\cdots \\\\\\&&&&&&&&&&&&\\\{\tfrac {3}{1}}&&{\tfrac {3}{2}}}&&{\tfrac {3}{3}}&&{\tfrac {3}{4}}}&&{\tfrac {3}{5}}}&\cdots \\\&&&&&&&&&&&&\\\{\tfrac {4}{1}}&&{\tfrac {4}{2}}&&{\tfrac {4}{3}}&&{\tfrac {4}{4}}&&{\tfrac {4}{5}}&\cdots \\\\&&&&&&&&&&\\{\tfrac {5}{1}}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}}&cdots \\\\\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\\\end{array}}}

Ensuite, les chiffres sont comptés, comme indiqué. Les fractions qui peuvent être simplifiées ne sont pas prises en compte :

1 1   ( 1 ) → 1 2   ( 2 ) 1 3   ( 5 ) → 1 4   ( 6 ) 1 5   ( 11 ) → ↙  ↙  2 1   ( 3 ) 2 2   ( ⋅ ) 2 3   ( 7 ) 2 4   ( ⋅ ) 2 5 ⋯ ↓  ↙  3 1   ( 4 ) 3 2   ( 8 ) 3 3   ( ⋅ ) 3 4 3 5 ⋯ ↙ 4 1 ( 9 ) 4 2 ( ⋅ ) 4 3 4 4 4 5 ⋯ ↓ 5 1 ( 10 ) 5 2 5 3 5 4 5 5 5 ⋯ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ {\displaystyle {\begin{array}{lclclclclclclc}{\tfrac {1}{1}}}\ _{\color {Blue}(1)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{2}}\ _{\color {Blue}(2)}&&{\tfrac {1}{3}}\ _{\color {Blue}(5)}&{\color {MidnightBlue}\rightarrow }&{\tfrac {1}{4}}\ _{\color {Blue}(6)}&&{\tfrac {1}{5}}\ _{\color {Blue}(11)}&{\color {MidnightBlue}\rightarrow }\\&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&\{\{\tfrac {2}{1}}\ _{\color {Blue}(3)}&&&{\tfrac {2}{2}}\ _{\color {Blue}(\cdot )}&&{\tfrac {2}{3}}\ _{\color {Blue}(7)}&&{\tfrac {2}{4}}\ _{\color {Blue}(\cdot )}&&&{\tfrac {2}{5}}&\cdots \\\{\color {MidnightBlue}\downarrow}&{\color {MidnightBlue}\nearrow}&&{\tfrac {3}{2}}\ _{\color {Blue}(8)}&&{\tfrac {3}{3}}\ _{\color {Blue}(\cdot )}&&{\tfrac {3}{4}}&&&{\tfrac {3}{5}}&\cdots \\\\\&{\color {MidnightBlue}\swarrow }&&{\color {MidnightBlue}\nearrow }&&&&&&&&\\{\tfrac {4}{1}}\ _{\color {Blue}(9)}&&{\tfrac {4}{2}}\ _{\color {Blue}(\cdot )}&&{\tfrac {4}{3}}&&&&{\frac {4}{4}}&&{\frac {4}{5}}&cdot \\\{\color {MidnightBlue}\downarrow}&{\color {MidnightBlue}\nearrow}&&&&&&&&&\\\{\tfrac {5}{1}}\ _{\couleur {Bleu}(10)}&&{\tfrac {5}{2}}&&{\tfrac {5}{3}}&&{\tfrac {5}{4}}&&{\tfrac {5}{5}}&\cdots \\\\\vdots &&\vdots &&\vdots &&\vdots &&\vdots &\\\\\end{array}}}

De cette façon, les fractions sont comptées :

1 2 3 4 5 6 7 8 9 10 11 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 1 1 2 2 3 1 3 1 4 2 3 3 2 4 5 1 5 ⋯ {\displaystyle {\begin{array}{cccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}\cdots }\\\\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow}&{\color {MidnightBlue}\downarrow}&{\color {MidnightBlue}\downarrow}&{color {MidnightBlue}\downarrow}&{color {MidnightBlue}\downarrow}&amp{color {MidnightBlue}\downarrow}&{\color {MidnightBlue}\downarrow}&{\color {MidnightBlue}\downarrow}&{\color {MidnightBlue}\downarrow}&{color {MidnightBlue}\downarrow}&{color {MidnightBlue}\downarrow}&amp{color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\\[3pt]1&{\tfrac {1}{2}}&2&3&{\tfrac {1}{3}}&{\tfrac {1}{4}}&{\tfrac {2}{3}}&{\tfrac {3}{2}}&4&5&{\tfrac {1}{5}}&\cdots \\\\\\\end{array}}}

En omettant les fractions qui peuvent encore être simplifiées, il y a une bijection qui associe chaque élément des nombres naturels, à un élément des fractions :

Pour montrer que tous les nombres naturels et les fractions ont la même cardinalité, l'élément 0 doit être ajouté ; après chaque fraction, son négatif est ajouté ;

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ⋯ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ 0 1 - 1 1 2 - 1 2 2 - 2 3 - 3 1 3 - 1 3 1 4 - 1 4 2 3 - 2 3 ⋯ {\displaystyle {\begin{array}{cccccccccccccc}{\color {Blue}1}&{\color {Blue}2}&{\color {Blue}3}&{\color {Blue}4}&{\color {Blue}5}&{\color {Blue}6}&{\color {Blue}7}&{\color {Blue}8}&{\color {Blue}9}&{\color {Blue}10}&{\color {Blue}11}&{\color {Blue}12}&{\color {Blue}13}&{\color {Blue}14}&{\color {Blue}15}&{\color {Blue}\cdots }\\\\[3pt]{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{color {MidnightBlue}\downarrow}&{\color {MidnightBlue}\downarrow}&{\color {MidnightBlue}\downarrow}&{\color {MidnightBlue}\downarrow}&{color {MidnightBlue}\downarrow}&{color {MidnightBlue}\downarrow}&amp{color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow}&&{color {MidnightBlue}\downarrow}&{color {MidnightBlue}\downarrow}&amp{color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }&{\color {MidnightBlue}\downarrow }\\\[3pt]0&1&-1&{\tfrac {1}{2}}&-{\tfrac {1}{2}}&2&-2&3&-3&{\tfrac {1}{3}}&-{\tfrac {1}{3}}&{\tfrac {1}{4}}}&-{\tfrac {1}{4}}}&{\tfrac {2}{3}}}&-{\tfrac {2}{3}}}&-{\tfrac {2}{3}}}&cdots \\\\\\end{array}}}

Ainsi, il y a une bijection complète, qui associe une fraction à chaque nombre naturel. En d'autres termes : les deux ensembles ont la même cardinalité. Aujourd'hui, les ensembles qui ont le même nombre d'éléments que l'ensemble des nombres naturels sont dits dénombrables. Les ensembles qui ont moins d'éléments que les nombres naturels sont appelés tout au plus dénombrables. Selon cette définition, l'ensemble des nombres rationnels / fractions est dénombrable.

Les ensembles infinis ont souvent des propriétés qui vont à l'encontre de l'intuition : David Hilbert l'a montré dans une expérience appelée "Hilbert's paradox of the Grand Hotel".

L'ensemble des nombres réels n'a pas la même cardinalité que celui des nombres naturels ; il y a plus de nombres réels que de nombres naturels. L'idée exposée ci-dessus a influencé sa preuve. Dans son article de 1891, Cantor considère l'ensemble T de toutes les séquences infinies de chiffres binaires (c'est-à-dire que chaque chiffre est zéro ou un).

Il commence par une preuve constructive du théorème suivant :

Si s1, s2, ... , _sn, ... est une énumération d'éléments de T, alors il y a toujours un élément s de T qui correspond à aucun _sn dans l'énumération.

Pour le prouver, compte tenu d'une énumération d'éléments de T, comme par exemple

La séquence s est construite en choisissant le 1er chiffre comme complémentaire du 1er chiffre de s1 (en échangeant les 0 contre les 1 et vice versa), le 2ème chiffre comme complémentaire du 2ème chiffre de s2, le 3ème chiffre comme complémentaire du 3ème chiffre de s3, et généralement pour chaque n, le nième chiffre comme complémentaire du nième chiffre de _sn. Dans l'exemple, cela donne :

Par construction, q diffère de chaque _sn, puisque leurs nième chiffres diffèrent (mis en évidence dans l'exemple). Par conséquent, s ne peut pas figurer dans le dénombrement.

Sur la base de ce théorème, Cantor utilise alors une preuve par contradiction pour le démontrer :

L'ensemble T est innombrable.

Il suppose, par contradiction, que T était comptabilisable. Dans ce cas, tous ses éléments pourraient s'écrire comme une énumération s1, s2, ... , _sn, ... . L'application du théorème précédent à cette énumération produirait une séquence s n'appartenant pas à l'énumération. Cependant, s était un élément de T et devait donc être dans l'énumération. Cela contredit l'hypothèse initiale, de sorte que T doit être incomptable.