Archives du mot-clef ensemble dénombrable

Pourquoi nous ne connaîtrons jamais vraiment les nombres réels

Introduction

L’histoire des mathématiques est jonchée de construction de nouveaux ensembles de nombres afin de pouvoir effectuer des calculs qui n’étaient pas possible auparavant.

À partir des entiers naturels (0,1,2,3,…), les entiers relatifs (…,-3,-2,-1,0,1,2,3,…) sont apparus, afin de pouvoir rendre compte de phénomènes comme les dettes (le fameux découvert qui vous donne des sueurs froides, et fâche votre banquier) ou encore la température.

À partir des entiers relatifs, on a inventé les rationnels pour les problèmes de partages (comment partager 10 euros avec 3 personnes, source de tension au restaurant). Ce sont les fractions bien connues des collégiens (1/2, -3/77, etc…).

À partir des rationnels, la nécessité de nouveaux nombres est moins claire. Cependant, les grecs avaient déjà remarqué que la longueur de la diagonale d’un carré de longueur 1 (la fameuse racine de 2) ne peut pas s’exprimer comme un rationnel a/b (pour une démonstration, voir la fin de l’article). Les rationnels ne suffisent donc pas à décrire la réalité.

On a donc construit les nombres réels, et les mathématiciens sont contents (pas tout à fait, on a encore construit de nouveaux ensembles, notamment les nombres complexes). Pour faire simple, un réel se définit comme un nombre avec une infinité de chiffres après la virgule (qui peuvent être nuls). Même si la construction mathématique est beaucoup plus abstraite (un réel est une classe d’équivalence de suites de Cauchy rationnelles pour la relation d’équivalence « la différence tend vers 0 à l’infini », gloups !), cette vision des choses conviendra pour la suite.

Mais il est apparu que l’ensemble des nombres réels est extrêmement vaste, et contient des nombres monstrueux, non par leur taille, mais tout simplement parce que nous ne pouvons pas les calculer ! Et pire encore, ces nombres sont infiniment plus nombreux que les nombres calculables (dans un sens qui sera précisé plus loin)…

Ensembles dénombrables

La première référence d’ensemble infini dont nous disposons est l’ensemble des entiers naturels N, qui va nous servir de référence. Pour exprimer l’idée qu’un ensemble infini E à la même taille que N, on exige que l’on puisse faire correspondre à chaque élément de E un unique entier naturel. Autrement dit, que l’on peut lister les éléments de E, les classer dans un ordre précis (le premier, le deuxième, etc…). Mathématiquement, on dit que N et E sont en bijection. Si c’est le cas, E est dit dénombrable, le terme pour dire que E et N ont la même taille.

On peut se demander si l’ensemble Z des entiers relatifs est dénombrable. A priori non, car Z semble avoir une infinité d’éléments en plus (-1, -2, -3, etc…) par rapport à N, donc est plus gros. Cependant, on peut énumérer les éléments de Z de la manière suivante : 0 est le premier, 1 est le deuxième, -1 le troisième, 2 le quatrième, -2 le cinquième, etc… Ceci montre que les éléments de Z peuvent être énuméré, et donc que Z est dénombrable.

On peut ensuite se demander si l’ensemble Q des rationnels est dénombrable. A priori encore, non car cette fois-ci, entre chaque entier, on peut mettre une infinité de rationnels. Par exemple, entre 0 et 1 on peut mettre 1/2, 1/3, 1/4, etc… mais aussi 2/3, 4/5, etc… Mais il n’en est rien. On peut lister les rationnels. Je n’expose pas les détails de la démonstration, mais le graphique suivant me semble assez parlant :

irrationnels

Maintenant, si je vous demande si les nombres réels sont dénombrables, vous sentez le coup venir et vous allez me répondre oui. Mais la réponse est non. La démonstration est pour moi l’une des plus belles de toutes les mathématiques, vous la trouverez en fin d’article. Elle suit ce qu’on appelle l’argument de la diagonale de Cantor, le premier mathématicien à avoir exploré les concepts exposés ici.

L’ensemble des nombres réels est donc vraiment plus gros que l’ensemble des entiers naturels, des entiers relatifs et des rationnels.

Nombres calculables

Pour nous, nous dirons qu’un nombre réel est calculable s’il existe un algorithme permettant d’exhiber autant de chiffres après la virgule que nous le souhaitons. Un algorithme est un énoncé d’une suite d’opérations précises et fixées permettant de donner la réponse à un problème. Par exemple, vous connaissez (ou avez connu) l’algorithme permettant de calculer les décimales d’un rationnel, à travers la division, grande joie des écoliers. Ceci montre au passage que les rationnels sont calculables.

De nombreux réels utilisés en pratique sont calculables. Par exemple, pour calculer la racine de 2 on peut toujours prendre un entier, l’élever au carré puis essayer de corriger la différence avec 2 pour s’en rapprocher et itérer le résultat (vous trouverez un tel algorithme en fin d’article). De nombreux autres réels utiles, comme le nombre pi sont calculables.

Ce qui est remarquable, c’est que l’ensemble des nombres calculables est dénombrable ! En effet, un algorithme peut être exprimé dans un langage de programmation (par exemple le C++). Un langage de programmation s’exprime avec un nombre fini de caractère (pour l’exemple, disons 50), et un algorithme est un ensemble fini de caractères. L’ensemble des algorithmes possibles (qui contient l’ensemble des algorithmes permettant de calculer les réels) est donc la réunion de tous les algorithmes finis.

Plus précisément, pour une longueur n de caractères, l’ensemble A_n des algorithmes possibles a pour taille 50^n. L’ensemble des algorithmes possibles est donc la réunion des ensembles A_0, A_1, A_2, etc… Ce qui est remarquable, c’est que une réunion d’un nombre dénombrable de fois d’ensembles finis est encore dénombrable (pour une démonstration, voir en fin d’article). Ceci montre que les nombres calculables sont dénombrables.

Conclusion

L’ensemble des nombres réels n’étant pas dénombrable, alors que l’ensemble des nombres calculables l’est. Ceci montre qu’il existe des nombres non calculables, et même que ces nombres sont beaucoup plus nombreux que les nombres calculables. Il est donc vain de vouloir connaître précisément l’ensemble des nombres réels, ce qui fait que c’est un objet très compliqué… Bien souvent, les constructions mathématiques se révèlent plus riches que prévues.

Pour aller plus loin, je vous invite à lire les articles suivants :

Annexe: démonstrations

Vous pouvez retrouvez toutes les démonstrations dans ce document PDF.