Gödel para iniciantes, parte I

por Julio Lemos

Talvez alguns dos leitores tenham ouvido falar -- talvez com horror -- do famoso teorema da incompletude de Kurt Gödel, publicado em seu artigo "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" em 1931. A prova é longa e difícil: é necessário que o leitor domine dezenas e dezenas de definições apenas para começar a trabalhar com ela. 

Mas Raymond Smullyan dá uma idéia da prova de Gödel que me pareceu, até agora, a mais acessível.

Basicamente, o ponto é que um sistema formal pode decidir sobre muitas coisas... exceto sobre certas afirmações sobre ele mesmo. E se pudéssemos traduzir, em uma sentença lógica, a idéia de que ela mesma não pode ser provada, como que a dizer "eu sou indemonstrável"? Essa é a intuição de Gödel, que lembra antigos paradoxos.

Pense num computador ligado a uma impressora. Ele pode imprimir os seguintes desenhos, no total de cinco:

~ P N (  )

Podemos formar, com esses símbolos (mas nunca com 0 símbolos), uma expressão. Agora prestem atenção nas seguintes definições.

Uma expressão X é imprimível (a palavra não existe no português, mas vocês entenderam, não?) pelo computador caso possa ser impressa.

Chamaremos norma da expressão X uma expressão do tipo X(X). Por exemplo: P(P).

Pensando em X como qualquer expressão, temos uma sentença caso ela tenha uma das seguintes formas: (a) P(X); (b) PN(X); (c) ~P(X); (d) ~PN(X).

Agora vamos assumir que P significa "imprimível", N "norma de" e ~ "não". E definimos que P(X) é verdadeiro sse (se e somente se) X pode ser impresso. Por conseguinte, ~P(X) será verdadeiro sse X não é imprimível. O mesmo, mutatis mudandis, no que diz respeito a PN(X) e ~PN(X).

O leitor deve ter adiantado que nosso computador revela informações sobre seu próprio funcionamento: ela imprime sentenças que dizem o que ela pode e o que não pode imprimir...

Se o computador imprimir P(X), saberemos que X é imprimível. É o que diz a sentença. Se imprimir PN(X), saberemos que N(X) é imprimível (portanto verdadeira).

Mas com isso podemos dizer que o computador pode imprimir todas as sentenças verdadeiras? Só sabemos que ele não imprime sentenças falsas.

A resposta é não. Exercício para o leitor: saberá ele dar um exemplo de uma sentença certamente verdadeira, mas que o computador não possa imprimir?

A solução dá uma boa idéia sobre a prova de Gödel. Os que não souberem, que aguardem o próximo post!