Qu'est-ce que « Équipotence, dénombrabilité » ?

Exemple 1.7 (Une fonction de couplage, calculée)

La bijection $(p, q) \mapsto 2^p(2q + 1) - 1$ de la démonstration mérite d’être vue à l’œuvre. Ses premières valeurs :

La ligne $p$ regroupe les entiers $n$ pour lesquels $n + 1$ est exactement divisible par $2^p$ : tout entier naturel apparaît exactement une fois. Le décodage est aussi explicite que le codage : pour $n = 43$, on factorise $n + 1 = 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$, d’où $(p, q) = (2, 5)$. L’idée à retenir : les démonstrations de dénombrabilité sont souvent des algorithmes déguisés — ici, « mettre les puissances de deux en facteur ».

Exemple 1.8 (Les nombres algébriques sont dénombrables)

Un nombre complexe est algébrique lorsqu’il annule un polynôme non nul à coefficients rationnels. L’ensemble $\overline\Q$ des nombres algébriques est dénombrable : les polynômes de degré $\leq d$ sur $\Q$ s’injectent dans $\Q^{d+1}$, un produit fini d’ensembles dénombrables (Proposition 1.6 (2)) ; l’union sur $d$ énumère les polynômes rationnels non nuls en $P_0, P_1, P_2, \dots$ ; chaque $P_k$ a un nombre fini de racines ; et

est une union dénombrable d’ensembles finis (Proposition 1.6 (3)), infinie car elle contient $\Q$. Combiné avec la non-dénombrabilité de $\R$ (Théorème 1.9 ci-dessous), cela prouve — sans en exhiber un seul — que les nombres transcendants existent et forment une majorité non dénombrable : l’argument de comptage de Cantor de 1874, l’existence par la seule cardinalité.

Exemple 1.11

$\intoo{0}{1}$ et $\intcc{0}{1}$ sont équipotents : l’identité injecte dans un sens, $x \mapsto \frac{x + 1}{3}$ dans l’autre ; le théorème fabrique la bijection (nécessairement discontinue). De même $\R$, $\intoo{0}{1}$ (via des bijections de type $\tanh$) et $\mathcal{P}(\N)$ (développements binaires, Exercice 1.3) sont tous équipotents : « la puissance du continu ».