Ensembles dénombrables

Le caractère dénombrable d’un ensemble est une sorte d’équivalent de sa taille, car pour les ensembles infinis on ne peut pas parler de nombre d’éléments : ce nombre d’éléments est, de façon inattendue, … infini. La taille d’un ensemble s’appelle aussi son cardinal.

Taille d’un ensemble infini

Déterminer la taille d’un ensemble fini est simple : on compte le nombre d’éléments. L’ensemble M = {a ; b ; c ; d ; e} a donc pour taille 5, ce qu’on écrit |M| = 5.

Pour les ensembles infinis, la situation est nettement plus compliquée. Comment comparer la taille d’ensembles infinis ? Est-ce seulement possible, ou bien tous les ensembles infinis ont-ils « la même taille » ?

Prenons pour exemple l’ensemble des entiers naturels non nuls et l’ensemble des nombres pairs non nuls. Nous avons ainsi les ensembles ℕ^* = {1 ; 2 ; 3 ; 4 ; 5 ; 6 ; …} et S = {2 ; 4 ; 6 ; …}. On aurait envie de dire que l’ensemble des entiers naturels est plus grand que l’ensemble des nombres pairs, car les entiers naturels contiennent tous les nombres pairs et, en plus, d’autres éléments : les nombres impairs.

Nous pourrions donc écrire S ⊊ ℕ^* : l’ensemble S est un sous-ensemble strict de l’ensemble ℕ^*. Et nous pourrions dire que, si S ⊊ ℕ^*, l’ensemble ℕ^* est plus grand : il contient quand même plus d’éléments que l’ensemble S.

Une des raisons pour lesquelles on ne peut pas mesurer les ensembles avec la relation d’inclusion, c’est que des ensembles peuvent avoir des tailles différentes sans qu’aucun des deux ne soit un sous-ensemble de l’autre. On peut le montrer même avec des ensembles finis : A = {1 ; 3 ; 4 ; 9} et B = {b ; u ; r ; z ; m}. On a |A| = 4 et |B| = 5. L’ensemble B est plus grand que l’ensemble A, et pourtant A ⊂ B est faux. Pour les ensembles infinis, on le voit avec les nombres pairs et les nombres impairs : aucun des deux ensembles n’est un sous-ensemble de l’autre.

La relation d’inclusion n’est donc pas un bon candidat pour décider si un ensemble est plus grand qu’un autre.

Bijection

Essayons une autre approche. Nous avons deux ensembles, A et B. Nous pouvons dire qu’ils ont la même taille s’il existe une bijection entre eux. Qu’est-ce que cela signifie ? Nous prenons un élément de l’ensemble A, un élément de l’ensemble B et nous formons le couple (a ; b). Nous retirons ces éléments des ensembles et nous continuons. Si nous parvenons à « vider » les deux ensembles, nous avons trouvé une bijection.

Exemple avec des ensembles finis : A = {a ; b ; c} et B = {1 ; 2 ; 3}. Le premier couple pourrait être (a ; 1), le suivant (b ; 2) et enfin (c ; 3). Nous avons épuisé tous les éléments des deux ensembles, nous avons trouvé une bijection. L’important est que ce n’est pas la seule bijection. Celle-ci est valable aussi : (a ; 3), (b ; 1), (c ; 2).

Pour les ensembles infinis, c’est déjà un peu plus intéressant. Essayons avec les entiers naturels impairs et pairs. Intuitivement, on sent qu’il devrait y en avoir autant. Essayons. Prenons le premier nombre impair et associons-le au premier nombre pair : (1 ; 2). Puis le deuxième impair et le deuxième pair : (3 ; 4). Etc. Nous obtenons ainsi les couples : (1 ; 2), (3 ; 4), (5 ; 6), (7 ; 8), … Nous pourrions écrire que chaque nombre impair l est associé au nombre pair l + 1 et que chaque nombre pair s est l’image du nombre impair s − 1. Pour chaque nombre impair et pour chaque nombre pair, il existe donc un couple qui contient ce nombre. Les ensembles des nombres impairs et des nombres pairs ont donc la même taille.

