Compter, c'est numéroter. Tant qu'un ensemble peut faire la queue devant ℕ, il est dénombrable : les entiers relatifs y arrivent, les fractions aussi, malgré les apparences. Les nombres réels, eux, refusent la file — et c'est un argument d'une demi-page, la diagonale de Cantor, qui le démontre. Chaque planche calcule ce qu'elle affirme.
Un ensemble est dénombrable quand on peut ranger ses éléments en une file numérotée : un premier, un deuxième, un troisième… sans oubli et sans doublon. Choisissez une partie de ℕ : elle est rare, de plus en plus rare, et pourtant la file se remplit toujours.
ℤ semble deux fois plus gros que ℕ : il a une moitié négative en supplément. Il suffit pourtant de replier la droite sur elle-même pour que chaque entier relatif reçoive un numéro, et un seul.
Le même tour fonctionne avec k files : le rang n part dans la file n mod k, à la place ⌊n/k⌋. Une réunion de k ensembles dénombrables reste dénombrable.
Entre deux fractions il y en a toujours une autre : ℚ est partout, sans le moindre trou visible. Cela ne l'empêche pas de faire la queue. Deux énumérations le montrent, l'une avec des doublons à barrer, l'autre sans aucun doublon.
La fraction p/q occupe la case (p, q). On balaie les diagonales p + q = 2, 3, 4…, chacune finie : tout le tableau y passe. Les cases réductibles sont barrées, leur valeur ayant déjà reçu un numéro.
La racine vaut 1/1, et p/q engendre p/(p+q) à gauche et (p+q)/q à droite. Lu étage par étage, l'arbre énumère les rationnels strictement positifs sans répétition — et l'on retrouve la place de n'importe quelle fraction en remontant vers la racine.
Supposons qu'une liste numérote tous les réels de l'intervalle [0 ; 1]. On lit la première décimale du premier, la deuxième du deuxième, la troisième du troisième… et l'on fabrique, chiffre après chiffre, un nombre qui ne peut être aucun d'eux.
Cantor donne en 1874 une première démonstration, purement géométrique. On coupe l'intervalle en trois ; le point xn de la liste ne peut pas être dans les trois tiers à la fois, donc on se réfugie dans un tiers qui l'évite, et l'on recommence. Les intervalles emboîtés se referment sur un point que la liste ne contient pas.
Élément signature. Trois volets : on couvre tous les rationnels avec presque rien de longueur — ce qui redémontre autrement que ℝ n'est pas dénombrable ; on rencontre un ensemble de longueur nulle mais non dénombrable ; et l'on découvre qu'il n'existe pas de plus grand infini.
Les rationnels de [0 ; 1] étant numérotés, on enferme le k-ième dans un intervalle de longueur ε/2k. Le total ne dépasse pas ε, aussi petit qu'on veut, alors que l'ensemble recouvert est partout dense. Un tel tour serait impossible si [0 ; 1] tout entier pouvait être numéroté.
On retire le tiers du milieu, puis le tiers du milieu de ce qui reste, indéfiniment. La longueur tombe en (2/3)n, donc vers zéro ; le nombre de morceaux monte en 2n. Ce qui subsiste se lit en base trois avec les seuls chiffres 0 et 2, et remplacer 2 par 1 donne l'écriture binaire d'un réel quelconque de [0 ; 1] : cette poussière est aussi nombreuse que ℝ.
Cantor démontre en toute généralité qu'un ensemble ne peut jamais être mis en bijection avec l'ensemble de ses parties. Il n'y a donc pas de plus grand infini : la tour monte indéfiniment, et son premier étage au-dessus de ℕ est déjà ℝ.