Équipotence et ensembles dénombrables

Compter sans compter

Comment décider que deux ensembles ont « autant » d'éléments quand ils sont infinis ? Cantor propose en 1874 une réponse qui ne suppose aucun comptage : deux ensembles $E$ et $F$ sont équipotents s'il existe une bijection de $E$ sur $F$.

$$E \sim F \iff \exists\, f : E \to F \ \text{bijective}$$

Pour les ensembles finis, cela redonne l'égalité des cardinaux. Pour les ensembles infinis, cela réserve des surprises.

Ensembles dénombrables

Un ensemble est dénombrable s'il est équipotent à $\mathbb{N}$ : on peut donc numéroter ses éléments $x_0, x_1, x_2, \ldots$ sans en oublier ni en répéter. C'est le plus petit infini.

Le premier choc est que l'on peut retirer des éléments à un ensemble infini sans en changer la taille. L'application $n \mapsto n + 1$ est une bijection de $\mathbb{N}$ sur $\mathbb{N}^*$ : l'ensemble des entiers non nuls est aussi gros que celui de tous les entiers. C'est l'hôtel de Hilbert, complet mais qui accueille encore un client en décalant tout le monde d'une chambre.

Le catalogue des ensembles dénombrables

Ensemble	Bijection avec $\mathbb{N}$	Dénombrable ?
$\mathbb{N}^*$	$n \mapsto n + 1$	oui
entiers pairs	$n \mapsto 2n$	oui
$\mathbb{Z}$	alternance $0, 1, -1, 2, -2, \ldots$	oui
$\mathbb{N}^2$	parcours en diagonales	oui
$\mathbb{Q}$	voir la leçon suivante	oui
nombres algébriques	union dénombrable de parties finies	oui

Détaillons $\mathbb{Z}$. La bijection s'écrit explicitement

$$f(n) = \begin{cases} \dfrac{n}{2} & \text{si } n \text{ est pair} \\[2mm] -\dfrac{n+1}{2} & \text{si } n \text{ est impair} \end{cases}$$

qui énumère $0, -1, 1, -2, 2, \ldots$ et atteint chaque entier relatif exactement une fois.

Deux règles de stabilité

Elles servent en permanence, et découlent toutes deux du parcours en diagonales de $\mathbb{N}^2$ :

Une union dénombrable d'ensembles dénombrables est dénombrable. Un produit fini d'ensembles dénombrables est dénombrable.

En revanche, un produit infini d'ensembles à deux éléments ne l'est pas : l'ensemble $\{0, 1\}^{\mathbb{N}}$ des suites binaires est le premier ensemble non dénombrable que l'on rencontre, et c'est lui que la diagonale de Cantor mettra en défaut.

Piège classique

Croire qu'un ensemble « plus riche » est nécessairement plus gros. L'intuition dit que $\mathbb{Q}$ contient beaucoup plus d'éléments que $\mathbb{N}$, puisqu'il en existe une infinité entre deux entiers consécutifs. C'est faux au sens de l'équipotence : la densité et le cardinal sont deux notions indépendantes. L'ensemble $\mathbb{Q}$ est dense dans $\mathbb{R}$ et pourtant dénombrable.