L’ensemble des rationnels est dénombrable !!

Eh oui, je viens de capter la nouvelle aujourd’hui en cours de stochastique. J’ai creusé un peu la question, et il s’avère que c’est bien vrai.

En fait, un ensemble est dit dénombrable si on peut lister ses éléments dans une suite de nombre indexés par des entiers. En termes de démonstration le truc est de prouver qu’il existe une bijection entre l’espace en question et l’ensemble N des entiers naturels.

Il se trouve que les éléments de Q peuvent tous être écrit sous forme de fraction. Il sont donc construit sur la base d’un couple (x,y) ∈ Z×N*, tel que x est le numérateur et y le dénominateur. Il se trouve qu’il existe bien une bijection entre N et Z, et une autre entre N et N×N. En composant ces deux bijection on trouve bien une bijection entre N et Z×N*, et par conséquent une bijection entre N et Q. L’ensemble des relationnels est donc bel et bien dénombrable.

Alors la question qui se pose (et que j’ai posé au prof d’ailleurs) est de savoir quel est le deuxième élément de Q. La question est en fait mal posée. Une question ayant plus de sens est de donner une suite de nombre rationnel pouvant être indexée par des entiers, et qui énumérerait tous les nombres rationnels. La réponse, l’arbre de Stern-Brocot.

Je dormirai certainement moins bête cette nuit. Que ça fait du bien