Avertissement : dénombrabilité explicite

La dénombrabilité de $\mathbb{N}\times \mathbb{N}$ fait souvent l’objet de jolies preuves, comme celle-ci, une « preuve sans mot »,

En voici une autre plus explicite. On considère la fonction $g:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ telle que $$g(x,y)=2^x\cdot 3^y$$

On note que $g$ n’est pas surjective, parce qu’il existe des nombres $n\in \mathbb{N}$ dont la décomposition en facteurs premiers incluent des facteurs autres que $2$ ou $3$. Mais la fonction $g$ est néanmoins injective car le Théorème fondamental de l’arithmétique (coucou Euclide !) nous assure que chaque couple $(x,y)$ est associé par la fonction $g$ à un unique nombre naturel $2^x\cdot 3^y$. C’est suffisant pour montrer la dénombrabilité de $\mathbb{N}\times \mathbb{N}$ puisque $\mathbb{N}\times \mathbb{N}$ est en bijection avec un sous-ensemble de $\mathbb{N}$. Et comme un sous-ensemble d’un ensemble dénombrable est lui même dénombrable, $\mathbb{N}\times \mathbb{N}$ est dénombrable.

Références : Wikipedia : The Cantor pairing function assigns one natural number to each pair of natural numbers, image par Cronholm144

Croom, Fred H., Principles of Topology, 2016