Pourquoi les rationnels se numérotent

Numéroter les couples d'entiers

Le point de départ est l'énumération de $\mathbb{N}^2$ par diagonales successives. On parcourt d'abord les couples dont la somme des coordonnées vaut $0$, puis $1$, puis $2$, et ainsi de suite. Chaque diagonale ne contient qu'un nombre fini de couples, donc le parcours atteint tout couple en un temps fini.

Diagonale $i + j$	Couples parcourus	Rangs attribués
$0$	$(0,0)$	$0$
$1$	$(0,1)$, $(1,0)$	$1$, $2$
$2$	$(0,2)$, $(1,1)$, $(2,0)$	$3$, $4$, $5$
$3$	$(0,3)$, $(1,2)$, $(2,1)$, $(3,0)$	$6$ à $9$

La formule de couplage de Cantor donne le rang explicitement :

$$\pi(i, j) = \frac{(i + j)(i + j + 1)}{2} + i$$

C'est une bijection de $\mathbb{N}^2$ sur $\mathbb{N}$ : $\mathbb{N}^2$ est dénombrable.

$\mathbb{Q}$ est dénombrable

Tout rationnel strictement positif s'écrit de manière unique $\dfrac{p}{q}$ sous forme irréductible, avec $p$ et $q$ entiers strictement positifs premiers entre eux. L'application

$$\frac{p}{q} \longmapsto (p, q)$$

est donc injective de $\mathbb{Q}_+^*$ dans $\mathbb{N}^2$, qui est dénombrable. Une partie infinie d'un ensemble dénombrable étant dénombrable, $\mathbb{Q}_+^*$ l'est aussi.

On conclut en recollant les morceaux : $\mathbb{Q}$ est la réunion de $\mathbb{Q}_+^*$, de $\mathbb{Q}_-^*$ et de $\{0\}$, donc une réunion finie d'ensembles dénombrables — elle est dénombrable.

Une énumération concrète

On peut aussi énumérer les rationnels positifs par hauteur croissante, en appelant hauteur la somme $p + q$ de la forme irréductible, et en ordonnant à hauteur égale par numérateur croissant :

$$\frac{1}{1},\ \frac{1}{2},\ \frac{2}{1},\ \frac{1}{3},\ \frac{3}{1},\ \frac{1}{4},\ \frac{2}{3},\ \frac{3}{2},\ \frac{4}{1},\ \ldots$$

Les fractions non irréductibles, comme $\dfrac{2}{2}$, sont sautées pour éviter les répétitions. Chaque hauteur ne donnant qu'un nombre fini de fractions, tout rationnel finit par apparaître, une seule fois.

Les nombres algébriques aussi

Le même argument porte plus loin qu'on ne croit. Un nombre algébrique est racine d'un polynôme non nul à coefficients entiers. Or, pour un degré $n$ et une borne $H$ fixés, il n'existe qu'un nombre fini de polynômes à coefficients entiers majorés par $H$, chacun ayant au plus $n$ racines.

L'ensemble des nombres algébriques est donc une union dénombrable d'ensembles finis : il est dénombrable. Cette remarque, jointe au chapitre suivant, produira un résultat spectaculaire.

Piège classique

Proposer comme énumération de $\mathbb{Q}_+^*$ le parcours « d'abord tous les $\dfrac{1}{q}$, puis tous les $\dfrac{2}{q}$, et ainsi de suite ». Cette liste ne termine jamais la première ligne, donc n'atteint jamais $\dfrac{2}{1}$ : ce n'est pas une énumération. Une bonne bijection doit assigner à chaque élément un rang fini, ce que garantit le découpage en tranches finies — diagonales ou hauteurs.