Dénombrable : ℕ, ℤ et ℚ ont le même nombre d’éléments

L’ensemble des entiers naturels est contenu dans l’ensemble des entiers relatifs, qui lui-même est contenu dans l’ensemble des rationnels, et chaque inclusion est stricte : il manque les négatifs au premier, les fractions au second. L’intuition en conclut qu’il y a de plus en plus d’éléments. Elle se trompe trois fois. Ces trois ensembles ont exactement le même nombre d’éléments, et le démontrer ne demande que des applications bijectives — c’est-à-dire l’outil que notre livre sur les fondations des mathématiques emploie déjà pour compter les ensembles finis.

Cet article poursuit la série Aux fondations. Il emploie les bijections et les composées définies dans Fonction, application, correspondance, la construction de ℕ par les axiomes de Peano, et les quotients de Relations d’équivalence et passage au quotient, qui fabriquent ℤ et ℚ.

1. Ce que « autant d’éléments » veut dire

L’ouvrage sur les fondations des mathématiques définit les ensembles finis sans jamais compter. Pour $n\in\mathbb{N}^{\ast}$ , on note $I_{n}=\{m\in\mathbb{N}\mid 1\leq m\leq n\}$ , et $I_{0}=\emptyset$ ; un ensemble $E$ est fini s’il existe un $n$ et une bijection de $I_{n}$ vers $E$ , auquel cas $n$ est son cardinal. Le cardinal est bien défini parce qu’il existe une bijection de $I_{m}$ vers $I_{n}$ si et seulement si $m=n$ .

Ce qu’il faut voir, c’est que le nombre n’est pas prépondérant : la bijection l’est. Compter, c’est apparier ; le nombre n’est que le nom de la classe des ensembles appariables entre eux. Dès lors, une décision s’impose d’elle-même pour les ensembles infinis, et c’est celle de Cantor : deux ensembles ont le même nombre d’éléments lorsqu’il existe une bijection de l’un vers l’autre. Ce n’est pas un théorème, c’est une convention — mais la seule qui prolonge le cas fini sans rien changer.

Définition. Un ensemble est dénombrable lorsqu’il existe une bijection de $\mathbb{N}$ vers lui. Il revient au même de dire qu’on peut énumérer ses éléments en une suite $x_{0},x_{1},x_{2},\dots$ où chacun apparaît une fois et une seule.

La reformulation par les suites n’est pas un commentaire : c’est la même chose, puisqu’une suite est une application de $\mathbb{N}$ dans un ensemble. Énumérer sans répétition ni oubli, c’est exactement être injectif et surjectif.

2. Le fait qui heurte et qui définit l’infini

L’application $n\mapsto 2n$ est une bijection de $\mathbb{N}$ vers l’ensemble des entiers pairs : elle est injective car $2m=2n$ entraîne $m=n$ , et surjective sur les pairs par définition. Un ensemble infini peut donc être en bijection avec une partie stricte de lui-même, ce qu’un ensemble fini ne peut jamais faire — l’ouvrage le fait démontrer en exercice. Dedekind en a fait la définition même de l’infini, et l’on tient là le point où l’intuition doit céder : « la partie est plus petite que le tout » est un théorème du fini, pas une vérité générale.

Un lemme, qui servira deux fois et qu’il vaut mieux établir d’avance.

Lemme. Toute partie infinie de $\mathbb{N}$ est dénombrable.

Preuve. Soit $A\subseteq\mathbb{N}$ infinie. Toute partie non vide de $\mathbb{N}$ possède un plus petit élément ; on définit donc par récurrence $a_{0}=\min A$ , puis $a_{k+1}=\min\bigl(A\setminus\{a_{0},\dots,a_{k}\}\bigr)$ , ce qui a un sens car $A$ étant infinie, l’ensemble retranché n’est jamais vide. La suite obtenue est strictement croissante, donc injective. Elle est surjective : si un élément $a\in A$ n’était atteint par aucun $a_{k}$ , il serait à chaque étape un candidat au minimum, de sorte que $a_{k}<a$ pour tout $k$ ; or une suite d’entiers strictement croissante vérifie $a_{k}\geq k$ , ce qui donnerait $k<a$ pour tout entier $k$ . C’est impossible. $\quad\Box$

3. Les entiers relatifs

Il suffit d’énumérer $\mathbb{Z}$ en alternant : $0,-1,1,-2,2,\dots$ . Formellement, on pose

$\displaystyle f:\mathbb{N}\rightarrow\mathbb{Z},\qquad f(2k)=k,\qquad f(2k+1)=-k-1.$

Tout entier naturel s’écrit de manière unique $2k$ ou $2k+1$ , donc $f$ est bien une application. Elle est surjective : un entier relatif $z\geq 0$ est $f(2z)$ , et un entier $z<0$ est $f(-2z-1)$ . Elle est injective : les images des pairs sont exactement les entiers positifs ou nuls, celles des impairs les entiers strictement négatifs, et sur chacune des deux familles $f$ est visiblement injective. Donc $\mathbb{Z}$ est dénombrable.

4. Le produit ℕ × ℕ et la diagonale

