Site menu De Peano para Gödel, parte 1 de 4
e-mail icon
Site menu

De Peano para Gödel, parte 1 de 4

e-mail icon

Este artigo é dividido em quatro partes. Esta é a primeira parte.

Vou basear muito da minha prosa no livro "Gödel's proof", de Nagel & Newman, e no famoso "Godel, Escher, Bach: an eternal golden braid" de Douglas Hofstadter. Este último livro é conhecido pelo carinhoso apelido de GEB pelos nerds mundo afora.

No artigo sobre aritmética de Peano, toquei no assunto dos axiomas, ou seja, como a aritmética com números naturais é definida por um punhado de definições muito simples, os axiomas de Peano.

Veja que "axiomas de Peano", "aritmética de Peano" e "aritmética normal" que aprendemos no ensino fundamental, são basicamente a mesma coisa. A diferença é a fundamentação lógica. No meu tempo, se alguém contestasse a afirmação 2+2=4, a professora batia com a régua na cabeça :) Argumentum ad baculum.

Relembrando uma parte dos axiomas de Peano:

Número é todo objeto que possui um sucessor
     y = S(x), então x é número [a]
Não existe número cujo sucessor é zero
     não existe x tal que S(x) = 0 [b]
O sucessor de um número é outro número
     y = S(x), y é número [c]
Dois números diferentes possuem diferentes sucessores
     a ≠ b, S(a) ≠ S(b) [d]
     a = b, S(a) = S(b) [d*]
Define-se "soma" de dois números como:
     x + S(y) = S(x + y) [e1]
     x + 0 = x (elemento neutro) [e2]
Define-se "multiplicação" de dois números como:
     x . 0 = 0 [f1]
     S(x) . y = y + x . y [f2]

Axioma é uma afirmação que aceitamos sem discussão, seja por fé, ou porque é evidente, ou porque temos a intuição que é razoável.

Por exemplo, faz sentido (para nós) dizer que todo número tem sucessor, de modo que os diversos números formem uma seqüência contínua: 0, 1, 2, 3... Ou I, II, III, IV...

A notação utilizada realmente não importa. Conforme já dissemos no artigo sobre aritmética unária e Peano, o número "três" ou 3 ou III é apenas um rótulo para o terceiro sucessor de zero.

A partir dos poucos axiomas acima, podemos deduzir quase tudo na aritmética. Dá muito trabalho, assim como usar aritmética unária não seria prático. Mas o fato é que é possível, e isto nos assegura que a aritmética do dia-a-dia tem respaldo na lógica. Não há chance de chegar um extraterrestre amanhã e dizer "olha, isso aí tá tudo errado".

Vamos provar que 1+1=2. Você pode ter notado que eu rotulei os axiomas com letras entre colchetes, como [a]. Vou usar esta notação para apontar que axiomas apóiam cada passo da prova.

Primeiro, vamos provar um "lema", mostrando que x+1=S(x), estabelecendo uma relação bastante conveniente entre sucessão e soma:

S(0) = 1                 [a] 
x + 1 = x + S(0)
x + S(0) = S(x + 0)      [e1]
x + 1 = S(x)             [e2]

Agora, a soma em si:

x + 1 = S(x)		[lema]
1 + 1 = S(1)            [fazendo x = 1]
1 + 1 = 2

Podemos fazer uma prova mais direta, que não produz o lema:

1 + 1 = S(0) + S(0)          [a]
S(0) + S(0) = S(S(0) + 0)    [e1]
S(S(0) + 0) = S(S(0))        [e2]
1 + 1 = S(S(0))              [a]
1 + 1 = S(1)
1 + 1 = 2

Altamente trabalhoso, mas serve para dar um respaldo filosófico, digamos assim.

Neste ponto, se começarmos a pensar filosoficamente, começam a aparecer muitas perguntas de cunho filosófico. Por exemplo:

Peano é consistente?

Um conjunto de axiomas é dito "consistente" se ele não conduz a contradições. É mais fácil enxergar isto introduzindo deliberadamente um axioma "vilão", como 1+1=3.

Tal axioma, junto com os demais, torna a aritmética inconsistente, já que acabamos de provar que 1+1=2. Daí poderíamos deduzir que 2=3, S(2)=3 e S(2)=S(3), que conflita com o axioma [d].

Podemos continuar com este absurdo "provar" facilmente que 2=4 pois 2=3 e 3=S(3)=4. Finalmente, podemos dizer que a fórmula 1+1=x é "verdadeira" para qualquer valor de x, elevando-a ao nível de um teorema.

Segundo os logicistas, um sistema de axiomas inconsistente permite "provar" que qualquer fórmula é um teorema, ou seja, verdadeira sob quaisquer variáveis. Um sistema inconsistente permite "provar" inclusive a sua própria consistência. (É claro que tal prova não vale nada.) Esta é a marca de um sistema inconsistente.

Por outro lado, um "sintoma" de consistência de um sistema é a presença de fórmulas que não sejam teoremas. Por exemplo, a fórmula 1+1=x só é verdadeira quando x=2.

