Paradoxo de Berry

Paradoxo de Berry é um paradoxo autorreferencial decorrente de uma expressão como "o menor inteiro positivo indefinível em menos de onze palavras" (note que essa frase que o define tem menos que 11 palavras). Bertrand Russell, o primeiro a discutir o paradoxo em impressão, atribuiu isto a G.G. Berry (1867-1928), um bibliotecário júnior na biblioteca Bodleian, de Oxford, que tinha sugerido o mais limitado paradoxo decorrente da expressão "primeiro ordinal indefinível".

Lógica

Considere a expressão:

   "O menor inteiro positivo indefinível em menos de onze palavras"

Uma vez que há um número finito de palavras, há um número finito de frases com menos de onze palavras; e portanto, um número finito de inteiros positivos que são definidos por frases de menos de 11 palavras. Uma vez que existem infinitos números inteiros positivos, isto significa que existem inteiros positivos que não podem ser definidos por frases com menos de onze palavras. Se existem inteiros positivos que satisfazem uma dada propriedade, então há um menor inteiro positivo que satisfaz essa. Portanto, há um menor inteiro positivo que satisfaz a propriedade "indefinível em menos de onze palavras". Esse é o inteiro ao qual as expressões se referem. A expressão acima tem apenas dez palavras, então o inteiro é definido por uma expressão que possui menos de 11 palavras; não é o menor inteiro positivo indefinível em 11 palavras; e não é definível pela expressão. Isto é um paradoxo: deve haver um inteiro definido por essa expressão, mas uma vez que a expressão é autocontraditória (qualquer inteiro que define é definível em menos de onze palavras), não pode ser qualquer número inteiro definido por ele.

Resolução

O Paradoxo de Berry, como formulado acima, decorre por causa da ambiguidade sistemática na palavra "definível". Em outras formulações do Paradoxo de Berry, tal como aquele que, em vez de ler "não nomeável em menos...", o termo "nomeável" também possui a ambiguidade sistemática. Termos desse tipo dão origem a círculos viciosos. Outro termos com esse tipo de ambiguidade são: satisfazível, verdadeiro, falso, função, propriedade, classe, relação, cardinal e ordinal. Para resolver um desses paradoxos, significa identificar exatamente onde o nosso uso da linguagem deu errado e fornecer restrições sobre o uso da linguagem que podem evitá-los.

Essa família de paradoxos pode ser resolvida através da incorporação de estratificação de sentido na linguagem. Termos com ambiguidade 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 nomeável em menos de 11 palavras" pode ser nomeável em menos de 11 palavras nesse regime.

Análogos formais

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

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 da sua prova é a proposição que detém x, se x = n, para algum número natural n; e pode ser chamada de uma definição para n; e que o conjunto {(n,k): n tem um tamanho k de símbolos} possa ser mostrado para ser representável (utilizando números de Gödel). Em seguida, a proposição "m é o primeiro número não definível em menos de k símbolos" pode ser formalizada e mostrada como sendo a definição do senso declarado.

Relacionamento com a complexidade de Kolmogorov

 Artigo: Complexidade de Kolmogorov

Não é possível, em geral, definir de forma inequívoca o que é o número mínimo de símbolos necessários para descrever uma determinada cadeia (dado um mecanismo de descrição específica). Neste contexto, o número de cadeias e termos podem ser utilizados indiferentemente, uma vez que um número é, na verdade, uma cadeia de símbolos, isto é, uma palavra em inglês (como a palavra "onze" utilizada no paradoxo); enquanto, por outro lado, é possível se referir a qualquer palavra com um número, como por exemplo, pondo o número da sua posição num determinado dicionário ou por codificação adequada. Algumas cadeias longas podem ser descritas exatamente utilizando menos símbolos do que aqueles requeridos para a sua total representação, como é frequentemente experimentada utilizando compressão de dados. A complexidade de uma determinada cadeia é definida como o comprimento mínimo que uma descrição requer, a fim de (inequivocamente) referir-se à total representação dessa cadeia de caracteres.

A complexidade de Kolmogorov é definida utilizando linguagens formais, ou máquina de Turing, que evita ambiguidades sobre a sequência de resultados de uma dada descrição. Pode-se provar 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 similares a esse, isto é, descrições menores do que a complexidade implicada pela sequência descrita. Ou seja, a definição do número Berry é paradoxal, porque não é realmente possível calcular quantas palavras são necessárias para definir um número; e se sabe que este cálculo não é possível por causa do paradoxo.

Ver também

• Algoritmo do Castor
• Paradoxo
• Teoremas da incompletude de Gödel

Bibliografia

• Nicholas Griffin (2003-06-23). The Cambridge Companion to Bertrand Russell. Cambridge University Press. p. 63. ISBN 978-0-521-63634-6.
• Russell and Whitehead (1927).
• Willard Quine(1976) Ways of Paradox. Harvard Univ. Press
• Charles H. Bennett(1979). "On Random and Hard-to-Describe Numbers.". IBM Report RC7483. CiteSeerX: 10.1.1.27.3492..
• George Boolos(1989) "A new proof of the Gödel Incompleteness Theorem", Notices of the American Mathematical Society 36: 388–90; 676. Reimpressa * em sua(1998) Logic, Logic, and Logic. Harvard Univ. Press: 383-88.
• Gregory Chaitin(1993), Transcript of lecture given 27 October 1993 at the University of New Mexico
• Gregory Chaitin(1995) "The Berry Paradox." Complexity 1: 26-30.
• James D. French(1988) "The False Assumption Underlying Berry's Paradox," Journal of Symbolic Logic 53: 1220–1223.
• Bertrand Russell(1906) "Les paradoxes de la logique", Revue de métaphysique et de morale 14: 627–650
• Bertrand Russell; Alfred N. Whitehead(1927) Principia Mathematica. Cambridge University Press. 1962 Reedição parcial *56.