Exercice : dénombrable ou non ?

Deux techniques, et deux seulement, ont été mises en place : construire une énumération pour prouver qu’un ensemble est dénombrable, et construire un objet manquant pour prouver qu’il ne l’est pas. Les dix ensembles qui suivent se répartissent entre les deux camps, et l’intérêt de l’exercice tient à ce que l’intuition se trompe au moins deux fois : un ensemble qui paraît immense est dénombrable, un autre qui paraît maigre ne l’est pas.

L’article poursuit la série Aux fondations. Il met à l’épreuve « Dénombrable : ℕ, ℤ et ℚ ont le même nombre d’éléments » et « L’argument diagonal : ℝ n’est pas dénombrable », et il emploie les images directes et réciproques d’« Image directe, image réciproque ». La rédaction attendue est celle de Cinq raisonnements, une seule démonstration correcte : une bijection explicite, ou une contradiction explicite.

1. Les dix ensembles

(a) L’ensemble des entiers naturels pairs. — (b) $\mathbb{Z}\times\mathbb{Z}$ . — (c) $\mathbb{Q}\cap[0,1]$ . — (d) L’ensemble des parties finies de $\mathbb{N}$ . — (e) L’ensemble des suites à valeurs dans $\{0,1\}$ .

(f) L’ensemble des polynômes à coefficients entiers. — (g) L’ensemble des nombres algébriques, c’est-à-dire des réels qui annulent un polynôme non nul à coefficients entiers. — (h) $\mathcal{P}(\mathbb{N})$ . — (i) L’ensemble des intervalles ouverts bornés non vides de $\mathbb{R}$ dont les deux extrémités sont rationnelles. — (j) $\mathbb{R}\setminus\mathbb{Q}$ .

2. Les questions

Pour chacun des dix ensembles, dire s’il est fini, dénombrable ou non dénombrable. Une réponse « dénombrable » exige une bijection ou une injection explicite ; une réponse « non dénombrable » exige une contradiction construite, non une impression de taille.
Les ensembles (d) et (h) ne diffèrent que par un adjectif. Expliquer, sans calcul, pourquoi cet adjectif change tout, puis démontrer les deux résultats.
Montrer que (e) et (h) sont en bijection. Quelle application fait le travail ?
Une réunion finie d’ensembles dénombrables est-elle dénombrable ? Et une réunion dénombrable d’ensembles dénombrables ? Démontrer les deux. Puis relire la seconde démonstration et désigner l’endroit exact où l’on effectue une infinité de choix.
Un ensemble non dénombrable peut-il être inclus dans un ensemble dénombrable ? Deux ensembles non dénombrables ont-ils nécessairement le même nombre d’éléments ? Justifier la première réponse ; pour la seconde, dire précisément ce que l’on sait et ce qu’on ne sait pas.

3. Trois indications

Pour (d), chercher à coder une partie finie par un seul entier. Une partie finie $A\subseteq\mathbb{N}$ est entièrement décrite par la somme $\sum_{k\in A}2^{k}$ , et l’unicité de l’écriture en base deux fait le reste.
Pour (f), un polynôme de degré $n$ est un $(n+1)$ -uplet de coefficients. Il suffit donc de savoir dénombrer $\mathbb{Z}^{n+1}$ pour chaque $n$ , puis de réunir. Pour (g), remarquer qu’un polynôme non nul de degré $n$ a au plus $n$ racines réelles.
Pour (i), ne pas se laisser impressionner par le mot intervalle : un tel intervalle est entièrement déterminé par un couple, et l’on sait déjà dénombrer les couples de rationnels. C’est d’ailleurs cet ensemble qui sert, en topologie, à montrer que $\mathbb{R}$ possède une base dénombrable d’ouverts.

4. Ce que la question 4 dissimule

La question 4 n’est pas un exercice de routine, et sa seconde moitié est la plus instructive de toute la série. La démonstration habituelle consiste à énumérer chaque ensemble $A_{i}$ de la famille, puis à ranger tous les éléments dans un tableau à double entrée et à le parcourir en diagonale. Elle est correcte — à ceci près qu’énumérer chaque $A_{i}$ suppose qu’on ait choisi, pour chacun, une énumération parmi une infinité de possibles. Rien, dans les huit axiomes, ne permet de faire une infinité de choix simultanés.

L’énoncé reste vrai, mais il repose sur un principe supplémentaire, dont le corrigé dira le nom et dont le dernier article du fil examinera le statut. La comparaison avec la démonstration menée pour $\mathbb{Q}$ est instructive : là, aucun choix n’était fait, parce que $\mathbb{N}$ fournit gratuitement un procédé de sélection — prendre le plus petit indice. Ici, on ne dispose d’aucun procédé de ce genre.

5. Ce que l’exercice prépare

Les questions 1 à 3 fixent les deux techniques et montrent leur portée : on dénombre des objets qui semblent innombrables — tous les polynômes entiers, tous les nombres algébriques — et l’on échoue à dénombrer un ensemble de suites de zéros et de uns. La question 5 pose la seule question que les mathématiques ne savent pas trancher, et le corrigé dira pourquoi elle est indécidable plutôt que difficile.

Le corrigé paraîtra dans l’article « Corrigé, et l’hypothèse du continu ».

Les constructions de $\mathbb{N}$ , $\mathbb{Z}$ , $\mathbb{Q}$ et $\mathbb{R}$ , ainsi que les ensembles finis et leur cardinal, occupent le chapitre 3 de Discours formel sur les mathématiques pour le secondaire, Volume I. La dénombrabilité n’y est pas traitée ; les dix ensembles de cet exercice sont construits sur les notions qui s’y trouvent.

Formalis Mathematica

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

Exercice : dénombrable ou non ?

1. Les dix ensembles

2. Les questions

3. Trois indications

4. Ce que la question 4 dissimule

5. Ce que l’exercice prépare

Laisser un commentaire Annuler la réponse.

1. Les dix ensembles

2. Les questions

3. Trois indications

4. Ce que la question 4 dissimule

5. Ce que l’exercice prépare

Partagez :

Similaire

Laisser un commentaire Annuler la réponse.