ℕ × ℕ, ℤ et ℚ sont dénombrables

(i) Injectivité. Les puissances $2^p$ sont celles du nœud Sommes finies, dans $(\mathbb N, \cdot)$. Supposons $2^p(2q + 1) = 2^{p'}(2q' + 1)$ avec $p < p'$. Comme $2^{p'} = 2^p \cdot 2 \cdot 2^{p' - p - 1}$ (Sommes finies, (vi)), en simplifiant par $2^p \neq 0$ (Propriétés des opérations), $2q + 1 = 2 \cdot 2^{p' - p - 1}(2q' + 1)$, et l'unicité de la division euclidienne par $2$ serait contredite, le reste valant $1$ d'un côté et $0$ de l'autre. Le cas $p' < p$ est symétrique ; donc $p = p'$, puis $2q + 1 = 2q' + 1$ et $q = q'$.

Surjectivité. Montrons par récurrence forte que tout $m \geqslant 1$ s'écrit $2^p(2q + 1)$ : si $m$ est impair, $p = 0$ convient ; sinon $m = 2m'$ avec $1 \leqslant m' < m$, et l'écriture de $m'$ fournit celle de $m$. On l'applique à $m + 1$ pour tout $m \in \mathbb N$.

Enfin $\mathbb N^{k+1} = \mathbb N^k \times \mathbb N$ est équipotent à $\mathbb N \times \mathbb N$, donc à $\mathbb N$, par récurrence sur $k$.

(ii) L'application qui envoie $n \geqslant 0$ sur $2n$ et $-n < 0$ sur $2n - 1$ est une bijection de $\mathbb Z$ sur $\mathbb N$.

Tout rationnel s'écrit de façon unique $p/q$ avec $p \in \mathbb Z$, $q \geqslant 1$ et $p \wedge q = 1$ : c'est son écriture irréductible (Construction de ℚ).

On obtient une injection de $\mathbb Q$ dans $\mathbb Z \times \mathbb N$, donc dans $\mathbb N$ ; comme $\mathbb N \subset \mathbb Q$, le théorème de Cantor-Bernstein (Cantor-Bernstein) conclut. Enfin $\mathbb Q^k$ est équipotent à $\mathbb N^k$, donc dénombrable.