Les cardinaux infinis

Combien y a-t-il d'entiers naturels, de rationnels, de réels ? Une infinité bien sûr. Mais l'infinité des réels est plus grande que l'infinité des rationnels. Pour donner un sens à cette affirmation, il faut d'abord définir ce qu'est un ensemble dénombrable.

Définition 12   Un ensemble infini est dit dénombrable s'il existe une application injective de cet ensemble vers $\mathbb{N}$.

Il peut paraître paradoxal que $\mathbb{Q}$ soit dénombrable. C'est pourtant le cas, car il existe une application injective de $\mathbb{Q}$ vers $\mathbb{Z}\times \mathbb{N}$ (à un rationnel $p/q$ on associe le couple $(p,q)$), et une application bijective de $\mathbb{Z}\times \mathbb{N}$ dans $\mathbb{N}$ : on compte les éléments de $\mathbb{Z}\times \mathbb{N}$, en commençant par $(0,0)$, puis $(1,0), (0,1), (-1,0)$, puis $(2,0), (1,1), (0,2),$ $(-1,1), (-2,0)$, ...  Plus généralement, on démontre que le produit et la réunion de deux ensembles dénombrables sont eux-mêmes dénombrables.

Théorème 4   L'ensemble des réels n'est pas dénombrable.

Démonstration : Nous allons démontrer par l'absurde que l'intervalle $[0,1]$ n'est pas dénombrable. Supposons que l'on puisse compter les éléments de $[0,1]$, donc les mettre en bijection avec $\mathbb{N}$. Nous aurions $[0,1]=\{ x_n ,\;n\in\mathbb{N}\}$. À l'élément $x_n$, nous associons un développement décimal :

$$x_n = 0.a_{n,1}a_{n,2}a_{n,3}\ldots\;,$$

où les $a_{n,k}$ sont des entiers compris entre 0 et $9$. Pour tout $n$, fixons $b_n\in \{1,\ldots,8\}$, tel que $b_n\neq a_{n,n}$. Considérons le réel $x$ dont le développement décimal est

$$x = 0.b_1b_2b_3\ldots$$

Ce réel est différent de $x_n$ pour tout $n$, par construction. Il n'a donc pas pu être compté. (Ce principe de démonstration s'appelle le procédé diagonal de Cantor).$\square$

Il y a plus de réels que de rationnels, et donc plus d'irrationnels que de rationnels. Parmi les irrationnels, on distingue ceux qui sont solutions d'une équation polynomiale à coefficients entiers, comme $\sqrt{2}$ : on les appelle les nombres algébriques. Ils semblent former une grosse masse. Pourtant il n'y a pas plus de polynômes à coefficients entiers que d'entiers : l'ensemble des nombres algébriques est lui aussi dénombrable. Les nombres qui ne sont pas algébriques (on les appelle «transcendants») forment l'essentiel des réels. Pourtant il est extrêmement difficile de démontrer qu'un réel particulier est transcendant. C'est une des victoires du XIX^e siècle que de l'avoir fait pour $\pi$ et $\mathrm{e}$. Existe-t-il des ensembles «intermédiaires»  entre $\mathbb{N}$ et $\mathbb{R}$, qui seraient non dénombrables, sans pourtant être en bijection avec $\mathbb{R}$ ? C'est le premier des 23 problèmes posés par Hilbert en 1900. On a longtemps essayé d'en construire, ou de démontrer qu'il n'en existe pas, avant de s'apercevoir finalement que c'est une assertion indécidable : on peut la supposer vraie, ou bien fausse, sans jamais aboutir à une contradiction. Elle s'appelle «l'hypothèse du continu».