Em 1931, o lógico austríaco Kurt Gödel conseguiu sem dúvida uma das mais espantosas realizações intelectuais da história.
Os matemáticos da época procuraram uma base sólida para a matemática: um conjunto de factos matemáticos básicos, ou axiomas, que fosse simultaneamente consistente – nunca conduzindo a contradições – e completo, servindo como blocos de construção de todas as verdades matemáticas.
Mas os teoremas chocantes de incompletude de Gödel, publicados quando ele tinha apenas 25 anos, esmagaram esse sonho. Ele provou que qualquer conjunto de axiomas que se possa apresentar como base possível para a matemática estará inevitavelmente incompleto; haverá sempre factos verdadeiros sobre números que não podem ser provados por esses axiomas. Ele também mostrou que nenhum conjunto de axiomas candidatos pode alguma vez provar a sua própria consistência.
Os seus teoremas de incompletude significam que não pode haver teoria matemática de tudo, nenhuma unificação do que é provável e do que é verdadeiro. O que os matemáticos podem provar depende dos seus pressupostos iniciais, e não de qualquer verdade fundamental do terreno a partir do qual todas as respostas surgem.
Nos 89 anos desde a descoberta de Gödel, os matemáticos tropeçaram apenas nos tipos de perguntas não respondidas que os seus teoremas previam. Por exemplo, o próprio Gödel ajudou a estabelecer que a hipótese do continuum, que diz respeito aos tamanhos do infinito, é indecidível, tal como o problema da paragem, que pergunta se um programa de computador alimentado com uma entrada aleatória funcionará para sempre ou eventualmente será interrompido. Questões indecidíveis surgiram mesmo na física, sugerindo que a incompletude de Gödelian aflige não só a matemática, mas – de alguma forma mal compreendida – a realidade.
p>Aqui está um resumo simplificado e informal de como Gödel provou os seus teoremas.
Numeração de Gödel
A principal manobra de Gödel foi mapear declarações sobre um sistema de axiomas em declarações dentro do sistema – ou seja, em declarações sobre números. Este mapeamento permite a um sistema de axiomas falar convincentemente sobre si mesmo.
O primeiro passo neste processo é mapear qualquer declaração matemática possível, ou série de declarações, para um número único chamado número de Gödel.
A versão ligeiramente modificada do esquema de Gödel apresentada por Ernest Nagel e James Newman no seu livro de 1958, Gödel’s Proof, começa com 12 símbolos elementares que servem como vocabulário para expressar um conjunto de axiomas básicos. Por exemplo, a afirmação de que algo existe pode ser expresso pelo símbolo ∃, enquanto que a adição é expressa por +. Importante, o símbolo s, denotando “sucessor de”, dá uma forma de especificar números; ss0, por exemplo, refere-se a 2,
Estes doze símbolos são então atribuídos aos números de Gödel de 1 a 12.
| Sinal constante | Número de Gödel | Usual Meaning |
| 1 | not | |
| ∨ | 2 | ou |
| ⊃ | 3 | se…então… |
| ∃ | 4 | aqui é um… |
| = | 5 | equais |
| 0 | 6 | zero |
| s | 7 | o sucessor de |
| ( | 8 | marca de pontuação |
| ) | 9 | marca de pontuação | , | 10 | punctuation mark |
| + | 11 | plus |
| × | 12 | vezes |
P>Próximo, letras que representam variáveis, começando por x, y e z, mapeadas para números primos superiores a 12 (ou seja, 13, 17, 19, …).
Então qualquer combinação destes símbolos e variáveis – ou seja, qualquer fórmula aritmética ou sequência de fórmulas que possam ser construídas – obtém o seu próprio número de Gödel.
Por exemplo, considere 0 = 0. Os três símbolos da fórmula correspondem aos números de Gödel 6, 5 e 6. Gödel precisa de mudar esta sequência de três números para um número único e único – um número que nenhuma outra sequência de símbolos irá gerar. Para tal, toma os três primeiros primes (2, 3 e 5), eleva cada um ao número de Gödel do símbolo na mesma posição na sequência, e multiplica-os em conjunto. Assim 0 = 0 torna-se 26 × 35 × 56, ou 243.000.000,
O mapeamento funciona porque nenhuma das duas fórmulas acabará alguma vez com o mesmo número Gödel. Os números de Gödel são números inteiros, e os números inteiros são apenas factores em primes de uma única forma. Assim, a única factorização primária de 243.000.000 é 26 × 35 × 56, o que significa que só há uma forma possível de descodificar o número de Gödel: a fórmula 0 = 0,
Gödel foi então um passo mais à frente. Uma prova matemática consiste numa sequência de fórmulas. Assim, Gödel também deu a cada sequência de fórmulas um número de Gödel único. Neste caso, ele começa com a lista de números primos como antes – 2, 3, 5 e assim por diante. Em seguida, ele eleva cada prime para o número de Gödel da fórmula na mesma posição na sequência (2243.000.000 × …, se 0 = 0 vem primeiro, por exemplo) e multiplica tudo em conjunto.
Aritmetização de Metamathematics
A verdadeira vantagem é que mesmo as afirmações sobre fórmulas aritméticas, chamadas afirmações metamatméticas, podem, elas próprias, ser traduzidas em fórmulas com números de Gödel próprios.
Primeiro considerar a fórmula ~(0 = 0), significando “zero não é igual a zero”. Esta fórmula é claramente falsa. No entanto, tem um número de Gödel: 2 elevado à potência de 1 (o número de Gödel do símbolo ~), multiplicado por 3 elevado à potência de 8 (o número de Gödel do símbolo “parênteses abertos”), e assim por diante, produzindo 2¹ × 38 × 56 × 75 × 116 × 139.
Porque podemos gerar números de Gödel para todas as fórmulas, mesmo as falsas, podemos falar sensatamente sobre estas fórmulas falando dos seus números de Gödel.
Considerar a afirmação, “O primeiro símbolo da fórmula ~(0 = 0) é um til”. Esta afirmação (verdadeira) metamathematical sobre ~(0 = 0) traduz-se numa afirmação sobre o número de Gödel da fórmula – nomeadamente, que o seu primeiro expoente é 1, o número de Gödel para um til. Por outras palavras, a nossa afirmação diz que 2¹ × 38 × 56 × 75 × 116 × 139 tem apenas um factor de 2. Se ~(0 = 0) tivesse começado com qualquer símbolo que não fosse um til, o seu número de Gödel teria pelo menos dois factores de 2. Portanto, mais precisamente, 2 é um factor de 2¹ × 38 × 56 × 75 × 116 × 139, mas 22 não é um factor.
Podemos converter a última frase numa fórmula aritmética precisa que podemos escrever* usando símbolos elementares. Esta fórmula tem naturalmente um número de Gödel, que poderíamos calcular mapeando os seus símbolos em poderes de primes.
Este exemplo, Nagel e Newman escreveram, “exemplifica uma percepção muito geral e profunda que está no centro da descoberta de Gödel: as propriedades tipográficas de longas cadeias de símbolos podem ser faladas de uma forma indirecta mas perfeitamente precisa, falando em vez disso das propriedades de factorizações primárias de grandes inteiros.”
Conversão em símbolos também é possível para a afirmação metamathematical, “Existe alguma sequência de fórmulas com número de Gödel x que prova a fórmula com número de Gödel k” – ou, em suma, “A fórmula com número de Gödel k pode ser provada”. A capacidade de “aritmetizar” este tipo de afirmação preparou o palco para o golpe.
G Itself
A percepção extra de Gödel era que ele podia substituir o próprio número de Gödel de uma fórmula na própria fórmula, não levando a problemas.
Para ver como a substituição funciona, considere a fórmula (∃x)(x = sy). (Diz: “Existe alguma variável x que é o sucessor de y”, ou, em suma, “y tem um sucessor”). Como todas as fórmulas, tem um número de Gödel – algum número inteiro grande a que chamaremos apenas m.
Agora vamos introduzir m na fórmula em vez do símbolo y. Isto forma uma nova fórmula, (∃x)(x = sm), que significa, “m tem um sucessor”. Como chamaremos a esta fórmula o número de Gödel? Há três pedaços de informação a transmitir: Começámos com a fórmula que tem o número de Gödel m. Nela, substituímos m pelo símbolo y. E de acordo com o esquema de mapeamento introduzido anteriormente, o símbolo y tem o número de Gödel 17. Assim, vamos designar a nova fórmula com o número Gödel sub(m, m, 17).
Substituição forma o ponto crucial da prova de Gödel.
Ele considerou uma afirmação metamátema segundo as linhas de “A fórmula com número Gödel sub(y, y, 17) não pode ser provada”. Recordando a notação que acabámos de aprender, a fórmula com número de Gödel sub(y, y, 17) é a obtida tomando a fórmula com número de Gödel y (alguma variável desconhecida) e substituindo esta variável y em qualquer lugar há um símbolo cujo número de Gödel é 17 (ou seja, em qualquer lugar há um y).
As coisas estão a ficar trippy, mas no entanto, a nossa afirmação metamathematical – “A fórmula com número de Gödel sub(y, y, 17) não pode ser provada” – é certamente traduzida numa fórmula com um número de Gödel único. Vamos chamar-lhe n.
Agora, uma última ronda de substituição: Gödel cria uma nova fórmula substituindo o número n em qualquer lugar onde haja um y na fórmula anterior. A sua nova fórmula diz: “A fórmula com número de Gödel sub(n, n, 17) não pode ser provada”. Vamos chamar a esta nova fórmula G.
Naturalmente, G tem um número de Gödel. Qual é o seu valor? Eis que deve ser sub(n, n, 17). Por definição, sub(n, n, 17) é o número de Gödel da fórmula que resulta de tomar a fórmula com o número de Gödel n e substituir n em qualquer lugar onde haja um símbolo com o número de Gödel 17. E G é exactamente esta fórmula! Devido à singularidade da factorização primária, vemos agora que a fórmula de que G está a falar não é outra senão G em si.
G afirma de si mesmo que não pode ser provado.
Mas será que G pode ser provado? Se sim, isto significaria que há alguma sequência de fórmulas que prova a fórmula com o número de Gödel sub(n, n, 17). Mas isso é o oposto de G, que diz não existir tal prova. As declarações opostas, G e ~G, não podem ser ambas verdadeiras num sistema axiomático consistente. Portanto, a verdade de G deve ser indecidível.
No entanto, embora G seja indecidível, é claramente verdade. G diz: “A fórmula com número de Gödel sub(n, n, 17) não pode ser provada”, e foi exactamente o que descobrimos ser o caso! Uma vez que G é verdadeiro, mas indecidível dentro do sistema axiomático utilizado para o construir, esse sistema está incompleto.
Poderia pensar-se que se poderia simplesmente colocar algum axioma extra, usá-lo para provar G, e resolver o paradoxo. Mas não se pode. Gödel mostrou que o sistema axiomático aumentado permitirá a construção de uma nova e verdadeira fórmula Gʹ (de acordo com um plano semelhante ao anterior) que não pode ser provada dentro do novo sistema aumentado. Ao lutar por um sistema matemático completo, nunca se pode apanhar a própria cauda.
Sem prova de consistência
Aprendemos que se um conjunto de axiomas é consistente, então está incompleto. Este é o primeiro teorema de Gödel de incompletude. O segundo – que nenhum conjunto de axiomas pode provar a sua própria consistência – segue-se facilmente.
O que significaria se um conjunto de axiomas pudesse provar que nunca irá produzir uma contradição? Significaria que existe uma sequência de fórmulas construídas a partir destes axiomas que prova a fórmula que significa, metamathematicamente, “Este conjunto de axiomas é consistente”. Pelo primeiro teorema, este conjunto de axiomas estaria então necessariamente incompleto.
Mas “O conjunto de axiomas é incompleto” é o mesmo que dizer, “Há uma fórmula verdadeira que não pode ser provada”. Esta afirmação é equivalente à nossa fórmula G. E sabemos que os axiomas não podem provar G.
Então, Gödel criou uma prova por contradição: Se um conjunto de axiomas pudesse provar a sua própria consistência, então seríamos capazes de provar G. Mas não podemos. Portanto, nenhum conjunto de axiomas pode provar a sua própria consistência.
A prova de Gödel matou a procura de um sistema matemático consistente e completo. O significado de incompletude “não foi totalmente sondado”, escreveram Nagel e Newman em 1958. Continua a ser verdade hoje.
*Para o curioso, a afirmação diz: “Existe algum número inteiro x tal que x multiplicado por 2 é igual a 2¹ × 38 × 56 × 75 × 116 × 139, e não existe nenhum número inteiro x tal que x multiplicado por 4 é igual a 2¹ × 38 × 56 × 75 × 116 × 139”. A fórmula correspondente é:
(∃x)(x × ss0 = sss … sss0) ⋅ ~(∃x)(x × sss0 = sss … sss0)
onde sss … sss0 representa 2¹ × 38 × 56 × 75 × 116 × 139 cópias do símbolo sucessor s. O símbolo ⋅ significa “e”, e é abreviatura para uma expressão mais longa no vocabulário fundamental: p ⋅ q significa ~(~p ∨ ~q).
Este artigo foi reimpresso em Wired.com.