Nombres pairs et entiers naturels

Essayons maintenant le même procédé et comparons l’ensemble des entiers naturels et celui des nombres pairs. Nous avons les ensembles ℕ^* = {1 ; 2 ; 3 ; 4 ; 5 ; 6 ; …} et S = {2 ; 4 ; 6 ; …}. Intuitivement, nous nous attendons à ce que l’ensemble des entiers naturels soit plus grand.

Essayons pourtant de trouver cette bijection. Nous pouvons dire que chaque entier naturel n est associé à son double, 2n. Nous obtenons ainsi les couples (1 ; 2), (2 ; 4), (3 ; 6), (4 ; 8), (5 ; 10), … Pour chaque entier naturel n, nous avons donc un couple (n ; 2n) et pour chaque nombre pair s, nous avons un couple (s/2 ; s). Nous avons trouvé une bijection : l’ensemble des nombres pairs et l’ensemble des entiers naturels ont donc la même taille, ils ont le même cardinal.

Cela peut sembler déroutant, car les entiers naturels contiennent quand même plus d’éléments que les nombres pairs. Les entiers naturels contiennent tous les nombres pairs et, en plus, tous les nombres impairs. Pourtant, nous savons trouver une bijection, donc les deux ensembles ont la même taille.

Comparaison avec les entiers naturels

Les entiers naturels donnent en fait la plus petite taille possible d’un ensemble infini. Savoir si un autre ensemble a la même taille que l’ensemble des entiers naturels est souvent assez facile : il suffit de trouver une bijection avec les entiers naturels, ce qui revient en pratique à pouvoir numéroter les éléments de notre ensemble M, c’est-à-dire à les ordonner.

Autrement dit, si l’on sait ranger les éléments de l’ensemble de sorte à décider quel élément est le premier, lequel est le deuxième, le troisième, le quatrième, le dixième, etc., l’ensemble a la même taille que ℕ. On dit alors qu’il est dénombrable.

On voit facilement que les entiers naturels pairs et impairs sont dénombrables, car nous savons déterminer le premier, le deuxième, le troisième, etc. nombre pair ou impair. Et les entiers relatifs pairs ? C’est-à-dire l’ensemble S = {… ; −4 ; −2 ; 0 ; 2 ; 4 ; …}. Savons-nous les ordonner ? Oui : il suffit de prendre le même ordre que tout à l’heure et d’écrire, juste après chaque nombre pair strictement positif, son opposé : S = {0 ; 2 ; −2 ; 4 ; −4 ; 6 ; −6 ; …}. De même pour les entiers relatifs, par exemple.

Taille de l’ensemble des rationnels

Un exemple plus intéressant est celui des nombres rationnels, les fractions. Savons-nous les ordonner ? Oui, mais ce sera un peu plus compliqué. Construisons un tableau qui a une infinité de lignes et de colonnes. Dans chaque case, il y aura une fraction. Dans la n-ième colonne et la m-ième ligne, nous mettons la fraction n/m. Ainsi, dans la 1re colonne et la 2e ligne, nous avons $\frac{1}{2}$, et dans la troisième colonne et la quatrième ligne, nous avons 3/4.

$$\begin{array}{ccccc}1/1& 2/1& 3/1& 4/1& \dots \\ 1/2& 2/2& 3/2& 4/2& \dots \\ 1/3& 2/3& 3/3& 4/3& \dots \\ 1/4& 2/4& 3/4& 4/4& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}$$

Comment maintenant ranger ces nombres, les numéroter ? Nous ne pouvons pas les numéroter ligne par ligne ni colonne par colonne, car nous nous noierions aussitôt dans la ligne ou la colonne en question. Prenons plutôt les nombres le long des diagonales : (première diagonale :) 1/1, (deuxième diagonale :) 2/1 ; 1/2, (troisième diagonale :) 3/1 ; 2/2 ; 1/3, (quatrième diagonale :) 4/1 ; 3/2 ; 2/3 ; 1/4, … Il y a encore beaucoup de fractions en double, mais cela ne gêne pas. Ce qui gêne davantage, c’est qu’il n’y a pas de nombres négatifs. On le règle simplement : chaque fois que nous écrivons une fraction, nous plaçons juste après elle sa version négative. Et il manque alors encore le zéro au tout début. Et c’est tout : nous avons tous les nombres rationnels dans une suite.

Nous obtenons au total la suite : 0 ; 1/1 ; −1/1 ; 2/1 ; −2/1 ; 1/2 ; −1/2 ; 3/1 ; −3/1 ; 2/2 ; −2/2 ; 1/3 ; −1/3 ; …

Taille de l’ensemble des réels

Les nombres réels ont-ils la même taille que les entiers naturels ? La décision sera encore plus délicate que pour les nombres rationnels. Nous allons faire un raisonnement par l’absurde. Supposons que les nombres réels soient dénombrables et qu’il existe une bijection avec les entiers naturels. Supposons donc qu’on puisse les ordonner. Et admettons que le tableau suivant soit cet ordre :

$$\begin{array}{ccccccccc}0,& 3& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& 9& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& 3& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& 7& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& 7& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& 6& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& 0& \dots \\ \dots \end{array}$$

Le tableau contient les sept premiers nombres réels de notre ordre. Cet ordre peut évidemment être quelconque : les nombres ne sont pas forcément rangés par ordre croissant.

Par hypothèse, tous les nombres réels sont rangés dans ce tableau infini. (Le tableau est de nouveau infini, nous n’en montrons ici que les sept premières lignes.) Nous allons maintenant essayer de trouver ou de construire un nombre qui est réel mais ne figure pas dans ce tableau. Si nous en trouvons un, c’est une contradiction avec le fait que tous les nombres réels sont dans le tableau, et nous pourrons en conclure que l’ensemble des nombres réels n’est pas dénombrable.

Nous construisons ce nombre absent du tableau de la façon suivante :

$$\begin{array}{ccccccccc}0,& \boxed{\text{3}}& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& \boxed{\text{9}}& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& \boxed{\text{3}}& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& \boxed{\text{7}}& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& \boxed{\text{7}}& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& \boxed{\text{6}}& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& \boxed{\text{0}}& \dots \\ \dots \end{array}$$

Nous commençons par écrire 0,… C’est ainsi que notre nouveau nombre réel commencera. À la première décimale, nous mettrons un chiffre différent du premier chiffre du premier nombre réel de notre ordre (il est encadré dans le tableau). Là, il y a le chiffre 3, donc nous choisissons par exemple 1 et nous obtenons le nombre 0,1…

Continuons. À la deuxième place, nous mettrons un chiffre différent du deuxième chiffre du deuxième nombre réel. Là, il y a 9, donc par exemple 2. Nous obtenons le nombre 0,12… À la troisième place, nous mettrons un chiffre différent du troisième chiffre du troisième nombre réel. Là, il y a 3, donc nous choisissons par exemple 7. Nous obtenons 0,127…

Et ainsi de suite. À la n-ième position du nouveau nombre, il y aura toujours un chiffre différent du chiffre qui est à la n-ième position du n-ième nombre de notre ordre.

Qu’obtenons-nous ainsi ? Un nombre qui diffère de tous les nombres de notre ordre par au moins un chiffre. Prenons le dernier résultat provisoire : 0,127… Ce nombre diffère certainement du premier nombre de notre ordre au moins par le premier chiffre, puisque nous l’avons construit ainsi. Du deuxième nombre, il diffère au moins par le deuxième chiffre. Du troisième, par le troisième chiffre. En général, ce nouveau nombre diffère du nombre de l’ordre qui occupe la n-ième place au moins par le chiffre à la n-ième position.

Ce nombre nouvellement construit ne se trouve donc pas dans le tableau, qui devait représenter une bijection entre les entiers naturels et les nombres réels. Les nombres réels sont donc plus nombreux que les entiers naturels. L’ensemble des nombres réels n’est pas dénombrable, il est non dénombrable.

Pour aller plus loin

• Are there more odd or even numbers?