Seus teoremas da incompletude derrotaram a busca por uma teoria matemática de tudo. Quase cem anos depois, ainda estamos tentando entender as implicações disso.
Em 1931, o lógico austríaco Kurt Gödel aplicou indiscutivelmente um dos truques intelectuais mais surpreendentes da história.
Os matemáticos daquela época buscavam os fundamentos inabaláveis da matemática: um conjunto de fatos básicos, axiomas que seriam consistentes e completos, desempenhando o papel de blocos de construção de todas as verdades matemáticas.
No entanto, os chocantes teoremas da incompletude de Gödel, publicado por ele com apenas 25 anos de idade, destruiu esse sonho. Ele provou que qualquer conjunto de axiomas que você possa propor como a base da matemática será inevitavelmente incompleto. Sempre haverá afirmações verdadeiras sobre os números que não podem ser provadas usando esses axiomas. Ele também mostrou que nenhum conjunto de axiomas pode ser usado para provar sua própria consistência.
Seus teoremas da incompletude significam que não pode haver uma teoria matemática de tudo, e é impossível combinar o conjunto de afirmações prováveis com o conjunto de afirmações verdadeiras. O que os matemáticos podem provar depende de suposições iniciais, não de alguma verdade fundamental da qual todas as respostas se originam.
Nos 89 anos desde a descoberta de Gödel, os matemáticos tropeçaram em perguntas semelhantes sem resposta, cuja existência previu seus teoremas. Por exemplo, o próprio Gödel ajudou a estabelecer que a hipótese do continuum a respeito das cardinalidades dos infinitos é indecidível - assim como o problema de parada, no qual é necessário determinar se a execução de um programa de computador terminará com certos dados de entrada ou se executará para sempre. Questões insolúveis surgiram até mesmo na física , o que sugere que a incompletude de Gödel afeta não apenas a matemática, mas em algum sentido (não totalmente claro), a realidade.
O que se segue é um resumo breve, simplificado e informal de como Gödel provou seus teoremas.
Numeração de Gödel
O movimento principal de Gödel foi a comparação de afirmações sobre o sistema de axiomas com afirmações feitas dentro desse sistema - com afirmações sobre números. Essa justaposição permite ao sistema de axiomas raciocinar calmamente sobre si mesmo.
O primeiro passo é combinar qualquer afirmação matemática possível, ou sequência de afirmações, com um número único chamado número de Gödel .
Uma versão ligeiramente revisada da numeração de Gödel como apresentada no livro de 1958 Gödel's Proof de Ernest Nagel e James Newman, começa com 12 símbolos elementares, que servem como um dicionário para expressar um conjunto de axiomas básicos. Por exemplo, uma afirmação sobre a existência de algo pode ser expressa pelo símbolo ∃ e a adição pelo símbolo +. O s, que significa "próximo elemento", torna possível denotar números: por exemplo, ss0 significa dois.
Esses doze caracteres são então atribuídos aos números de Gödel de 1 a 12.
| Notação constante | Numeração de Gödel | Significado comum |
| ~ | 1 | não |
| ∨ | 2 | ou |
| ⊃ | 3 | se então .. |
| ∃ | 4 | existe |
| = | cinco | é igual a |
| 0 | 6 | zero |
| s | 7 | próximo item |
| ( | 8 | sinal de pontuação |
| ) | nove | sinal de pontuação |
| , | dez | sinal de pontuação |
| + | onze | um mais |
| × | 12 | multiplicar |
Em seguida, letras que denotam variáveis, começando com x, y e z, são combinadas com números primos maiores que 12 (13, 17, 19, ..).
Então, cada uma das combinações desses símbolos e variáveis - isto é, qualquer fórmula aritmética ou sequência de fórmulas que podem ser inventadas - obtém seu próprio número de Gödel.
Considere, por exemplo, a afirmação 0 = 0. Seus três símbolos correspondem aos números de Gödel 6, 5 e 6. Gödel precisa substituir essa sequência de três números por um único - um número que nenhuma outra sequência de símbolos produzirá. Para fazer isso, ele pega os três primeiros primos (2, 3 e 5), eleva cada um deles à potência igual ao número correspondente na sequência e os multiplica. Portanto, 0 = 0 torna-se 2 6 × 3 5 × 56 ou 243.000.000.
Essa marcação funciona porque duas fórmulas não fornecem o mesmo número de Gödel. Os números de Gödel são números inteiros e os números podem ser decompostos em fatores primos de uma maneira única. Portanto, a única maneira de fatorar 243.000.000 em fatores é 2 6 × 3 5 × 5 6 , ou seja, só há uma maneira de decifrar esse número de Gödel: escrevendo a fórmula 0 = 0.
Então Gödel foi ainda mais longe. Uma prova matemática consiste em uma sequência de fórmulas. Portanto, Gödel atribuiu a cada sequência de fórmulas seu próprio número de Gödel. Nesse caso, ele também começa com uma sequência de primos - 2, 3, 5, etc. Em seguida, ele eleva cada um deles à potência correspondente ao número de Gödel para a fórmula na mesma posição ordinal na sequência (digamos, 2.243.000.000 , se a fórmula 0 = 0 vier primeiro) e multiplica tudo junto.
Matemática aritmética
É notável que mesmo as declarações relativas às fórmulas aritméticas, as chamadas. declarações metamatemáticas podem ser traduzidas em fórmulas e receber seus próprios números de Gödel.
Considere primeiro a fórmula ~ (0 = 0), que significa “zero não é zero”. É claramente falso. No entanto, ele tem um número de Gödel: 2 elevado à potência de 1 (o número de Gödel para o caractere ~), multiplicado por 3 elevado à oitava potência (o número de Gödel para o parêntese esquerdo), e assim por diante, o que resulta em 2 1 × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 .
Visto que podemos gerar números de Gödel para todas as fórmulas, mesmo as falsas, podemos raciocinar sobre elas de forma significativa usando seus números de Gödel.
Considere a declaração “O primeiro caractere da fórmula ~ (0 = 0) é um til”. Esta declaração metamatemática verdadeira sobre ~ (0 = 0) se transforma em uma declaração sobre o número de Gödel de uma fórmula particular - a saber, que seu primeiro grau é 1, isto é, o número de Gödel para o til. Em outras palavras, nossa declaração diz que há apenas um fator "2" em 2 1 × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 . Se ~ (0 = 0) começasse com qualquer caractere diferente de um til, haveria pelo menos dois fatores em seu número . Então, para ser mais preciso, 2 é um fator de 2 1 × 3 8 × 5 6 × 7 5× 11 6 × 13 9 , mas 2 2 não é.
Podemos converter a última frase em uma fórmula matemática exata e escrevê-la usando símbolos elementares. Essa fórmula, naturalmente, terá seu próprio número de Gödel, que podemos calcular combinando seus símbolos com as potências dos números primos.
Se você estiver interessado, a formulação fica assim: há um inteiro x tal que x, multiplicado por 2, será igual a 2 1 × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 , mas não existe tal inteiro x que multiplicado por 4 deu 2 1 × 3 8 × 5 6× 7 5 × 11 6 × 13 9 . A fórmula correspondente é semelhante a esta:
(∃x) (x × ss0 = sss… sss0) ⋅ ~ (∃x) (x × ssss0 = sss… sss0)
Onde sss… sss0 significa 2 1 × 3 8 × 5 6 × 7 5 × 11 6 × 13 9 cópias do personagem do próximo elemento s. O símbolo ⋅ significa “e” e é uma notação mais curta para o vocabulário fundamental: p ⋅ q significa ~ (~ p ∨ ~ q).
Este exemplo, como escreveram Nagel e Newman, “ilustra uma ideia geral e profunda subjacente à descoberta de Gödel: podemos falar com muita precisão sobre as propriedades tipográficas de longas sequências de caracteres, mas não diretamente, mas por meio das propriedades da fatoração de grandes inteiros.
Declarações metamatemáticas também podem ser transformadas em símbolos. “Existe uma certa sequência de fórmulas com número de Gödel x, provando uma fórmula com número de Gödel k” - ou, em suma, “uma fórmula com número de Gödel k é demonstrável”. Foi a capacidade de “aritmética” tais declarações que lançou as bases para o golpe.
G por si só
Além disso, Gödel percebeu que era possível substituir o próprio número de Gödel, denotando uma fórmula, na própria fórmula - e isso já leva a problemas sem fim.
Para entender como essa substituição funciona, considere a fórmula (∃x) (x = sy). Significa "há uma variável x que é o próximo elemento de y", ou, mais simplesmente, "y '' '' tem o próximo elemento". Como todas as fórmulas, ele tem seu próprio número de Gödel - algum número inteiro grande, vamos chamá-lo de m.
Agora vamos inserir o número m na fórmula em vez do símbolo y. O resultado é uma nova fórmula (∃x) (x = sm), que significa “m tem o próximo elemento”. Qual é o número de Gödel para esta fórmula? Precisamos transmitir três características: começamos com uma fórmula que tem o número m de Gödel. Nele, substituímos o símbolo y pelo símbolo m. E, de acordo com o esquema de comparação descrito anteriormente, o número de Gödel do símbolo y é 17. Denotemos então o número de Gödel da nova fórmula sub (m, m, 17).
A substituição forma a base da prova de Gödel.
Estudante Kurt Gödel em Viena. Ele publicou teoremas da incompletude em 1931, um ano após receber seu diploma.
Ele considerou a seguinte declaração matemática: "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 adotar, sabemos que obtemos a fórmula com o número de Gödel sub (y, y, 17) tomando a fórmula com o número de Gödel y (alguma variável desconhecida) e substituindo esta variável y sempre que o símbolo com Gödel número 17 (isto é, onde quer que y ocorra).
A cabeça já está começando a girar, mas, no entanto, podemos traduzir definitivamente nossa declaração metamatemática, “uma fórmula com o número de Gödel sub (y, y, 17) não pode ser provada” em uma fórmula com um número de Gödel único. Vamos chamá-lo de n.
E a última etapa das substituições: Gödel cria uma nova fórmula, substituindo o número n onde quer que y apareça na fórmula anterior. Sua nova fórmula é a seguinte: “A fórmula com o número de Gödel sub (n, n, 17) não pode ser provada”. Vamos chamar essa fórmula de G.
G naturalmente tem um número de Gödel. Qual é esse número? Voila - deve ser sub (n, n, 17). Por definição, sub (n, n, 17) é o número de Gödel para a fórmula, que é obtido tomando a fórmula com o número de Gödel n e substituindo n sempre que um símbolo com o número de Gödel igual a 17 ocorre na fórmula. E G é exatamente essa fórmula e Há sim! Como os inteiros são decompostos em fatores primos de uma maneira única, fica claro para nós que a Fórmula G nos fala apenas sobre a própria Fórmula G, e nada mais.
G diz que isso por si só não pode ser provado.
Mas G pode ser provado? Se isso fosse possível, significaria que há alguma sequência de fórmulas provando uma fórmula com o número de Gödel sub (n, n, 17). Mas isso é o oposto da Fórmula G, que diz que não existe tal prova. Declarações opostas, G e ~ G, em um sistema consistente de axiomas não podem ser simultaneamente verdadeiras. Portanto, G deve ser improvável.
No entanto, embora G não possa ser provado, é definitivamente verdade. G diz que “a fórmula com o número de Gödel sub (n, n, 17) não pode ser provada”, que é exatamente o que estabelecemos! Visto que G é uma afirmação verdadeira, mas improvável, que existe dentro do sistema axiomático que usamos para construí-la, esse sistema está incompleto.
Você pode pensar que podemos apenas adicionar algum axioma adicional, usá-lo para provar G e resolver este paradoxo. Mas isso é impossível. Gödel mostrou que o sistema aumentado de axiomas tornará possível criar uma nova fórmula verdadeira G 'de acordo com o mesmo esquema de antes, o que não pode ser provado dentro da estrutura do novo sistema aumentado. Ao tentar construir um sistema matemático completo, você apenas perseguirá seu próprio rabo sem sucesso.
Falta de prova de consistência
Agora sabemos que se um conjunto de axiomas é consistente, ele está incompleto. Este é o primeiro teorema da incompletude de Gödel. O segundo decorre facilmente disso - nenhum conjunto de axiomas pode provar sua consistência.
O que significaria se um conjunto de axiomas pudesse provar que nunca seria controverso? Isso significaria que existe uma sequência de fórmulas construída sobre esses axiomas, comprovando uma fórmula que, metamatemática, significa “este conjunto de axiomas é consistente”. Mas então, de acordo com o primeiro teorema, esse conjunto de axiomas seria necessariamente incompleto.
Porém, dizer que “o conjunto de axiomas está incompleto” é o mesmo que dizer “existe uma fórmula verdadeira que não pode ser provada”. E isso é equivalente à nossa fórmula G. E sabemos que os axiomas não podem provar G.
Assim, Gödel construiu uma prova por contradição: se um conjunto de axiomas pudesse provar sua própria consistência, então poderíamos provar G. Mas não podemos. Conseqüentemente, nenhum conjunto de axiomas prova sua própria consistência.
A prova de Gödel matou a busca por um sistema matemático consistente e completo. Os matemáticos “não conseguiram captar toda a profundidade” da incompletude, escreveram Nagel e Newman em 1958. E hoje essa afirmação continua verdadeira.
Veja também: