Seminário de Teoria da Computação


    Incompletude da Aritmética Formal: a prova de Gödel 

           Guilherme Albuquerque Pinto

         Sexta-feira, 14 de março de 2003
              Sala 96 (IC2), 13:00hs


Resumo:

 Alguns livros-texto de Complexidade Computacional, ex. Papadimitriou,
 e de Computabilidade, ex. Rogers, trazem provas do teorema da
 Incompletude pela via da indecidibilidade. Quer dizer, a
 indecidibilidade de um certo problema computacional implica
 diretamente no Teorema da Incompletude. Essas provas são, em
 essência, aquelas dadas por Church e Turing, cerca de cinco anos após
 a publicação do famoso artigo de Gödel em 1931, quando ele mostrou
 que um Sistema Formal, não importa o quão expressivo, será sempre
 incompleto, nunca poderá demonstrar todas as sentenças aritméticas
 válidas.

 Não causa, claro, nenhuma estranheza que livros-texto de teoria da
 computação prefiram abordar a incompletude da aritmética pela via da
 computabilidade. Mas é de franzir a testa que o próprio Gödel tenha
 dito, uma vez, que após o trabalho de Turing o seu Teorema da
 Incompletude podia ser provado de maneira "mais satisfatória" por
 aquela via.

 O fato é que, ao contrário das provas "computacionais", a prova de
 Gödel tem mesmo algum potencial para suscitar paradoxos e para causar
 desconforto na intuição matemática do leitor. A origem desse
 potencial é o cerne da prova, a sentença aritmética $G$ que diz que
 ela própria não pode ser demonstrada. A sentença $G$ é, ao mesmo
 tempo, o fogo do céu que permitiu Gödel provar o teorema, e o pomo da
 discórdia que alimenta discussões filosóficas até hoje sobre o "real"
 significado do resultado de Gödel.

 Neste rápido seminário não iremos tratar das discussões filosóficas.  Vamos
 sim, sem medo de ser feliz, após revisar alguns conceitos sobre
 Sistemas Formais para poder enunciar o Teorema da Incompletude, ver
 como Gödel conseguiu construir a sentença $G$; como ocorre
 efetivamente a auto-referência na sentença; e como ela leva à prova
 do Teorema. Nesse caminho, vamos ver as duas ferramentas que ele usou
 e que ficaram conhecidas como o Lema da Correspondência e a Numeração
 de Gödel. Teremos também, no final, oportunidade para voltar à discussão:
 o que essa incompletude tem a ver com a nossa indecidibilidade? Incompletude
 e indecidibilidade são más ou boas notícias?