Paradoxe des baies - Berry paradox

Le paradoxe de Berry est un autoréférentielle paradoxe résultant d'une expression comme « le plus petit entier positif non définissable dans moins de soixante lettres » (une phrase avec cinquante-sept lettres).

Bertrand Russell , le premier à discuter du paradoxe dans la presse, attribué à GG Berry (1867-1928), un junior bibliothécaire à Oxford de la bibliothèque Bodleian . Russell a appelé Berry "la seule personne à Oxford qui comprenait la logique mathématique".

Aperçu

Considérons l'expression :

"Le plus petit entier positif non définissable en moins de soixante lettres."

Comme il n'y a que vingt-six lettres dans l'alphabet anglais, il existe un nombre fini de phrases de moins de soixante lettres, et donc un nombre fini d'entiers positifs définis par des phrases de moins de soixante lettres. Comme il existe une infinité d'entiers positifs, cela signifie qu'il existe des entiers positifs qui ne peuvent pas être définis par des phrases de moins de soixante lettres. S'il y a des entiers positifs qui satisfont une propriété donnée, alors il y a un plus petit entier positif qui satisfasse cette propriété ; par conséquent, il existe un plus petit entier positif satisfaisant la propriété "non définissable en moins de soixante lettres". Il s'agit de l'entier auquel se réfère l'expression ci-dessus. Mais l'expression ci-dessus ne compte que cinquante-sept lettres, elle est donc définissable en moins de soixante lettres, et n'est pas le plus petit entier positif non définissable en moins de soixante lettres, et n'est pas définie par cette expression. C'est un paradoxe : il doit y avoir un entier défini par cette expression, mais comme l'expression est auto-contradictoire (tout entier qu'elle définit est définissable en moins de soixante lettres), il ne peut y avoir d'entier défini par elle.

Une autre analogie utile avec le paradoxe de Berry serait peut-être l'expression « sentiment indescriptible ». Si le sentiment est en effet indescriptible, alors aucune description du sentiment ne serait vraie. Mais si le mot « indescriptible » communique quelque chose sur le sentiment, alors il peut être considéré comme une description : c'est en soi contradictoire.

Le mathématicien et informaticien Gregory J. Chaitin dans The Unknowable (1999) ajoute ce commentaire : « Eh bien, l'historien mathématique mexicain Alejandro Garcidiego a pris la peine de trouver cette lettre [de Berry à partir de laquelle Russell a rédigé ses remarques], et un paradoxe différent. La lettre de Berry parle en fait du premier ordinal qui ne peut pas être nommé en un nombre fini de mots. Selon la théorie de Cantor, un tel ordinal doit exister, mais nous venons de le nommer en un nombre fini de mots, ce qui est une contradiction."

Résolution

Le paradoxe de Berry tel que formulé ci-dessus survient en raison de l' ambiguïté systématique du mot « définissable ». Dans d'autres formulations du paradoxe de Berry, comme celle qui se lit à la place : "... non nommable en moins..." le terme "nommable" est également celui qui a cette ambiguïté systématique. Les termes de ce genre donnent lieu à des erreurs de cercle vicieux . D'autres termes avec ce type d'ambiguïté sont : satisfiable, vrai, faux, fonction, propriété, classe, relation, cardinal et ordinal. Résoudre l'un de ces paradoxes signifie identifier exactement où notre utilisation du langage a mal tourné et fournir des restrictions sur l'utilisation du langage qui peuvent les éviter.

Cette famille de paradoxes peut être résolue en incorporant des stratifications de sens dans le langage. Les termes avec une ambiguïté systématique peuvent être écrits avec des indices indiquant qu'un niveau de sens est considéré comme une priorité plus élevée qu'un autre dans leur interprétation. "Le nombre non nommable 0 en moins de onze mots" peut être nommable 1 en moins de onze mots dans le cadre de ce schéma.

Analogues formels

En utilisant des programmes ou des preuves de longueurs bornées, il est possible de construire un analogue de l'expression de Berry dans un langage mathématique formel, comme cela a été fait par Gregory Chaitin . Bien que l'analogue formel ne conduise pas à une contradiction logique, il prouve certains résultats d'impossibilité.

George Boolos (1989) s'est appuyé sur une version formalisée du paradoxe de Berry pour prouver le théorème d'incomplétude de Gödel d'une manière nouvelle et beaucoup plus simple. L'idée de base de sa démonstration est qu'une proposition qui tient à x si et seulement si x = n pour un nombre naturel n peut être appelée une définition de n , et que l'ensemble {( n , k ): n a une définition qui est k symboles long} peut être représenté comme représentable (en utilisant les nombres de Gödel ). Alors la proposition « m est le premier nombre non définissable en moins de k symboles » peut être formalisée et montrée comme une définition dans le sens qui vient d'être indiqué.

Relation avec la complexité de Kolmogorov

Il n'est en général pas possible de définir sans ambiguïté quel est le nombre minimal de symboles nécessaires pour décrire une chaîne donnée (compte tenu d'un mécanisme de description spécifique). Dans ce contexte, les termes chaîne et nombre peuvent être utilisés de manière interchangeable, puisqu'un nombre est en fait une chaîne de symboles, par exemple un mot anglais (comme le mot « onze » utilisé dans le paradoxe) alors que, d'autre part, il est possible faire référence à n'importe quel mot avec un numéro, par exemple par le numéro de sa position dans un dictionnaire donné ou par un codage approprié. Certaines chaînes longues peuvent être décrites exactement en utilisant moins de symboles que ceux requis par leur représentation complète, comme cela est souvent réalisé en utilisant la compression de données . La complexité d'une chaîne donnée est alors définie comme la longueur minimale requise par une description pour se référer (sans ambiguïté) à la représentation complète de cette chaîne.

La complexité de Kolmogorov est définie à l' aide de langages formels , ou machines de Turing, ce qui évite les ambiguïtés sur la chaîne résultant d'une description donnée. On peut prouver que la complexité de Kolmogorov n'est pas calculable. La preuve par contradiction montre que s'il était possible de calculer la complexité de Kolmogorov, alors il serait aussi possible de générer systématiquement des paradoxes similaires à celui-ci, c'est-à-dire des descriptions plus courtes que ce qu'implique la complexité de la chaîne décrite. C'est-à-dire que la définition du nombre de Berry est paradoxale car il n'est pas réellement possible de calculer combien de mots sont nécessaires pour définir un nombre, et nous savons qu'un tel calcul n'est pas possible à cause du paradoxe.

Voir également

Remarques

Les références

Liens externes