De Peano para Gödel, parte 3 de 4
De Peano para Gödel, parte 3 de 4
Este artigo é dividido em quatro partes. Esta é a terceira parte. Clique aqui para retornar à parte anterior.
Ao longo dos séculos, diversos paradoxos fizeram os logicistas coçar a cabeça. Sempre houve alguma desconfiança quanto à possibilidade de um sistema de axiomas ser completo.
Há uma velha anedota sobre um general romano que foi feito prisioneiro pelos bárbaros. Estes sempre matavam os prisioneiros, mas permitiam ao condenado fazer uma última declaração. Se fosse verdadeira, morria rápido, decapitado. Se fosse falsa, morria na cruz, bem devagar.
Pois bem, o tal general afirmou então como última frase: "Eu vou morrer crucificado". É fácil ver o paradoxo a que isto conduz. Os bárbaros acabaram libertando o general, na falta de melhor opção.
Se fosse um general português, provavelmente ia afirmar "Eu vou morrer decapitado", aí de fato seria decapitado e morreria com uma verdade na boca... O paradoxo depende de dois ingredientes para existir: auto-referência e negação.
Podemos conceber uma frase paradoxal ainda mais simples, sem conotações anedóticas:
ESTA FRASE É FALSA.
Se ela é de fato falsa, então afirma uma verdade, portanto é verdadeira. Se é de fato verdadeira, então afirma uma mentira, portanto é falsa. Se é verdadeira e falsa ao mesmo tempo, então é indecidível.
Por completeza, vamos analisar o exemplar "português" da frase-paradoxo:
ESTA FRASE É VERDADEIRA.
Esta frase compartilha duas características com a outra: referencia-se a si mesma e não contém informação útil. Mas não há dúvida que ela é verdadeira.
Mas isto são apenas jogos de palavras. Recriar este paradoxo dentro da matemática dá um pouco mais de trabalho. Um grande marco foi estabelecido por Georg Cantor, com seu "argumento diagonal". O passo seguinte foi dado por Jules Richard, com seu "Paradoxo de Richard".
Richard propôs o seguinte: atribuir um código numérico a cada predicado. Lembra dos predicados? São teoremas que definem conjuntos de números, finitos ou infinitos. Exemplos: números pares, números primos... Um predicado pode até definir um conjunto unitário; apenas o número 2 atende ao predicado "números primos pares".
Todo teorema e predicado pode ser expresso por uma quantidade finita de símbolos, sejam aqueles símbolos matemáticos esquisitos, seja o alfabeto comum. Com base neles, podemos atribuir um rótulo ou código a cada predicado, assim como cada produto no supermercado tem seu código de barras.
Vamos supor que, no sistema hipotético de numeração que tenhamos escolhido, o predicado "número par" E(x) receba o número 710, o predicado "número ímpar" O(x) receba o código 1010, e o predicado "número primo" P(x) receba o código 95332.
Agora, vamos definir um predicado novo, o "Richardiano", ou R(x). O código deste novo predicado é 34567. Um número é richardiano quando não atende ao predicado de mesmo número. Confuso? Vamos exemplificar.
O número 710 está relacionado ao predicado E(x): número par. Como 710 é par, E(710) é verdadeiro. O número 710 atende ao predicado 710, portanto ele não é um número richardiano.
Já o número 1010 está relacionado ao predicado O(x): número ímpar. A fórmula O(1010) é falsa, porque 1010 não é ímpar. Portanto, 1010 é richardiano.
Agora, a perguntinha sacana: o número 34567 é richardiano? Esta pergunta leva a uma contradição, porque:
Ou seja, 34567 é ao mesmo tempo richardiano e não-richardiano, o que torna o problema indecidível.
Novamente, foi a negação que causou o paradoxo. Vejamos agora o "Paradoxo de Manuel", desenvolvido por Manuel, um matemático português.
Assumindo o mesmo sistema de codificação de Richard, um número é Manuelino B(x) quando atende ao predicado de mesmo número. O código de B(x) é 55555. Neste caso:
Não há paradoxo: todo número é decididamente manuelino ou não-manuelino. Mas há um detalhe residual interessante: ficamos sem saber se 55555 é manuelino ou não. Eu chutaria que ele é; mas a definição de B(x) parece insuficiente, porque nem nos permite concluir sobre o número 55555, e tampouco produz contradição.
Assim como o paradoxo de Richard desemboca no trabalho de Gödel, o "paradoxo de Manuel" também tem um análogo na lógica: as "sentenças de Henkin", que revisitaremos no final da série de artigos. (A propósito, provou-se que as "sentenças de Henkin" provam a si mesmas, o que sugere que o número 55555 é sim manuelino.)
O Paradoxo de Richard tem um erro fatal de lógica: mistura matemática com meta-matemática, ou seja, a descrição de objetos matemáticos em linguagem "superior".
O paradoxo de Richard, para ser válido, precisaria apresentar uma fórmula aritmética para R(x) — assim como há fórmulas para determinar se um número é par, ímpar, primo etc. Sem fórmula aritmética, o predicado R(x) não pode jogar no mesmo campo que os demais.
Outro paradoxo do gênero, divulgado por Bertrand Russell, envolve a seguinte expressão:
O menor inteiro positivo com definição mínima em onze palavras.
O paradoxo advém do fato da frase acima ter apenas dez palavras, mas está definindo um número que, segundo ela, precisa de no mínimo onze palavras. O erro de lógica aqui advém da ambiguidade da palavra "definição".
Mesmo com estes paradoxos a assombrar a lógica, os matemáticos e logicistas ainda achavam que a aritmética poderia ser tornada completa, com todas as verdades matemáticas conhecidas e desconhecidas fundadas nos axiomas de Peano.
Sendo assim, o mesmo Bertrand Russell engajou-se num projeto denominado Principia Mathematica, costumeiramente abreviado para PM. O PM pretendia construir uma base lógica indestrutível para a matemática. Não é exatamente um livro didático; ele usa símbolos extensivamente e demora trezentas páginas para provar que 1+1=2.
Assim como Marx achava que o comunismo desligaria o "motor da história", os autores do PM achavam que o fim da matemática estava próximo. Cedo ou tarde, seria construída alguma máquina que produziria teoremas por atacado...
Aí veio Kurt Gödel, e provou que o PM nunca poderia ser um sistema completo, que sempre haveria verdades novas e sem prova dentro do PM.
Estas verdades sem prova não são apenas uma previsão. Diversas delas já foram achadas: teorema de Goodstein, teorema de Paris-Harrington etc. São teorias altamente "viajonas", mas existem. E há a conjectura de Goldbach, que por enquanto é apenas candidata ao posto.
Gödel estendeu sua prova de incompleteza para "sistemas relacionados" ao Principia Mathematica. Ou seja, a incompleteza não vale apenas para a aritmética de Peano. Ela vale para qualquer sistema baseado em axiomas suficientemente poderoso.
Aqui entra o conceito de isomorfismo entre sistemas. Dois sistemas são isomórficos quando, apesar de diferentes, possam ser "mapeados" um no outro.
Por exemplo, geometrica e álgebra são isomórficos. Tudo que pode ser expresso pela geometria, pode ser expresso também pela álgebra, e vice-versa.
A prova da incompleteza de Gödel em si segue a picada aberta pelo paradoxo de Richard.
Em primeiro lugar, Gödel estabeleceu um método à prova de bala para atribuir códigos únicos a cada axioma, teorema, predicado, e prova de teorema. São os "números de Gödel".
Cada símbolo elementar ganha um número:
01: S (função sucessora) 02: 0 (zero) 03: + (adição) 04: = (igual) 05: ⊃ (relação de implicância "se... então...") 06: ∃ (existe) 07: ~ (negação) 08: | (ou) 09: ( (abre parênteses) 10: ) (fecha parênteses) 11: , (vírgula) 12: x (multiplicação)
Já as variáveis numéricas (x, y etc.) são codificadas como números primos a partir de 13.
As variáveis sentenciais (que representam fórmulas lógicas, não números) são codificadas como quadrados de primos a partir de 13 (ou seja, começam em 169).
Os predicados são codificados como cubos de primos a partir de 13 (ou seja, 2197).
As fórmulas em si são codificadas fazendo uso do teorema fundamental da aritmética: pega-se cada primo, começando de 2, e eleva-o à potência correspondente ao símbolo.
Vamos ver qual seria o número de Gödel para uma expressão bem simples, utilizando o esquema que acabamos de descrever:
0 = 0 <-- fórmula 2 4 2 <-- códigos dos símbolos elementares da fórmula 2² . 3⁴ . 5² 2 . 2 . 3 . 3 . 3 . 3 . 5 . 5 8100
Para recriar a fórmula a partir do número de Gödel, basta fatorar 8100. O resultado é 2.2.3.3.3.3.5.5. Temos 2 dois, 4 três e 2 cincos, então os símbolos originais eram 2 4 2 e a fórmula era 0=0.
Como só existe um jeito de fatorar cada número natural, podemos ter absoluta confiança que diferentes fórmulas têm de ter diferentes números de Gödel.
A fórmula 0=0 é uma verdade, mas poderíamos ter calculado o número de Gödel para 0=1 ou 1=2. As "mentiras" matemáticas também têm seus números de Gödel...
Podemos ainda calcular o número de Gödel de um simples número. A tabela de símbolos que definimos antes não contempla números maiores que zero, então precisamos usar a função sucessorra para expressar números positivos. Por exemplo, "três" vira "o terceiro sucessor de zero":
3 SSS0 1 1 1 2 2¹ . 3¹ . 5¹ . 7² 1470
Disto resulta a curiosa conclusão de que o número 3 tem um número de Gödel igual a 1470! Cada número natural tem um G relacionado, inclusive o zero: G("0")=22=4.
A prova de um teorema é codificada de forma semelhante:
e = número de Gödel do teorema a, b, c, d = números de Gödel dos passos que demonstram "e" Número de Gödel da prova, ou demonstração, do teorema "e": 2 ** a . 3 ** b . 5 ** c . 7 ** d . 11 ** e
Certamente a demonstração de qualquer teorema trivial vira um número gigantesco, mas é perfeitamente calculável.
Note que usamos potências de primos de novo, sendo que os teoremas a, b, c, d, e já são números de Gödel calculados com base em potências de primos.
Mas isto não causa ambiguidade, porque ao fatorar uma prova, descobre-se logo que as potências a, b, c, d, e têm valores muito altos e não são primas, então não podem ser símbolos elementares; têm de ser fórmulas.
Neste momento, precisamos parar para lembrar de um detalhe. Não há nada especial com o dicionário de símbolos que escolhemos, nem com o esquema de codificação! Se preferíssemos, poderíamos expressar todas as fórmulas em bom português.
Neste caso, atribuiríamos um valor para cada letra de A a Z e mais alguns caracteres de pontuação, símbolos de aritmética, e o número zero. Os números de Gödel acabariam muito maiores, mas a idéia original (transformar fórmulas em números) continua a mesma.
O único detalhe é que as variáveis precisam ter códigos distintos dos símbolos alfabéticos. A letra A do alfabeto, a variável a e o predicado A(x) devem ter códigos distintos.
Por quê? Na hora de interpretar uma fórmula, precisaremos substituir variáveis por valores. Se não acredita, suponha a frase-fórmula "x é igual à adição de a com b". Substituindo a por 5, ficaria: "x é igu5l 5 5diç5o de 5 com b", o que é obviamente errado. Apenas um único a da frase deveria ter sido trocado. Coisas análogas acontecem também na linguagem humana, e é por isso que existem aspas, negritos, itálicos, etc.
Estes procedimentos trazem a lógica para dentro da matemática porque permitem analisar fórmulas e teoremas usando simples aritmética, assim como um software pode analisar outro, dentro de certos limites.
Por exemplo, para detectar se uma fórmula começa com o símbolo S (função sucessora), podemos pegar o respectivo número de Gödel G e verificar se G÷2 é ímpar.
Por quê? Porque, se o primeiro símbolo da fórmula era S, os fatores primos de G incluem 21. Dividindo por 2, sobram apenas primos diferentes de 2, e G÷2 tem de ser ímpar. Assim, o que seria uma análise lógica passa a ser uma conta de padeiro.
Note que, segundo a primeira codificação que sugerimos, toda fórmula possui número de Gödel par, pois sempre há potência de 2 na sua composição. Apenas símbolos isolados têm número ímpar.
Por último, devo mencionar que hoje em dia o esquema dos "números de Gödel" não parece grande coisa, simplesmente porque estamos mais acostumados a transformar tudo em números. Um texto que digitamos no computador vira um arquivo, que é uma longa sequência de números, ou seja, um grande número inteiro.
O mesmo acontece com uma planiha ou um software qualquer. Quando você faz uma planilha, você está sistematizando um procedimento. Salvar uma planilha num arquivo equivale a calcular e gravar o número de Gödel daquele procedimento. Felizmente é o computador que faz isso por nós :)
Um problema mais filosófico: será que os símbolos de matemática e lógica que enumeramos mais acima, realmente significam alguma coisa? Será que eles merecem as definições que lhes atribuímos? A possibilidade de codificar símbolos e fórmulas como simples números é mais um tempero nesta discussão.
Gödel também trabalhou nesta questão, e demonstrou que de fato os símbolos, as regras de "sintaxe" para construção de fórmulas, mais os axiomas, permitem chegar a um número infinito de teoremas, que por sua vez têm respaldo no mundo real.
É uma discussão que já levantei no artigo sobre axiomas de Peano: a rigor, o número 2 não significa nada, e a expressão 1 + 1 = 2 é vazia.
Mas até mesmo uma criança pequena sabe que dois chocolates é melhor do que um. É um na boca e outra na mãozinha, esperando para ser degustado em seguida. Você acha adultos analfabetos com relativa facilidade, mas é impossível achar alguém que não saiba contar dinheiro. Humanos e primatas rejeitam instintivamente a desigualdade social, mas igualdade pressupõe divisão igualitária, que vai ao encontro da definição aritmética de divisão.
É uma demonstração empírica que a evolução da vida nos deu uma noção intuitiva de número e aritmética, que coincidem com os axiomas de Peano, em particular aquele que fixa o valor de "zero" como sendo "nada". Um ser humano com problemas mentais, que por algum motivo pense que zero tem valor intrínseco, vai passar maus bocados. Se comer zero calorias, vai morrer de fome.
Este artigo é dividido em quatro partes. Esta é a terceira parte. Clique aqui para abrir a próxima parte.