Corrigé, et l’hypothèse du continu

Sept des dix ensembles proposés sont dénombrables, trois ne le sont pas, et l’intuition se trompe précisément là où on l’attend : les polynômes entiers et les nombres algébriques, qui semblent innombrables, s’énumèrent sans peine ; les suites de zéros et de uns, qui semblent modestes, ne s’énumèrent pas. Le corrigé traite les dix cas, puis s’arrête longuement sur la question 4, qui cache un axiome, et sur la question 5, qui débouche sur le seul énoncé célèbre que les mathématiques aient démontré indécidable.

L’article corrige l’exercice précédent de la série Aux fondations, « Dénombrable ou non ? ». Il emploie l’argument diagonal de « L’argument diagonal : ℝ n’est pas dénombrable », et la notion d’indépendance déjà rencontrée à propos du postulat des parallèles dans les cinq groupes d’axiomes de Hilbert.

1. Les sept dénombrables

(a) L’application $n\mapsto 2n$ est une bijection de $\mathbb{N}$ vers les pairs. (b) $\mathbb{Z}\times\mathbb{Z}$ est un produit de deux ensembles dénombrables, donc dénombrable. (c) $\mathbb{Q}\cap[0,1]$ est une partie infinie de $\mathbb{Q}$ , donc dénombrable par le lemme sur les parties. (i) Un intervalle $]a,b[$ à extrémités rationnelles est entièrement déterminé par le couple $(a,b)$ , et l’application qui à l’intervalle associe ce couple est injective : l’ensemble s’injecte dans $\mathbb{Q}\times\mathbb{Q}$ , qui est dénombrable.

(d) Les parties finies de $\mathbb{N}$ . À une partie finie $A$ , associons l’entier $\varphi(A)=\sum_{k\in A}2^{k}$ , la somme vide valant $0$ . L’unicité de l’écriture d’un entier en base deux montre que $\varphi$ est injective — et même bijective sur $\mathbb{N}$ . L’ensemble des parties finies est donc dénombrable. Chaque partie finie tient dans un entier : c’est tout le contenu du résultat.

(f) Les polynômes à coefficients entiers. Un polynôme de degré au plus $n$ est un $(n+1)$ -uplet d’entiers, et $\mathbb{Z}^{n+1}$ est dénombrable par récurrence sur $n$ . L’ensemble cherché est la réunion, pour $n\in\mathbb{N}$ , de ces ensembles dénombrables ; il est donc dénombrable. Ici, aucun choix arbitraire n’est fait : l’énumération de $\mathbb{Z}^{n+1}$ est donnée par une formule explicite, la même pour tout $n$ . Cette remarque, qui paraît pointilleuse, sera le sujet du paragraphe 4.

(g) Les nombres algébriques. Un polynôme non nul de degré $n$ possède au plus $n$ racines réelles. À chaque polynôme non nul correspond donc un ensemble fini de réels, que l’on peut énumérer sans aucun arbitraire, par ordre croissant. En parcourant les polynômes selon l’énumération de (f) et, pour chacun, ses racines par ordre croissant, on énumère tous les nombres algébriques. L’ensemble est dénombrable — ce qui inclut tous les rationnels, toutes les racines carrées, cubiques, et leurs combinaisons.

2. Les trois qui résistent

(e) Les suites de zéros et de uns. Soit $f:\mathbb{N}\rightarrow\{0,1\}^{\mathbb{N}}$ une application, et notons $f(n)=(a_{n,0},a_{n,1},a_{n,2},\dots)$ . Définissons la suite $b$ par $b_{n}=1-a_{n,n}$ . Pour chaque $n$ , les suites $b$ et $f(n)$ diffèrent au rang $n$ , donc $b\neq f(n)$ . Aucune application n’est surjective : l’ensemble n’est pas dénombrable. C’est l’argument diagonal dans sa forme la plus nue — pas de virgule, pas de chiffre, une seule soustraction.

(h) $\mathcal{P}(\mathbb{N})$ . Le théorème de Cantor s’applique directement : aucune application de $\mathbb{N}$ vers $\mathcal{P}(\mathbb{N})$ n’est surjective. On peut aussi invoquer la bijection avec (e), établie au paragraphe suivant.

(j) Les irrationnels. Si $\mathbb{R}\setminus\mathbb{Q}$ était dénombrable, alors $\mathbb{R}=\mathbb{Q}\cup(\mathbb{R}\setminus\mathbb{Q})$ serait une réunion de deux ensembles dénombrables, donc dénombrable. Or il ne l’est pas.

3. L’adjectif qui change tout, et l’application indicatrice

Réponse à la question 2. Une partie finie de $\mathbb{N}$ se décrit par une quantité finie d’information : la liste de ses éléments, qui tient dans un entier. Une partie quelconque exige, pour être décrite, une réponse par oui ou par non pour chaque entier — une infinité de bits. La différence entre (d) et (h) n’est donc pas une question de taille, c’est une question de description finie, et c’est la même remarque qui expliquait, dans l’article sur les fonctions, que presque aucune fonction n’admet de formule.

Réponse à la question 3. L’application qui fait le travail est l’indicatrice : à une partie $A\subseteq\mathbb{N}$ on associe la suite $\mathbf{1}_{A}$ définie par $\mathbf{1}_{A}(n)=1$ si $n\in A$ et $0$ sinon. Elle est bijective, et son inverse est explicite : à une suite $s$ on associe $\{n\in\mathbb{N}\mid s(n)=1\}$ . Les deux applications sont réciproques l’une de l’autre, ce qui se vérifie en une ligne dans chaque sens. Une partie et sa suite de bits sont deux écritures du même objet.

4. La question 4, et l’axiome caché

Une réunion finie d’ensembles dénombrables est dénombrable : on choisit une énumération pour chacun — ils sont en nombre fini, donc ces choix se font un par un, et une récurrence les légitime — puis on entrelace. Rien à signaler.

Une réunion dénombrable d’ensembles dénombrables est dénombrable — et c’est ici qu’il faut ouvrir l’œil. La démonstration range les éléments dans un tableau : la ligne $i$ contient l’énumération de $A_{i}$ , et l’on parcourt le tableau en diagonale, comme pour $\mathbb{N}\times\mathbb{N}$ . L’endroit fautif est la première phrase : « la ligne $i$ contient l’énumération de $A_{i}$ ». Chaque $A_{i}$ admet une infinité d’énumérations, et aucune n’est distinguée ; il faut donc en choisir une pour chaque $i$ , c’est-à-dire effectuer une infinité de choix simultanés. Les huit axiomes ne le permettent pas.

Ce principe supplémentaire s’appelle l’axiome du choix dénombrable, et l’énoncé lui est réellement nécessaire : on sait construire des univers de la théorie des ensembles, satisfaisant les huit axiomes, dans lesquels $\mathbb{R}$ lui-même est une réunion dénombrable d’ensembles dénombrables. Le contraste avec la démonstration menée pour $\mathbb{Q}$ est éclairant : là, on ne choisissait rien, on prenait le plus petit indice, et $\mathbb{N}$ offre toujours ce service. C’est aussi pourquoi les cas (f) et (g) ci-dessus sont irréprochables : les énumérations y sont données par des formules, non par des choix.

5. La question 5, première moitié

Un ensemble non dénombrable ne peut pas être inclus dans un ensemble dénombrable, puisque toute partie d’un ensemble dénombrable est finie ou dénombrable. Quant à savoir si deux ensembles non dénombrables ont le même nombre d’éléments, la réponse est non, et le théorème de Cantor la fournit : $\mathbb{R}$ et $\mathcal{P}(\mathbb{R})$ sont tous deux non dénombrables, et il n’existe aucune bijection entre eux. « Non dénombrable » n’est donc pas un cardinal : c’est une négation, et elle recouvre une infinité de tailles différentes.

6. L’hypothèse du continu

Reste la question précise, celle que Cantor a posée en 1878 et qui a occupé ses dernières années.

Hypothèse du continu. Toute partie infinie de $\mathbb{R}$ est soit dénombrable, soit en bijection avec $\mathbb{R}$ . Autrement dit, il n’existe aucun ensemble dont le nombre d’éléments soit strictement compris entre celui de $\mathbb{N}$ et celui de $\mathbb{R}$ .

Elle figurait en tête de la liste des vingt-trois problèmes que Hilbert proposa aux mathématiciens en 1900. La réponse est venue en deux temps, et elle n’est ni oui ni non.

Gödel, 1938. Si la théorie des ensembles est cohérente, elle le reste quand on lui ajoute l’hypothèse du continu. On ne peut donc pas la réfuter.
Cohen, 1963. Si la théorie des ensembles est cohérente, elle le reste quand on lui ajoute la négation de l’hypothèse du continu. On ne peut donc pas la démontrer. Ce travail, qui inaugure la méthode du forcing, lui a valu la médaille Fields en 1966.

L’hypothèse du continu est donc indépendante des axiomes. Il faut peser le mot : ce n’est pas qu’on ignore la réponse, c’est que la question n’en a pas, dans ce cadre. Le parallèle avec la géométrie est exact, et il vaut mieux que n’importe quel commentaire : le postulat des parallèles est indépendant des autres axiomes d’Euclide, et il existe des géométries où il est vrai, d’autres où il est faux, toutes cohérentes. De la même manière, il existe des univers ensemblistes où l’hypothèse du continu est vraie, d’autres où elle est fausse. Une liste d’axiomes ne décrit pas un monde unique : elle délimite une famille de mondes.

7. Ce que le fil aura montré

Deux principes supplémentaires ont été rencontrés en chemin sans figurer parmi les huit axiomes : le choix dénombrable, au paragraphe 4, et l’hypothèse du continu, au paragraphe 6. Le premier est employé partout, souvent sans qu’on le dise ; le second n’est employé nulle part, et l’on ne peut pas trancher son cas. Le dernier article du fil, « L’axiome du choix et le lemme de Zorn », examine le premier pour lui-même : ce qu’il autorise, ce qu’il coûte, et pourquoi il continue de déranger.

Les huit axiomes de Zermelo et Fraenkel, les constructions de $\mathbb{N}$ , $\mathbb{Z}$ , $\mathbb{Q}$ et $\mathbb{R}$ , et les ensembles finis occupent le chapitre 3 de Discours formel sur les mathématiques pour le secondaire, Volume I. Ni la dénombrabilité, ni l’hypothèse du continu n’y sont traitées : elles sont construites ici sur ces fondations.

Formalis Mathematica

Rigueur et formalisme au cœur de l’apprentissage et de l’enseignement des mathématiques

Corrigé, et l’hypothèse du continu

1. Les sept dénombrables

2. Les trois qui résistent

3. L’adjectif qui change tout, et l’application indicatrice

4. La question 4, et l’axiome caché

5. La question 5, première moitié

6. L’hypothèse du continu

7. Ce que le fil aura montré

Une réflexion sur “Corrigé, et l’hypothèse du continu”

Votre commentaire Annuler la réponse.

1. Les sept dénombrables

2. Les trois qui résistent

3. L’adjectif qui change tout, et l’application indicatrice

4. La question 4, et l’axiome caché

5. La question 5, première moitié

6. L’hypothèse du continu

7. Ce que le fil aura montré

Partagez :

Similaire

Une réflexion sur “Corrigé, et l’hypothèse du continu”

Votre commentaire Annuler la réponse.