De Peano para Gödel, parte 4 de 4
De Peano para Gödel, parte 4 de 4
Este artigo é dividido em quatro partes. Esta é a quarta e última parte. Clique aqui para retornar à parte anterior.
Se teoremas e provas de teoremas podem ser convertidos em números, e obviamente teorema e demonstração são relacionados, então os respectivos números de Gödel podem ser relacionados.
Suponha o teorema T, cujo número de Gödel é t, e cuja prova possua número p.
Definimos então um predicado PROVA(t,p) que define pares de números t e p; teoremas e respectivas provas. O predicado é verdadeiro quando p demonstra t. Será um dos instrumentos mais adiante.
Gödel teve bastante trabalho para provar que este predicado PROVA(t,p) pode ser codificado em termos aritméticos e lógicos. (Se não fosse, tudo acabaria no mesmo brejo que Richard, pois PROVA() seria um predicado diferente dos demais.)
Em seu artigo, Gödel definiu toda uma família de funções que manipulam e testam fórmulas, sempre usando operações aritméticas e predicados atuando sobre os números de Gödel das fórmulas. A leitura cuidadosa convence o leitor que de fato o esquema funciona.
Outro conceito do artigo intimamente relacionado a estas funções é a função primitiva recursiva. É basicamente a certeza de que uma fórmula pode ser calculada num limite finito de tempo.
O método genérico de obter esta certeza é lancar mão de uma definição recursiva. Por exemplo, a definição de fatorial n!=n.(n-1)!, 0!=1 é um exemplo bem cohecido. É apenas uma definição; não é o método mais eficiente de calcular fatorial, mas temos a garantia de que obteremos o resultado em, no máximo, n passos.
Gödel mostra em seu artigo que funções como PROVA(a,b) são primitivas recursivas; elas tomariam um tempo grande, mas nunca infinito, para serem calculadas.
(A propósito, um programa de computador pode executar tarefas mais complexas que fórmulas primitivas recursivas, porque um programa não tem obrigação de terminar. Uma planilha Excel não tem obrigação de fechar depois de n horas de execução.)
Um detalhe crucial nisto é que cada instância concreta de PROVA(a,b), onde as variáveis livres t,p foram substituídas por números a,b, também tem seu número de Gödel. Cada exemplar concreto encarrega-se de afirmar que o par a,b em questão é um teorema e sua respectiva prova, ou não.
O outro instrumento a ser utilizado no núcleo da prova da incompleteza é a substituição de variáveis por números. Vamos definir esta fórmula como SUBST(t, s, v), onde t é o número de Gödel da fórmula; s é o código da variável a ser substituída; e v é o valor numérico que toma o lugar da variável.
Devido ao método que concebemos para calcular números de Gödel a partir de fórmulas, é mais fácil enxergar que esta substituição pode ser calculada com simples aritmética. Dá muito trabalho, é preciso fazer fatoração, achar os expoentes etc. mas é perfeitamente possível.
Ou seja, a fórmula SUBST tem expressão na aritmética pura, não é apenas meta-matemática. Desta forma, SUBST também tem um número de Gödel para ela.
Lembre que, no esquema de codificação que definimos há muitos parágrafos, a variável x recebeu o código 13. Assim, substituir os x de uma fórmula pelo número 5 seria expresso assim:
u = SUBST(t, 13, 5) t: número de Gödel da fórmula ou teorema u: número de Gödel da nova fórmula, onde 'x' vale 5
Não existe nenhuma relação aritmética entre o 13 e o 5; são laranjas e bananas justapostas, e SUBST troca laranja por banana.
Como às vezes fica difícil enxergar o que faz este 13 ao lado do 5, podemos adotar uma notação alternativa, que coloque o símbolo entre aspas, assim fica claro que é um símbolo e não uma variável independente:
u = SUBST(t, 'x', 5) t: número de Gödel da fórmula ou teorema u: número de Gödel da nova fórmula, onde 'x' vale 5 'x': símbolo ou caractere, cujo valor de Gödel é 13
Podemos estender esta idéia de usar aspas para a própria fórmula, tornando mais claro o que significa cada pedaço.
G: função que calcula o número de Gödel para uma fórmula
G('5 + 1 = 6') = SUBST(G('x + 1 = Sx'), 'x', 5)
Lembrando sempre que, na aritmética de Peano e na geração dos números de Gödel, não existem os números 1 e 5. Existem os sucessores de zero, apenas. Fomos um pouco relapsos neste aspecto... o correto (e tedioso) seria escrever
G('SSSSS0 + S0 = SSSSSS0') = SUBST(G('x + S0 = Sx'), 'x', 5)
Um caso especial de SUBST é quando a fórmula não possui a variável a ser substituída. Neste caso, SUBST retorna o mesmo número de Gödel da fórmula original, o que significa que a fórmula não foi alterada:
SUBST(G('5 + 1 = 6'), 'x', 5) = G('5 + 1 = 6')
Disto também podemos deduzir que aplicar SUBST diversas vezes sobre uma mesma fórmula não tem efeito, pelo menos não além da primeira rodada.
Um outro caso interessante, ou bizarro, de SUBST, é substituir uma variável pelo próprio número de Gödel da fórmula. Algo como:
x = Número de Gödel de uma fórmula qualquer u = SUBST(x, 'x', x)
Pode ser feito, já que x é um número, mas é confuso porque sabemos que esse número tem um significado "maior". Este truque é utilizado na prova da incompleteza de Gödel a seguir.
A prova de Gödel consiste em construir uma expressão indecidível, utilizando as ferramentas mostradas há pouco. Começamos com a fórmula
Não existe x tal que PROVA(SUBST(y, 'y', y), x)
Como SUBST é uma fórmula aritmética, SUBST(y,'y',y) é calculável, qualquer que seja o valor de y. Vamos desmembrar a fórmula para enxergar isto melhor:
w = SUBST(y, 'y', y) Não existe x tal que PROVA(w, x)
Considerando o significado de PROVA, estamos dizendo que PROVA nunca é verdadeiro quando o número w (relacionável a um teorema) é o primeiro parâmetro, seja qual for x (relacionável a uma demonstração).
Em resumo, a fórmula diz: w não pode ser provado.
Tá, e daí? Pode ser uma afirmação falsa. Mas, mesmo que seja falsa, ela possui um número de Gödel, que chamaremos de h.
h = G("Não existe x tal que PROVA(SUBST(y, 'y', y), x)")
Agora, a fórmula final:
Não existe x tal que PROVA(SUBST(h, 'y', h), x)
Aqui, afirmamos que a fórmula h não pode ser provada. Esta última fórmula também possui seu número de Gödel, g.
g = G("Não existe x tal que PROVA(SUBST(h, 'y', h), x)")
Porém, g também é igual a SUBST(h,'y',h), ou seja, o teorema com esse número de Gödel referencia a si mesmo. Revisando:
h = G("Não existe x tal que PROVA(SUBST(y, 'y', y), x)")
Pegando a fórmula acima e Fazendo a substituição de 'y' por 'h', temos
g = G("Não existe x tal que PROVA(SUBST(h, 'y', h), x)")
A função que executa essa substituição de forma aritmética, usando o número de Gödel da fórmula original, e devolvendo o número de Gödel da fórmula modificada, é SUBST(), então as duas fórmulas abaixo são equivalentes:
g = G("Não existe x tal que PROVA(SUBST(h, 'y', h), x)")
g = SUBST(h, 'y', h)
porém coincide que SUBST(h, 'y', h), além de ser uma definição completa do número g, também aparece dentro da própria fórmula de g.
Por conta disso, deduzimos que o teorema g está falando de si mesmo, de forma indireta e bastante engenhosa. Interpretendo isso em linguagem humana:
Não existe x que prove este teorema.
ou
Este teorema não pode ser demonstrado.
Muito bem. Se este teorema g fosse demonstrável, então este fato poderia ser expresso como Este teorema pode ser demonstrado. Uma afirmação exatamente contrária à que encontramos no parágrafo anterior. A propósito, vamos rotular este anti-teorema como ~g. O til é o símbolo usual de negação na lógica.
Com duas afirmações opostas e simultaneamente verdadeiras, a aritmética seria então um sistema inconsistente, do tipo em que 0=0 e 0=1 ao mesmo tempo.
Por outro lado, é mais provável é que a aritmética seja consistente. E neste caso, nem g nem sua negação ~g podem ser demonstrados.
Mas, apesar de não serem demonstráveis, os teoremas dizem alguma coisa. Um está dizendo a verdade, e o outro não. Qual dos dois é verdadeiro?
No plano meta-matemático, podemos afirmar que g é verdadeiro, porque ele diz exatamente o que constatamos: que g não pode ser provado com recursos aritméticos.
No nível da aritmética pura, poderíamos adotar g ou ~g (mas nunca os dois ao mesmo tempo) como um novo axioma, de forma a "estender" o poder da aritmética de Peano — assim como admitir que existe um antecessor de zero "cria" os números negativos.
O livro GEB faz um interessante exercício mental sobre a idéia de estender a aritmética de Peano com g. Ele imaginou números "sobrenaturais", dentre os quais encontraríamos a prova para g.
Hofstadter aproveita-se de um fino detalhe de g: não existe número natural que prove g. Mas, se considerarmos outras espécies de número, então...
É fantasmagórico, mas é como admitir que existe um número i cujo quadrado é igual a -1. Definitivamente os números imaginários não são algo palpável, e o grosso da população simplesmente não os entende, apesar de presentes no currículo escolar.
Mas este tipo de extensão não resolve o problema da incompleteza; mesmo na presença de g como axioma, podemos utilizar a prova de Gödel novamente e achar um novo teorema g2 que também não admite prova, senão num hipotético reino de números "sobresobrenaturais".
Conforme dissemos antes, a incompleteza é "essencial": faz parte do sistema e não pode ser sanada.
As sentenças de Henkin são basicamente fórmulas opostas àquela encontrada por Gödel. Elas afirmam, em vez de negar, sua própria provabilidade:
i = G("Existe sim x tal que PROVA(SUBST(y, 'y', y), x)")
Existe sim x tal que PROVA(SUBST(i, 'y', i), x)
Este teorema pode ser demonstrado.
As sentenças de Henkin são de fato verdadeiras. Isto foi provado pelo interessantíssimo Teorema de Löb (ou Loeb):
Se a fórmula "se C pode ser provado, então C" pode ser provada, então C pode ser provado.
Traduzindo para nosso caso:
Se pode ser provado que "se a sentença de Henkin pode ser provada, então a sentença de Henkin é verdadeira", então a sentença de Henkin pode ser provada — e é verdadeira.
Apesar da simetria com a incompleteza de Gödel, a prova do Teorema de Löb depende completamente dos teoremas de Gödel. O trabalho de Gödel tem portanto importância muito maior e não poderia ter sido precedido pelo de Löb.
Embora não haja relação direta entre o teorema fundamental da aritmética e a incompleteza de Gödel, podemos traçar um paralelo que ajuda no seu entendimento, ou pelo menos na sua aceitação como fato da vida.
Os números naturais podem ser: ou 0, ou 1, ou primos, ou compostos. Número composto é aquele que tem fatores primos e.g. 6=2×3. O teorema fundamental da aritmética garante que cada número composto só pode ser fatorado de um jeito. Fato aliás que foi muito explorado na transformação de fórmulas em "números de Gödel".
Podemos estabelecer então o seguinte paralelo: os números primos são parecidos com axiomas; eles simplesmente existem, não podem ser divididos em componentes menores. Já os números compostos são parecidos com teoremas, que podem ser esmiuçados.
Assim como existem infinitos números primos, também existem infinitos axiomas (que não podem ser provados). Se nos limitarmos a poucos axiomas, ainda assim podemos provar infinitos teoremas, mas haverá muitos outros fora do nosso alcance. Os axiomas de Peano provam muita coisa porém há verdades fora do alcance deles.
Da mesma forma, se limitarmos nosso conhecimento de números naturais a um punhado de números primos, podemos criar infinitos números compostos a partir deles, mas outros tantos ficarão fora do nosso alcance. Por exemplo, se eu restringir-me aos primos 2 e 3, posso a partir deles obter os números 4, 6, 8, 9, 12, 16, 18, etc.
Note que ainda tenho acesso a infinitos números compostos, e não seria tão mau se, por exemplo, os preços das coisas fossem todos divisíveis por 2 e/ou por 3. Nunca mais haveria falta de troco no mercado.
Porém, neste campo numérico limitado eu não posso expressar números como 10, 15, 51 ou 100, pois não conheço os números primos 5 e 17. À medida que adiciono 5 e 17 à minha lista de primos "permissíveis", tenho mais um conjunto infinito de números compostos à minha disposição.
Porém muitos outros números ainda continuam "proibidos", simplesmente porque há infinitos números primos. Então não posso estabelecer nenhuma restrição aos primos, sob pena de perder uma fatia enorme de números naturais.
Da mesma forma, há infinitos "números primos de Gödel", ou seja, axiomas que não são passíveis de prova dentro da aritmética. Uma infinitude de teoremas depende de cada um destes axiomas. A aritmética tradicional possui apenas um punhado de axiomas (os de Peano).
A comparação nos dá uma noção de quantas verdades matemáticas estão inacessíveis ao nosso entendimento.
A grande diferença — é onde esta comparação começa a azedar — é que é fácil achar números primos, pois é fácil provar a primalidade de um número qualquer. Por outro lado, achar novos axiomas para a aritmética é muito difícil, pois é complicado provar que uma afirmação matemática qualquer é a) verdadeira; b) não admite prova dentro da aritmética de Peano; c) não "quebra" a aritmética de Peano, tornando-a inconsistente.
F I M