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

thedudeminds_2016111302

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