L'équipotence et les ensembles infinis : approfondissement
Deux ensembles sont équipotents quand une bijection les apparie élément par élément. La première page a montré que ℕ, ℤ et ℚ se rangent en une seule file, alors que ℝ y échappe. Celle-ci va plus loin. On loge une infinité de cars infinis dans l'hôtel de Hilbert, on dénombre tout ce qui peut s'écrire, nombres algébriques compris. On voit pourquoi presque aucun réel ne peut être calculé, et l'on fabrique des bijections explicites entre intervalles. On finit par trois surprises : les transcendants, les ordinaux et le vase de Ross-Littlewood.
Vue d'ensemble
Un ensemble est dénombrable s'il est en bijection avec ℕ, c'est-à-dire si l'on peut ranger ses éléments en une liste a₀, a₁, a₂… sans oubli ni répétition. Les ensembles infinis se répartissent alors en deux grandes familles :
| Dénombrables (cardinal ℵ₀) | Non dénombrables (au moins 2ℵ₀) |
|---|---|
| ℕ, ℤ, ℚ, ℕ × ℕ, ℕk | ℝ, tout intervalle non réduit à un point |
| les mots finis sur un alphabet fini, donc tous les textes et tous les programmes | les suites infinies de 0 et de 1, P(ℕ) |
| les nombres algébriques (racines de polynômes à coefficients entiers) | les nombres transcendants |
| les nombres calculables par un programme | les nombres non calculables |
L'hôtel de Hilbert au complet
Un hôtel aux chambres numérotées 0, 1, 2… est plein, et pourtant il accueille toujours.
Si un client arrive, chaque occupant passe de la chambre n à la chambre n + 1 : la chambre 0 se libère. Pour k clients, on décale de k. Pour un car infini, chaque occupant va de n à 2n, ce qui libère les chambres impaires pour les passagers. Pour une infinité de cars infinis, on numérote chaque personne par un couple (car, place), et l'on range les couples par diagonales : c'est le couplage de Cantor, une bijection de ℕ × ℕ sur ℕ. Une autre idée, envoyer (c, p) sur 2c·3p, loge aussi tout le monde sans collision, mais laisse une infinité de chambres vides : c'est une injection, pas une bijection.
Tout ce qui s'écrit est dénombrable
Avec un alphabet fini, il n'y a qu'une infinité dénombrable de textes.
Rangeons les mots par longueur, puis par ordre alphabétique : a, b, aa, ab, ba, bb, aaa… Chaque mot reçoit un numéro, et chaque numéro un mot. Tous les textes, toutes les formules et tous les programmes informatiques forment donc un ensemble dénombrable. Cantor en tire en 1874 que les nombres algébriques, racines de polynômes à coefficients entiers, sont dénombrables. Il attribue à chaque polynôme une hauteur, son degré plus la somme des valeurs absolues de ses coefficients. Pour une hauteur donnée, il n'y a qu'un nombre fini de polynômes, donc un nombre fini de racines. En listant les hauteurs 2, 3, 4…, on obtient tous les nombres algébriques en une seule liste.
Ce qui ne s'écrit pas : l'arbre binaire et les réels non calculables
L'arbre binaire a une infinité dénombrable de nœuds, mais une infinité non dénombrable de branches.
Un réel de [0 ; 1] s'écrit en base 2 comme une suite infinie de 0 et de 1, c'est-à-dire comme une branche de l'arbre binaire infini. Les nœuds, qui sont des mots finis, se dénombrent. Les branches, non : la diagonale de Cantor fabrique toujours une branche absente d'une liste donnée. Les branches sont en bijection avec les parties de ℕ (une partie = la liste des rangs où l'on lit 1). Conséquence (Turing, 1936) : les programmes étant dénombrables, ils ne peuvent calculer qu'une infinité dénombrable de réels. Presque tous les réels sont donc non calculables : aucun programme n'en donnera jamais les chiffres.
Des bijections explicites entre intervalles
Ajouter ou retirer un point ne change pas le cardinal d'un ensemble infini.
[0 ; 1] et [0 ; 1[ sont équipotents, mais aucune application continue ne le montre. L'astuce est celle de l'hôtel de Hilbert. On choisit dans [0 ; 1] la suite 1, 1/2, 1/3, 1/4…, on décale chacun de ses termes d'un cran (1 ↦ 1/2, 1/2 ↦ 1/3…) et l'on laisse fixes tous les autres points. Le point 1 a disparu de l'image, et rien n'a été perdu. De même, ]0 ; 1[ et ℝ sont équipotents par x ↦ tan(π(x − 1/2)). Le théorème de Cantor-Bernstein évite d'avoir à construire ces bijections. S'il existe une injection de A dans B et une injection de B dans A, une bijection existe.
Signature : les transcendants existent, les ordinaux, le vase de Ross-Littlewood
Trois conséquences surprenantes de la manière de compter l'infini.
Puisque les nombres algébriques sont dénombrables et les réels non, il existe des réels non algébriques : les transcendants. Ils sont même « presque tous » les réels. C'est la preuve de Cantor (1874), qui ne désigne aucun transcendant précis. Liouville en avait construit un en 1844 : L = 10−1! + 10−2! + 10−3! + … = 0,110001000000000000000001… Ses troncatures p/q l'approchent si bien, mieux que 1/qn pour tout n, qu'aucun nombre algébrique ne pourrait le faire. La page vérifie ces inégalités en arithmétique exacte.
Le cardinal compte les éléments ; l'ordinal décrit la manière de les ranger. Rangés dans l'ordre habituel, les entiers forment ω. Mettons 0 tout à la fin : 1, 2, 3, …, 0. On a toujours ℵ₀ éléments, mais l'ordre a maintenant un plus grand élément, ce qui est impossible dans ω : c'est ω + 1. Les pairs puis les impairs donnent ω·2, avec un élément (le premier impair) qui n'a pas de prédécesseur immédiat. Rangeons enfin les entiers selon la 2-valuation de n + 1 : d'abord les n pour lesquels n + 1 est impair, puis ceux pour lesquels n + 1 est le double d'un impair, et ainsi de suite. On obtient une infinité de blocs, chacun infini : c'est ω². Ces bons ordres ont tous le même cardinal, mais aucune bijection croissante ne les relie.
À midi moins une minute, on met les billes 1 à 10 dans un vase et l'on retire la bille 1. À midi moins une demi-minute, on ajoute les billes 11 à 20 et l'on retire la bille 2, et ainsi de suite en doublant la cadence. À chaque étape, le vase contient 9 billes de plus. Combien en contient-il à midi ? Aucune : chaque bille n a été retirée à l'étape n. Si l'on retire plutôt la bille 10n à l'étape n, le vase contient à midi une infinité de billes, celles dont le numéro n'est pas multiple de 10. Le nombre de billes à chaque étape est le même dans les deux cas : la limite des cardinaux n'est pas le cardinal de la limite (Littlewood 1953, Ross 1976).
Une brève histoire
En résumé
Dénombrable
ℕ × ℕ, les mots finis, les programmes et les nombres algébriques se rangent en une seule liste ; l'hôtel de Hilbert ne refuse jamais personne.
Non dénombrable
Les branches de l'arbre binaire, donc les réels et P(ℕ), échappent à toute liste ; presque tous les réels sont transcendants et non calculables.
Compter n'est pas ranger
Ajouter un point ne change pas le cardinal, mais peut changer l'ordinal ; et la limite d'un processus infini ne se calcule pas en passant à la limite sur les nombres.
Pour aller plus loin
Les nombres de Chaitin. La probabilité Ω qu'un programme tiré au hasard s'arrête est un réel bien défini, mais non calculable : connaître ses n premiers chiffres permettrait de résoudre le problème de l'arrêt pour tous les programmes de moins de n bits.
Les ordinaux dénombrables sont eux-mêmes en nombre non dénombrable : leur ensemble est le premier ordinal non dénombrable ω₁, de cardinal ℵ₁. L'hypothèse du continu affirme que ℵ₁ = 2ℵ₀.
Liens. Les ensembles infinis (première page), les cardinaux, les applications, les fondements de la théorie des ensembles, les nombres transcendants.