É um bom sinal, porém Gödel provou que um sistema consistente não pode provar que ele mesmo é consistente... Sistemas consistentes são forçosamente humildes.

Também a intuição nos diz que Peano parece ser consistente. Há uma prova "de verdade" da consistência de Peano (Gentzen) mas ela baseia-se na introdução de um conceito externo, novo (números ordinais), que vai além da aritmética. A aritmética "baunilha" não comporta tal prova.

Na verdade, há sistemas baseados em axiomas, consistentes, e que provam sua própria consistência, mas eles têm obrigatoriamente de ser "fracos", ou seja, com menos poder expressivo que a aritmética.

Há sistemas que foram criados deliberadamente fracos, como a aritmética de Presburger. Ela compartilha de algumas, mas não de todas características da aritmética normal. Por exemplo, nela não é possível definir o que é numero primo; mas é possível definir o que é número par ou ímpar.

A aritmética de Presburger é fraca, completa, consistente e decidível (vou esclarecer mais adiante o que é "decidível"). Ela torna-se tão poderosa quanto Peano (e deixa de ser completa e decidível) quando adiciona-se a ela a operação de multiplicação.

Axiomas "aberrantes" como extensões

Nem sempre adicionar um axioma conflitante com os demais é uma má ideia. Considere o seguinte axioma:

Existe um número z tal que S(z) = 0

A priori este novo axioma conflita com [b] (zero não sucede nenhum número natural). Mas quem falou de números naturais? Se admitirmos que z é "não-natural", o novo axioma pode conviver com os demais.

É claro, nós sabemos que z=-1, um número inteiro negativo. Este novo axioma estica a aritmética dos naturais para os inteiros. O axioma [b] permanece na função de discriminante entre números naturais e inteiros.

É possível provar teoremas "mecanicamente"?

Quanto à questão de provar teoremas usando meios automáticos, como um software de computador. Seria possível?

De fato é possível, e existem alguns softwares que fazem isto. São bastante úteis para conferir provas desenvolvidas por humanos, por exemplo. Mas esta possibilidade tem alguns limites, tanto teóricos quanto práticos.

Um limite prático é que trata-se de uma tarefa "difícil". Um teorema não-trivial pode demorar muuuuuito para ser provado, o que torna o procedimento inútil na prática. Um ser humano munido de papel e lápis tem mais chance, pois pode achar a prova do teorema por pura sorte.

É preciso tomar um certo cuidado para alimentar o software "provador" apenas com teoremas que sejam tratáveis, ou fornecer alguns "lemas" que facilitem o trabalho. Assim, o software permance útil e prova teoremas num tempo aceitável.

É prudente lembrar que verificar uma prova é diferente de elaborar um teorema (fórmula com prova). Embora ambas as atividades possam ser feitas mecanicamente, elaborar teoremas é infinitamente mais difícil.

Na verdade, elaborar teoremas é muito fácil; um computador pode cuspir zilhões deles, mas não sabe julgar quais destes teoremas são úteis, inéditos, ou elegantes. O matemático humano trabalha "ao contrário": parte de uma hipótese, ou mesmo algo observado empiricamente, e aí tenta elaborar uma prova, sabendo onde quer chegar.

O limite teórico dos programas verificadores de provas é ditado pela incompleteza de Gödel. falaremos mais deste cidadão e da sua teoria ao longo deste texto.

Gödel provou que nem toda verdade matemática é um teorema que possa ser demonstrado. Há verdades que são independentes dos axiomas de Peano.

Ou seja, a aritmética não é completa; nem todo fato da aritmética possui prova baseada na própria aritmética. A começar pelos axiomas de Peano, é claro; eles simplesmente existem, sem prova. Mas além deles, há infinitos outros.

Um possível exemplo é a conjectura de Goldbach: todo numero par é (talvez) a soma de dois primos. Todos os testes sugerem que a conjectura é verdadeira, mas ninguém provou isso, ainda.

Então, Goldbach pode ser a) um teorema cuja prova ainda não foi encontrada; b) uma verdade matemática nova, ou seja, um axioma; c) uma afirmação falsa, pois há um número par x que não é a soma de dois primos.

Supondo que de fato a conjectura de Goldbach seja verdadeira mas não possa ser provada, o que acontece? Bem, ela pode ser admitida como um novo axioma, o "axioma de Goldbach". Com a ajuda dele, muitos outros teoremas, que hoje não passam de hipóteses, passam a ser válidos.

Um computador pode ficar procurando para sempre por esta resposta, sem nunca encontrar. Esta possibilidade caracteriza o sistema como indecidível. Sistemas de axiomas mais "fracos", como a aritmética de Presburger, são decidíveis porque nestes há a certeza que "um dia" o computador achará a resposta. Existe um algoritmo para procurar a resposta e é possível calcular quanto tempo ele vai levar. (Lembra que eu prometi lá em cima a esclarecer o que era "decidível"? Aí está.)

(Note que o problema prático que mencionamos antes — que o algoritmo pode demorar um tempo inaceitavelmente longo — continua existindo para sistemas decidíveis.)

Este artigo é dividido em quatro partes. Esta é a primeira parte. Clique aqui para abrir a próxima parte..

e-mail icon