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 »,

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

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit exceeded. Please complete the captcha once again.