Paradoxo de Berry - Berry paradox

O paradoxo de Berry é um paradoxo autorreferencial que surge de uma expressão como "O menor inteiro positivo não definível em menos de sessenta letras" (uma frase com cinquenta e sete letras).

Bertrand Russell , o primeiro a discutir o paradoxo na impressão, atribuiu a GG Berry (1867-1928), um júnior bibliotecário em Oxford 's biblioteca Bodleian . Russell chamou Berry de "a única pessoa em Oxford que entendia de lógica matemática".

Visão geral

Considere a expressão:

"O menor número inteiro positivo não definível em menos de sessenta letras."

Uma vez que existem apenas 26 letras no alfabeto inglês, existem finitamente muitas frases com menos de sessenta letras e, portanto, um número finito de inteiros positivos que são definidos por frases com menos de sessenta letras. Como existem infinitos inteiros positivos, isso significa que existem inteiros positivos que não podem ser definidos por frases com menos de sessenta letras. Se houver inteiros positivos que satisfaçam uma determinada propriedade, haverá um menor inteiro positivo que satisfaça essa propriedade; portanto, há um menor inteiro positivo que satisfaz a propriedade "não definível em menos de sessenta letras". Este é o número inteiro ao qual a expressão acima se refere. Mas a expressão acima tem apenas cinquenta e sete letras, portanto é definível em menos de sessenta letras, e não é o menor inteiro positivo não definível em menos de sessenta letras, e não é definido por esta expressão. Isso é um paradoxo: deve haver um número inteiro definido por esta expressão, mas como a expressão é autocontraditória (qualquer número inteiro definido por ela é definível em menos de sessenta letras), não pode haver nenhum número inteiro definido por ela.

Talvez outra analogia útil para o Paradoxo de Berry seja a frase "sentimento indescritível". Se o sentimento é realmente indescritível, nenhuma descrição do sentimento seria verdadeira. Mas se a palavra "indescritível" comunica algo sobre o sentimento, então pode ser considerada uma descrição: isso é contraditório.

O matemático e cientista da computação Gregory J. Chaitin em The Unknowable (1999) adiciona este comentário: "Bem, o historiador matemático mexicano Alejandro Garcidiego se deu ao trabalho de encontrar aquela carta [de Berry da qual Russell escreveu suas observações], e é bastante um paradoxo diferente. A carta de Berry realmente fala sobre o primeiro ordinal que não pode ser nomeado em um número finito de palavras. De acordo com a teoria de Cantor, esse ordinal deve existir, mas acabamos de nomeá-lo em um número finito de palavras, que é uma contradição. "

Resolução

O paradoxo de Berry conforme formulado acima surge devido à ambigüidade sistemática na palavra "definível". Em outras formulações do paradoxo de Berry, como aquela que em vez disso diz: "... não nominável em menos ...", o termo "nominável" também possui essa ambigüidade sistemática. Termos desse tipo dão origem a falácias de círculo vicioso . Outros termos com este tipo de ambigüidade são: satisfazível, verdadeiro, falso, função, propriedade, classe, relação, cardinal e ordinal. Resolver um desses paradoxos significa apontar exatamente onde nosso uso da linguagem deu errado e fornecer restrições ao uso da linguagem que podem evitá-los.

Essa família de paradoxos pode ser resolvida incorporando estratificações de significado na linguagem. Termos com ambigüidade sistemática podem ser escritos com subscritos denotando que um nível de significado é considerado uma prioridade mais alta do que outro em sua interpretação. "O número não nominável 0 em menos de onze palavras" pode ser denominado 1 em menos de onze palavras neste esquema.

Análogos formais

Usando programas ou provas de comprimentos limitados, é possível construir um análogo da expressão de Berry em uma linguagem matemática formal, como foi feito por Gregory Chaitin . Embora o análogo formal não leve a uma contradição lógica, ele prova certos resultados de impossibilidade.

George Boolos (1989) construiu uma versão formalizada do paradoxo de Berry para provar o teorema da incompletude de Gödel de uma maneira nova e muito mais simples. A ideia básica de sua prova é que uma proposição que vale de x se e somente se x = n para algum número natural n pode ser chamada de definição para n , e que o conjunto {( n , k ): n tem uma definição que é k símbolos longos} pode ser mostrado para ser representável (usando números de Gödel ). Então, a proposição " m é o primeiro número não definível em menos de k símbolos" pode ser formalizada e mostrada como uma definição no sentido que acabamos de declarar.

Relação com a complexidade de Kolmogorov

Em geral, não é possível definir de forma inequívoca qual é o número mínimo de símbolos necessários para descrever uma dada string (dado um mecanismo de descrição específico). Neste contexto, os termos string e número podem ser usados ​​alternadamente, uma vez que um número é na verdade uma string de símbolos, por exemplo, uma palavra em inglês (como a palavra "onze" usada no paradoxo) enquanto, por outro lado, é possível para se referir a qualquer palavra com um número, por exemplo, pelo número de sua posição em um determinado dicionário ou por uma codificação adequada. Algumas strings longas podem ser descritas exatamente usando menos símbolos do que aqueles exigidos por sua representação completa, como geralmente é obtido usando compactação de dados . A complexidade de uma determinada string é então definida como o comprimento mínimo que uma descrição requer para (inequivocamente) se referir à representação completa dessa string.

A complexidade de Kolmogorov é definida usando linguagens formais , ou máquinas de Turing, que evita ambigüidades sobre qual string resulta de uma determinada descrição. Pode-se comprovar que a complexidade de Kolmogorov não é computável. A prova por contradição mostra que se fosse possível calcular a complexidade de Kolmogorov, então também seria possível gerar sistematicamente paradoxos semelhantes a este, ou seja, descrições mais curtas do que a complexidade da string descrita implica. Ou seja, a definição do número de Berry é paradoxal porque não é realmente possível calcular quantas palavras são necessárias para definir um número, e sabemos que tal cálculo não é possível por causa do paradoxo.

Veja também

Notas

Referências

links externos