C’est l’étape décisive, et la seule qui demande une idée. On range les couples $(m,n)$ selon la valeur de $m+n$ : il y a un couple avec $m+n=0$ , deux avec $m+n=1$ , trois avec $m+n=2$ , et ainsi de suite. En parcourant ces diagonales successives, on énumère tous les couples sans en oublier ni en répéter aucun. L’application obtenue s’écrit

$\displaystyle \varphi:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N},\qquad \varphi(m,n)=\frac{(m+n)(m+n+1)}{2}+n.$

Le premier terme compte les couples des diagonales précédentes — il y en a $1+2+\dots+(m+n)$ — et le second donne la place du couple sur sa propre diagonale. Cette lecture suffit à établir la bijectivité : pour un entier $N$ donné, il existe un unique $d$ tel que $\frac{d(d+1)}{2}\leq N<\frac{(d+1)(d+2)}{2}$ , et l’on retrouve alors $n=N-\frac{d(d+1)}{2}$ puis $m=d-n$ , de façon unique. Donc $\mathbb{N}\times\mathbb{N}$ est dénombrable, et par composition, le produit de deux ensembles dénombrables l’est aussi.

5. Les rationnels

Ici, la construction de $\mathbb{Q}$ rend le service qu’on attend d’elle. Un rationnel n’est pas une fraction : c’est une classe d’équivalence de couples, et l’ensemble $\mathbb{Q}=(\mathbb{Z}\times\mathbb{Z}^{\ast})/R$ vient avec une surjection canonique $\pi$ qui envoie le couple $(a,b)$ sur sa classe, c’est-à-dire sur le rationnel $a/b$ .

Or $\mathbb{Z}\times\mathbb{Z}^{\ast}$ est dénombrable, comme produit de deux ensembles dénombrables. Fixons-en une énumération $c_{0},c_{1},c_{2},\dots$ et posons, pour chaque rationnel $q$ , l’entier $\mu(q)$ égal au plus petit indice $k$ tel que $\pi(c_{k})=q$ . Cet indice existe puisque $\pi$ est surjective, et il est unique par définition du minimum — aucun choix arbitraire n’est fait. L’application $\mu:\mathbb{Q}\rightarrow\mathbb{N}$ est injective : deux rationnels distincts ont des antécédents distincts, donc des plus petits indices distincts. Son image est une partie infinie de $\mathbb{N}$ , puisque $\mathbb{Q}$ est infini, et le lemme du paragraphe 2 conclut. $\mathbb{Q}$ est dénombrable.

Le procédé vaut d’être retenu en général : l’image d’un ensemble dénombrable par une surjection est finie ou dénombrable, et la démonstration n’exige aucun axiome du choix, parce que $\mathbb{N}$ fournit gratuitement un procédé de sélection : prendre le plus petit.

6. Ce que ce résultat coûte à l’intuition

Trois habitudes de pensée y passent, et il vaut mieux les nommer.

L’inclusion stricte ne diminue pas le cardinal. $\mathbb{N}\subsetneq\mathbb{Z}\subsetneq\mathbb{Q}$ , et les trois sont équipotents.
La densité n’a rien à voir avec le nombre. Entre deux rationnels il y en a toujours un autre, alors que les entiers sont isolés : cela ne les distingue pas quantitativement.
Énumérer n’est pas ordonner. L’énumération de $\mathbb{Q}$ ne respecte pas l’ordre usuel, et ne le peut pas : dans une suite, chaque terme a un suivant immédiat, ce qu’aucun rationnel ne possède.

7. La question qui reste

Tout cela pourrait suggérer que l’infini est unique, et que tout ensemble infini est dénombrable pourvu qu’on trouve la bonne énumération. La question est légitime, et la réponse est non : $\mathbb{R}$ n’est pas dénombrable, et la démonstration tient en une page. Elle fait l’objet de l’article à paraître « L’argument diagonal : ℝ n’est pas dénombrable », où l’on retrouvera, sous une autre forme, le procédé qui avait déjà servi à réfuter la compréhension non restreinte : fabriquer un objet en le rendant différent de chacun de ceux qu’on prétendait avoir tous énumérés.

Les constructions de $\mathbb{N}$ , $\mathbb{Z}$ et $\mathbb{Q}$ occupent les sections 3.4 à 3.6 de Discours formel sur les mathématiques pour le secondaire, Volume I, et les ensembles finis, leur cardinal et leurs propriétés sont traités dans les exercices du même chapitre. Le mot dénombrable n’y figure pas : la notion est construite ici, sur la définition du cardinal fini par bijection.

Formalis Mathematica

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

Dénombrable : ℕ, ℤ et ℚ ont le même nombre d’éléments

1. Ce que « autant d’éléments » veut dire

2. Le fait qui heurte et qui définit l’infini

3. Les entiers relatifs

4. Le produit ℕ × ℕ et la diagonale

5. Les rationnels

6. Ce que ce résultat coûte à l’intuition

7. La question qui reste

Laisser un commentaire Annuler la réponse.

1. Ce que « autant d’éléments » veut dire

2. Le fait qui heurte et qui définit l’infini

3. Les entiers relatifs

4. Le produit ℕ × ℕ et la diagonale

5. Les rationnels

6. Ce que ce résultat coûte à l’intuition

7. La question qui reste

Partagez :

Similaire

Laisser un commentaire Annuler la réponse.