Paradoxe de Berry
# Paradoxe de Berry

Le paradoxe de Berry a été formulé par Bertrand Russell en 1906. On le trouve dans un article, paru en français cette même année, de la Revue de métaphysique et de morale. Russell introduit, dans une discussion à propos du paradoxe de Richard, le « plus petit entier non nommable en moins de dix-huit syllabes qui paraît être ainsi nommé en dix-sept syllabes », et attribue cette définition paradoxale à un bibliothécaire londonien, G. G. Berry.

Toujours selon Russell, c'est une simplification, qui « a le mérite de ne pas dépasser les nombres finis », du paradoxe du « plus petit ordinal indéfinissable qui semble défini par la phrase même qui annonce qu'il est indéfinissable » (forme probablement due à Russell lui-même). Ces énoncés sont repris dans l'article de Russell de 1908 sur la théorie des types.

## Énoncé

   « Le plus petit entier naturel non descriptible par une expression de quinze mots ou moins. »

Ce nombre appartient-il à l'ensemble des entiers naturels descriptibles par une expression de quinze mots ou moins ?

## Explications

Les entiers naturels peuvent être décrits par des énoncés (en français) tels que : « dix puissance cent » ou « le plus grand nombre premier connu au vingtième siècle ». Comme le vocabulaire disponible est fini (mettons qu'il y ait 300 000 mots en français), les énoncés de N mots ne peuvent décrire plus de $300000^{N}$ entiers (et en fait beaucoup moins ; la plupart des « phrases » ne voulant en fait rien dire, ou ne parlant pas d'entiers).

L'ensemble des « nombres entiers naturels descriptibles par une expression de quinze mots ou moins » est donc fini ; aussi existe-t-il forcément de nombreux entiers hors de cet ensemble. Le plus petit d'entre eux est donc « le plus petit entier naturel non descriptible par une expression de quinze mots ou moins ». Mais justement, cet énoncé qui le décrit parfaitement, ne comporte que quinze mots.

On pourrait aussi proposer de créer des mots nouveaux, mais ils ne sont pas en nombre infini si on pose une limite au nombre de lettres : il suffirait de réécrire l'énoncé avec une limite de lettres et non de mots pour contourner cet argument.

Ce paradoxe est très proche du paradoxe de Richard (il est d'ailleurs parfois donné sous ce nom), dont il peut être considéré comme une variante finie. Poincaré, qui tenait à voir la raison des paradoxes logiques dans un maniement sans précautions de l'infini, disait, à propos du paradoxe de Berry qui justement n'utilise que des notions finies, « ils [certains logiciens] ont eux-mêmes tendu le piège où ils se sont amusés à tomber, et même ils ont été obligés de faire bien attention pour ne pas tomber à côté du piège ».

On peut considérer également qu'il met en jeu le même genre de questions que certaines formes du paradoxe du menteur (la phrase qui dit d'elle-même qu'elle est fausse). On le résout habituellement en formalisant le langage, ici celui qui permet de décrire les entiers, et en le distinguant du métalangage dans lequel est énoncée la phrase de Berry qui n'est alors plus paradoxale (voir également l'article sur le paradoxe de Richard, ainsi que la traduction de ce paradoxe sous forme d'une preuve de ce que la complexité de Kolmogorov n'est pas calculable).

