Bijection entre entiers et rationnels,

non bijection entre entiers et réels

L’ensemble des rationnels, , est constitué des nombres de la forme avec p entier et q entier non nul ; pour créer une bijection de vers il faut donc fabriquer une liste numérotée des éléments de telle qu’à tout rationnel on attribue sans ambiguïté un numéro et qu’à chaque numéro on puisse associer un unique rationnel.

Si on range les rationnels de la manière suivante :

0, 1,

où en partant d’un nombre (par exemple 4) le numérateur descend d’un cran et le dénominateur augmente de un cran à chaque fois on est sûr de retrouver tous les rationnels (on élimine au passage ceux qui sont déjà dans la liste) ; la séquence suivante serait qui se réduit à . On obtient bien la bijection cherchée (la difficulté est quand même de trouver la fraction connaissant son rang…).

Un des résultats les plus profonds de Cantor fut alors de montrer que toute réunion dénombrable d’ensembles dénombrables est un ensemble dénombrable ; on procède comme précédemment : supposons que tous ces ensembles numérotés soient rangés de la manière suivante :

il suffit alors de les prendre comme précédemment par diagonales successives :

pour obtenir une liste numérotable.

Considérons maintenant les nombres rationnels compris entre 0 et 1 écrits sous forme décimale binaire : par exemple que l’on met sous la forme

(si on fait la limite de

quand n tend vers l’infini on a

)

et mettons les sous forme de tableau comme précédemment (pas rangés) :

on a alors une infinité dénombrable de tels nombres, eux mêmes composés d’une infinité dénombrable de 0 ou de 1.

Construisons alors le nombre suivant : où vaut 0 si le premier chiffre de la première ligne vaut 1, vaut 1 si ce chiffre vaut 0, vaut 0 si le deuxième chiffre de la deuxième ligne vaut 1, 1 s’il vaut 0, etc. On construit alors un nombre qui est différent de tous les nombres du tableau et ne peut donc être numéroté. Le nombre de points du segment [0, 1] n’est donc pas dénombrable et à plus forte raison (par exemple la fonction est bijective de [0, 1[ vers , ce qui suffit à prouver que ⁺ a même nombre d’éléments que [0, 1[)

Cantor disait qu’ « il le voyait mais qu’il ne le croyait pas » ! On comprend que ces résultats aient soulevé des discussions enflammées sur la constructibilité ou non de tels nombres.