Paradoxal...

Ce qui suit est un classique amusant de la théorie des ensembles, connu sous le nom de paradoxe de Berry.

Soit E l'ensemble des entiers naturels que l'on peut définir (sous-entendu de manière non ambiguë) à l'aide d'une phrase française d'au plus 100 lettres.

Ceci a-t-il bien un sens ? Autrement dit, cet ensemble E est-il correctement défini ?

Supposons que ce soit le cas. Le nombre de phrases (ayant un sens ou pas, peu importe) que l'on peut former avec 100 lettres est nécessairement fini. En effet, ces phrases sont au nombre de 26¹⁰⁰+26⁹⁹+26⁹⁸+...+26²+26. En effet, j'ajoute le nombre de phrases constituées d'exactement 100 lettres (26 possibilités pour chacune de ces lettres), à celles contenant exactement 99 lettres, puis 98, etc. jusqu'aux « phrases » ne contenant qu'une lettre (26 possibilités pour cette unique lettre).¹

Bref, c'est un très grand nombre, mais c'est fini. En particulier, E est un sous-ensemble fini de l'ensemble N des entiers naturels, le complémentaire de E dans N est donc non vide (puisque N est infini) et contient donc un plus petit élément n (propriété fondamentale des entiers naturels : toute partie non vide de N admet un plus petit élément).

J'insiste, ce n appartient au complémentaire de E dans N, il n'appartient donc pas à E.

Ainsi, par définition de E, « n est le plus petit entier naturel qu'on ne peut décrire avec cent lettres ».

Or, ce que je viens d'écrire entre guillemets est une phrase de moins de 100 lettres définissant n. Ce n appartient donc à E. Contradiction !

Alors, où se trouve le problème dans ce raisonnement ? Donnez votre réponse dans les commentaires ;)

Des présentations remarquables de clarté sur la théorie des ensembles, sujet difficile s'il en est, et ses derniers développements (au sujet de la fameuse hypothèse du continu notamment) sont disponibles sur la page personnelle de Patrick Dehornoy.

---

¹ En réalité il faudrait aussi tenir compte de la ponctuation, des espaces, des accents... Mais ça ne change pas fondamentalement le raisonnement.