Lister les nombres rationnels

L’idée de Cantor pour montrer que l’ensemble des rationnels est dénombrable est bien connue. Il existe d’autres façons d’ordonner les fractions pour obtenir le même résultat.

Georg Cantor a établi que l’ensemble des nombres rationnels, ceux que l’on peut écrire sous la forme de fractions d’entiers, est dénombrable, tout comme l’ensemble des nombres entiers naturels. Pour cela, parmi toutes les façons de les ordonner, il a imaginé une façon de ranger les nombres rationnels, ou plutôt leurs écritures fractionnaires.

La méthode trouvée par Cantor consiste à ranger les écritures fractionnaires comme s’il s’agissait des couples de coordonnées des points à coordonnées entières d’un quart de plan. On associe par exemple le point de coordonnées (4 ; 3) à la fraction 4 / 3.

Cantor propose ensuite une façon de parcourir cet ensemble de points qui permet de les lister tous : 1 / 1, 2 / 1, 1 / 2, 1 / 3, 2 / 2, 3 / 1, 4 / 1, 3 / 2, 2 / 3, 1 / 4, 1 / 5… en suivant les flèches du diagramme.

On peut donc numéroter ces points, ce qui revient à construire une bijection entre les entiers naturels et les écritures de fractions d’entiers. Plusieurs écritures fractionnaires représentent cependant le même nombre rationnel : 1 / 2 = 2 / 4 = 3 / 6 = …

On prouve ainsi que l’ensemble des nombres rationnels strictement positifs est un ensemble dénombrable. On prouverait que la propriété est vraie pour l’ensemble de tous les rationnels en ajoutant 0 au diagramme et en faisant suivre chaque fraction par son opposé : 0, 1 / 1, – 1 / 1, 2 / 1, – 2 / 1, 1 / 2, – 1 / 2…

On peut imaginer bien d’autres façons de ranger les nombres rationnels. En voici une, publiée en 2000 par les mathématiciens américains Neil Calkin et Herbert Wilf. Celle-ci a l’avantage d’« éviter les doublons », c’est-à-dire de ne pas lister les écritures différentes d’un même nombre rationnel.

Les deux chercheurs rangent les fractions dans un arbre. Chaque nombre rationnel de l’arbre engendre à gauche un nombre rationnel ayant le même numérateur que son nombre géniteur et, pour dénominateur, la somme des deux nombres de la fraction qui l’engendre.

À droite, chaque nombre rationnel engendre un nombre ayant le même dénominateur que son nombre géniteur et, pour numérateur, la somme des deux nombres de la fraction qui l’engendre.

À partir de cet arbre, on peut lister les nombres rationnels en le lisant ligne horizontale après ligne horizontale, de gauche à droite :

1 / 1, 1 / 2, 2 / 1, 1 / 3, 3 / 2, 2 / 3, 3 / 1, 1 / 4, 4 / 3, 3 / 5, 5 / 1, 1 / 5…