Paradoxo da baga

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 impresso, atribuiu-o a G. G. Berry (1867–1928), um bibliotecário júnior da Biblioteca Bodleian de Oxford. Russell chamou Berry de "a única pessoa em Oxford que entendia de lógica matemática". O paradoxo foi chamado de "paradoxo de Richard" por Jean-Yves Girard.

Visão geral

Considere a expressão:

"O menor inteiro positivo não definido em menos de sessenta letras."

Como há apenas vinte e seis letras no alfabeto inglês, há um número finito de frases com menos de sessenta letras e, portanto, um número finito de números inteiros positivos 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, então 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 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 inteiro definido por essa expressão, mas como a expressão é autocontraditória (qualquer inteiro que ela define pode ser definido com menos de sessenta letras), não pode haver nenhum inteiro definido por ela.

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

O matemático e cientista da computação Gregory J. Chaitin em O Incognoscível (1999) acrescenta este comentário: "Bem, o historiador matemático mexicano Alejandro Garcidiego se deu ao trabalho de encontrar aquela letra [de Berry do qual Russell escreveu suas observações], e é um paradoxo bastante diferente. A carta de Berry na verdade 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, tal ordinal deve existir, mas acabamos de nomeá-lo em um número finito de palavras, o 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 diz: "...não nomeável em menos..." o termo "nomeável" é também aquele que tem essa ambigüidade sistemática. Termos desse tipo dão origem a falácias do círculo vicioso. Outros termos com esse tipo de ambiguidade são: satisfatí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 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 onze palavras" pode ser nomeável₁ em menos de onze palavras sob este esquema.

No entanto, pode-se ler as contribuições de Alfred Tarski para o Paradoxo do Mentiroso para descobrir como essa resolução em idiomas fica aquém. Alfred Tarski diagnosticou o paradoxo como surgindo apenas em línguas que são "semanticamente fechadas", com o que ele quis dizer uma linguagem na qual é possível para uma sentença predicar a verdade (ou falsidade) de outra sentença na mesma língua. (ou mesmo de si mesmo). Para evitar a autocontradição, é necessário, ao discutir valores de verdade, prever níveis de linguagens, cada um dos quais pode predicar a verdade (ou falsidade) apenas de linguagens em um nível inferior. Assim, quando uma sentença se refere ao valor de verdade de outra, ela é semanticamente superior. A frase referida faz parte da "linguagem objeto", enquanto a frase referente é considerada parte de uma "meta-linguagem" em relação à linguagem objeto. É legítimo para sentenças em "idiomas" superior na hierarquia semântica para se referir a frases inferiores na "linguagem" hierarquia, mas não o contrário. Isso evita que um sistema se torne autorreferencial.

No entanto, este sistema está incompleto. Alguém gostaria de ser capaz de fazer declarações como "Para cada declaração no nível α da hierarquia, há uma declaração no nível α+1 que afirma que a primeira afirmação é falsa." Esta é uma declaração verdadeira e significativa sobre a hierarquia que Tarski define, mas refere-se a declarações em todos os níveis da hierarquia, portanto deve estar acima de todos os níveis da hierarquia e, portanto, não é possível dentro da hierarquia (embora versões limitadas de a sentença é possível). Saul Kripke é creditado por identificar essa incompletude na hierarquia de Tarski em seu altamente citado artigo "Esboço de uma teoria da verdade" e é reconhecido como um problema geral em linguagens hierárquicas.

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) desenvolveu 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 para x se e somente se x = n para algum número natural n pode ser chamado de definição para n, e que o conjunto {(n, k): n tem uma definição que tem k símbolos de comprimento} pode ser mostrado como 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 formalizado e mostrado como uma definição no sentido que acabamos de afirmar.

Relação com a complexidade de Kolmogorov

Em geral, não é possível definir inequivocamente qual é o número mínimo de símbolos necessários para descrever uma determinada string (dado um mecanismo de descrição específico). Nesse contexto, os termos string e número podem ser usados de forma intercambiável, pois 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 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 codificação adequada. Algumas strings longas podem ser descritas exatamente usando menos símbolos do que os 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) referir-se à representação completa dessa string.

A complexidade de Kolmogorov é definida usando linguagens formais, ou máquinas de Turing, o que evita ambiguidades sobre qual string resulta de uma determinada 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, também seria possível gerar sistematicamente paradoxos semelhantes a este, ou seja, descrições mais curtas do que a complexidade da cadeia 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.