Em 1931, o lógico austríaco Kurt Gödel conseguiu indiscutivelmente uma das mais impressionantes conquistas intelectuais da história.
Os matemáticos da época buscavam uma base sólida para a matemática: um conjunto de fatos matemáticos básicos, ou axiomas, que eram consistentes - nunca levando a contradições - e completos, servindo como os blocos de construção de todas as verdades matemáticas.
Mas os chocantes teoremas da incompletude de Gödel, publicados quando ele tinha apenas 25 anos, acabaram com esse sonho. Ele provou que qualquer conjunto de axiomas que você poderia postular como uma possível base para a matemática será inevitavelmente incompleto; sempre haverá fatos verdadeiros sobre números que não podem ser provados por esses axiomas. Ele também mostrou que nenhum conjunto de axiomas candidatos pode provar sua própria consistência.
Seus teoremas da incompletude significavam que não pode haver teoria matemática de tudo, nem unificação do que é comprovável e do que é verdade. O que os matemáticos podem provar depende de suas suposições iniciais, e não de qualquer verdade fundamental, da qual todas as respostas surjam.
Nos 89 anos desde a descoberta de Gödel, os matemáticos se depararam com apenas os tipos de perguntas sem resposta que seus teoremas predisseram. 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, assim como o problema da parada, que pergunta se um programa de computador alimentado com uma entrada aleatória será executado para sempre ou eventualmente será interrompido. Questões indecidíveis surgiram até na física , sugerindo que a incompletude de Gödelian afeta não apenas a matemática, mas - de alguma maneira mal compreendida - a realidade.
Aqui está um resumo simplificado e informal de como Gödel provou seus teoremas.
Numeração Gödel
A principal manobra de Gödel foi mapear declarações sobre um sistema de axiomas em declarações dentro do sistema - isto é, sobre declarações sobre números. Esse mapeamento permite que um sistema de axiomas fale convincentemente sobre si mesmo.
A primeira etapa desse processo é mapear qualquer declaração matemática possível, ou série de instruções, para um número único chamado número Gödel.
A versão ligeiramente modificada do esquema de Gödel apresentada por Ernest Nagel e James Newman em 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 expressa pelo símbolo ∃, enquanto a adição é expressa por +. Importante, o símbolo s , denotando “sucessor de”, fornece uma maneira de especificar números; ss 0, por exemplo, refere-se a 2.
Esses doze símbolos são atribuídos aos números de Gödel 1 a 12.
| Sinal constante | Número Gödel | Significado usual |
| ~ | 1 | não |
| ∨ | 2 | ou |
| ⊃ | 3 | se então… |
| ∃ | 4 | há um… |
| = | 5 | é igual a |
| 0 0 | 6 | zero |
| s | 7 | o sucessor de |
| ( | 8 | sinal de pontuação |
| ) | 9 | sinal de pontuação |
| , | 10 | sinal de pontuação |
| + | 11 | mais |
| × | 12 | vezes |
Em seguida, letras representando variáveis, começando com x , y e z , em mapa números primos e superiores a 12 (ou seja, 13, 17, 19, ...).
Então, qualquer combinação desses 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 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 6, 5 e 6. Gödel precisa alterar essa sequência de três números em um número único e único - um número que nenhuma outra sequência de símbolos gerará. Para fazer isso, ele pega os três primeiros números primos (2, 3 e 5), eleva cada um ao número Gödel do símbolo na mesma posição na sequência e os multiplica. Assim, 0 = 0 se torna 2 6 × 3 5 × 5 6 , ou 243.000.000.
O mapeamento funciona porque nunca duas fórmulas acabam com o mesmo número de Gödel. Os números de Gödel são números inteiros, e os números inteiros são apenas fatores primos de uma única maneira. Portanto, a única fatoração primária de 243.000.000 é 2 6 × 3 5 × 5 6 , o que significa que há apenas uma maneira possível de decodificar o número de Gödel: a fórmula 0 = 0.
Gödel foi um passo além. Uma prova matemática consiste em uma sequência de fórmulas. Então Gödel deu a cada sequência de fórmulas um número único de Gödel também. Nesse caso, ele começa com a lista de números primos como antes - 2, 3, 5 e assim por diante. Ele então eleva cada primo ao número de Gödel da fórmula na mesma posição na sequência (2 243.000.000 ×…, se 0 = 0 ocorrer primeiro, por exemplo) e multiplica tudo juntos.
Aritmetização da Metamatemática
O verdadeiro benefício é que mesmo declarações sobre fórmulas aritméticas, chamadas declarações metamatemáticas, podem ser traduzidas em fórmulas com números de Gödel próprios.
Primeiro, considere a fórmula ~ (0 = 0), significando "zero não é igual a zero". Esta fórmula é claramente falsa. No entanto, ele possui 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 de "parênteses abertos") e assim por diante , produzindo 2 × × 8 × 5 6 × 7 5 × 11 6 × 13 9 .
Como podemos gerar números de Gödel para todas as fórmulas, mesmo as falsas, podemos falar sensatamente sobre essas fórmulas falando sobre seus números de Gödel.
Considere a afirmação: "O primeiro símbolo da fórmula ~ (0 = 0) é um til." Essa afirmação metamatemática (verdadeira) sobre ~ (0 = 0) se traduz em uma afirmação sobre o número de Gödel da fórmula - ou seja, que seu primeiro expoente é 1, o número de Gödel para um til. Em outras palavras, nossa afirmação diz que 2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 possui apenas um único fator de 2. Se ~ (0 = 0) tivesse começado com qualquer símbolo que não fosse um til, seu Gödel número teria pelo menos dois fatores de 2. Portanto, mais precisamente, 2 é um fator de 2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 , mas 2 2 não é um fator.
Podemos converter a última frase em uma fórmula aritmética precisa que podemos escrever * usando símbolos elementares. É claro que esta fórmula tem um número de Gödel, que poderíamos calcular mapeando seus símbolos em potências de números primos.
Este exemplo, escreveu Nagel e Newman, “exemplifica uma visão muito geral e profunda que está no cerne da descoberta de Gödel: propriedades tipográficas de longas cadeias de símbolos podem ser discutidas de maneira indireta, mas perfeitamente precisa, ao invés disso, falando sobre as propriedades de Gödel. fatorações primárias de números inteiros grandes. ”
A conversão em símbolos também é possível para a afirmação metamatemática: "Existe alguma sequência de fórmulas com o número Gödel x que comprova a fórmula com o número Gödel k " - ou, em suma, "a fórmula com o número Gödel k pode ser comprovada". A capacidade de "aritmetizar" esse tipo de afirmação preparou o terreno para o golpe.
G Si
O insight extra de Gödel foi que ele poderia substituir o número de Gödel de uma fórmula na própria fórmula, levando a um problema sem fim.
Para ver como a substituição funciona, considere a fórmula (∃ x ) ( x = sy). (Lê: “Existe alguma variável x que é o sucessor de y ” ou, em suma, “ y tem um sucessor”.) Como todas as fórmulas, ele tem um número de Gödel - um número inteiro grande que chamaremos m .
Agora vamos introduzir m na fórmula no lugar do símbolo y . Isso forma uma nova fórmula, (∃ x ) ( x = sm ), significando " m tem um sucessor". Como devemos chamar o número de Gödel dessa fórmula? Há três informações a serem transmitidas: Começamos com a fórmula que tem o número m de Gödel . Nele, 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 Gödel 17. Então, vamos designar o número Gödel da nova fórmula sub ( m , m , 17).
A substituição forma o cerne da prova de Gödel.
Ele considerou uma afirmação metamatemática ao longo das linhas de "A fórmula com o número de Gödel sub ( y , y , 17) não pode ser provada". Recordando a notação que acabamos de aprender, a fórmula com Gödel sub número ( y , y , 17) é a obtida tomando a fórmula com Gödel número y (alguns 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 que haja um y ).
As coisas estão ficando complicadas, mas, no entanto, nossa afirmação metamatemática - "A fórmula com número de Gödel sub ( y , y , 17) não pode ser provada" - certamente se traduzirá em uma fórmula com um número de Gödel exclusivo. Vamos chamá-lo de n .
Agora, uma última rodada de substituição: Gödel cria uma nova fórmula substituindo o número n em qualquer lugar em que exista um y na fórmula anterior. Sua nova fórmula diz: "A fórmula com o número Gödel sub ( n , n , 17) não pode ser provada". Vamos chamar essa 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 pegar a fórmula com o número de Gödel ne substituir n em qualquer lugar onde houver um símbolo com o número de Gödel 17. E G é exatamente essa fórmula! Devido à singularidade da fatoração primária, agora vemos que a fórmula G está falando não é outra senão o próprio G.
G afirma por si mesmo que não pode ser provado.
Mas G pode ser provado? Nesse caso, isso significa que há alguma sequência de fórmulas que comprova a fórmula com o número de Gödel sub ( n , n , 17). Mas esse é o oposto de G, que diz que essa prova não existe. Declarações opostas, G e ~ G, não podem ser verdadeiras em um 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 o número de Gödel sub ( n , n , 17) não pode ser provada", e foi exatamente isso que descobrimos ser o caso! Como G é verdadeiro, porém indecidível dentro do sistema axiomático usado para construí-lo, esse sistema está incompleto.
Você pode pensar que poderia apenas postar um axioma extra, usá-lo para provar G e resolver o paradoxo. Mas você não pode. Gödel mostrou que o sistema axiomático aumentado permitirá a construção de uma nova fórmula verdadeira Gʹ (de acordo com um plano semelhante ao anterior) que não pode ser provado dentro do novo sistema aumentado. Na busca por um sistema matemático completo, você nunca pode pegar seu próprio rabo.
Nenhuma prova de consistência
Aprendemos que se um conjunto de axiomas é consistente, ele é incompleto. Esse é o primeiro teorema da incompletude de Gödel. O segundo - que nenhum conjunto de axiomas pode provar sua própria consistência - segue facilmente.
O que significaria se um conjunto de axiomas pudesse provar que nunca produzirá uma contradição? Isso significaria que existe uma sequência de fórmulas construídas a partir desses axiomas que comprova a fórmula que significa, meta-esquematicamente, "Esse conjunto de axiomas é consistente". Pelo primeiro teorema, esse conjunto de axiomas seria necessariamente incompleto.
Mas "O conjunto de axiomas é incompleto" é o mesmo que dizer: "Existe uma fórmula verdadeira que não pode ser provada". Essa 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 sua própria consistência, poderíamos provar G. Mas não podemos. Portanto, nenhum conjunto de axiomas pode provar sua própria consistência.
A prova de Gödel acabou com a busca por um sistema matemático consistente e completo. O significado de incompletude "não foi totalmente compreensível", escreveram Nagel e Newman em 1958. Isso permanece verdadeiro hoje.
* Para o curioso, a indicação lê: “Não existe algum inteiro x , tais que x multiplicado por 2 é igual a 2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 , e ali não existe qualquer número inteiro x tal que x multiplicado por 4 é igual a 2¹ × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 ”. A fórmula correspondente é:
(∃ x ) ( x × ss 0 = sss … sss 0) ⋅ ~ (∃ x ) ( x × ssss 0 = sss … sss 0)
onde sss … sss 0 significa 2 × × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 cópias do símbolo sucessor s. O símbolo ⋅ significa “e” e é uma abreviação de uma expressão mais longa no vocabulário fundamental: p ⋅ q significa ~ (~ p ∨ ~ q ).