42 Parte II: Gödel

Dando continuidade à série de postagens (iniciada aqui) vamos agora analisar questões referentes ao teorema da incompletude de Gödel. A idéia é discutir alguns detalhes de seu trabalho nessa área, deixando de lado a contextualização histórica (sintam-se livres para perguntar ao grande oráculo =) ). Para maiores detalhes é aconselhável buscar literaturas a respeito, de preferência com o mínimo de filosofia possível e máximo de fórmulas (livros filosóficos sobre esse assunto são beeem comuns, há grandes chances de que eles não sejam um bom ponto de partida).

De maneira geral, o trabalho de Gödel consistiu em provar que existem sistemas formais indecidíveis: sistemas que contêm teoremas cuja afirmação ou negação não pode ser provada dentro desses sistemas. O desenvolvimento do teorema da incompletude foi grandemente baseado em conceitos provenientes do Principia Mathematica(PM, este livro é excencialmente um livro de filosofia matemática), de Russel e Whitehead, assim como nos axiomas da Aritimética, de Peano, escritos com base na lógica do PM.

Um ponto-chave para que possamos entender em que consistiu o trabalho de Gödel é a questão da notação empregada, sendo também algo bastante peculiar ( já ouvi dizer que Gödel tinha uma visão "ortogonal" à sociedade, isso fica bem claro quando nos deparamos com sua notação, às vezes quase invertida em relação ao que esperaríamos "logicamente" =p ).  Dentre os símbolos utilizados vemos os símbolos básicos (constantes e variáveis), as classes de símbolos básicos (fórmulas, por exemplo), as classes de classes de símbolos básicos (classes de fórmulas, por exemplo),..., e símbolos utilizados para descrever conceitos externos ao sistema.  Esses conceitos externos são chamados por Gödel (assim como por uma série de outros autores, e originalmente por Hilbert) de conceitos "metamatemáticos". Essa expressão me parece um tanto quanto infeliz por atribuir à matemático um sentido tremendamente restrito (no contexto do trabalho de Gödel essa expressão sugeriria que a matemática refere-se apenas à aritimética). Sendo assim, utilizarei simplesmente a expressão "conceitos externos". Entre os símbolos básicos constantes podemos encontrar os seguintes: "~" (negação, embora às vezes seja utilizado para indicar equivalência), "f" (sucessor imediato), "V" (ou). Quanto às variáveis, há uma infinidade (literalmente) de tipos. As variáveis do primeiro tipo são elementares (representam números naturais), as variáveis do segundo tipo são classes de variáveis elementares, e assim sucessivamente. Entre os símbolos utilizados para representar conceitos externos encontramos o conceito de prova (símbolo "B"), o qual é utilizado da seguinte maneira:

xBy

isso é, x é uma prova (seqüência de passos necessários, a partir dos axiomas, à obtenção) da fórmula y. Nessa mesma linha encontramos:

Bew(y)

ou seja, y é uma fórmula provável (y pode ser provada), isso é equivalente a dizer que existe um x tal que x é uma prova de y:

Bew(y)=(Ex)xBy

conforme a notação de Gödel. Outro conceito fundamental é o de generalização, simbolizado por  "Gen" e utilizado da seguinte maneira:

v Gen a 

isso é, a classe de símbolos a é genérica em relação à sua variável livre v.  Intimamente relacionado a este último conceito encontramos o conceito de substituição, simbolizado por Sb (ou Subst, ou ainda Su, com algumas variações na notação), o qual será visto mais à frente. 

Outro ponto importante, um dos pontos centrais no  desenvolvimento do teorema de Gödel, diz respeito a um mapeamento entre os símbolos utilizados e os números naturais, ou seja, cada símbolo ou conjunto de símbolos poderia ser representado por um número natural, de acordo com determinadas regras.

Feitas essas considerações, vamos agora analisar sequencialmente o desenvolvimento do teorema de Gödel.  Os axiomas da Aritimética (de Peano) foram tomados como ponto de partida. A fim de utiliza-los de maneira eficiente para os  dados propósitos, Gödel os escreveu de acordo com conceitos provenientes do PM, dentre outras fontes. Propôs então um mapeamento entre a simbologia utilizada e os números naturais. Em seguinda definiu o conceito de recursividade (eis um exemplo de recursividade). Lançou então quatro proposições referentes a este conceito (cujas provas foram apresentadas ou indicadas). A partir dos conceitos de recursividade e dos axiomas em si, Gödel gerou uma série de definições, contidas em 46 fórmulas. Nessa série de fórmulas pode-se ver o uso do conceito de "herança", ou seja, uma dada fórmula pode aproveitar definições de fórmulas anteriores. O próximo passo consistiu em lançar uma quinta proposição, referente a relações recursivas. Como exemplo de relação recursiva (conforme a definição de Gödel) podemos citar a relação "sucessor imediato", dada por f: 

2= f1= ff0

 Gödel então definitiu o que ele chamou de "sistema w-consistente". Segundo essa definição, um sistema w-consistente é um sistema que não possui uma classe a para a qual a seguinte proposição é válida:

Na expressão acima o símbolo Flg(k) representa o menor conjunto de fórmulas que contém todos os axiomas e todas as fórmulas de k e é fechado no que diz respeito à relação "conseqüência imediata de" (k é uma classe de fórmulas). O símbolo Sb representa o conceito externo substituição (conforme mencionado anteriormente), essa fórmula indica a substituição da variável v, em a, pela variável de mesmo tipo z(n) (símbolo correspondente ao número natural n, de acordo com o mapeamento de Gödel). A expressão acima diz que existe um n tal que a fórmula resultante da substituição de v por z(n), em a, está contida em Flg(k), e a negação da generalização de a em relação a v também está contida em Flg(k).

Gödel, adimitindo a consistência do sistema, propôs então que para toda a classe de fórmulas k, recursiva e w-consistente, sempre haverá uma classe r (classe de símbolos, fórmula), tal que nem a fórmula "v Gen r", tampouco a fórmula "Neg(v Gen r)" (Neg indica negação) pertencem a Flg(k) (ou seja, essas fórmulas não podem ser provadas dentro do sistema k).Dentre outras proposições (referentes a aplicação dos seus resultados à aritimética), Gödel provou ainda que, para uma dada classe de fórmulas k, recursiva e consistente, a proposição que estabelece a sua consistência/inconsistência pode  ser indecidível (o que não se aplica a todos os possíveis k's).


Há quem conclua que estes resultados indicam a incompletude da matemática. O que vemos porém é o seguinte, Gödel desenvolveu uma estrutura finita para lidar com um número infinito de elementos (um número finito de axiomas, os quais se referem aos números naturais e às possíveis operações entre eles). Nesse caso, um número infinito de proposições podem ser provadas formalmente. No entanto, sempre restam proposições não contidas no sistema. Esse resultado sugere que estamos tentando representar algo infinito (a aritimética) através de uma estrutura finita: por mais que adicionemos axiomas ao nosso sistema sempre haverá proposições indecidíveis, pois essa estrutura finita não é capaz de conter todas as informações referentes ao que ela pretende representar. Sendo assim, parece mais sensato supor que a aritimética, e conseqüentemente a matemática, não é algo finito, muito menos uma mera construção da mente humana.

 Mas será que podemos aplicar os resultados de Gödel à física? ou seja, seria impossível desenvolvermos uma "Teoria do Tudo" ? Isso depende. Se o universo for infinito (estrutura não necessariamente quantizada), os resultados de Gödel poderiam ser aplicáveis, desde que se conseguisse um mapeamento adequado. Se o universo for finito, no entanto, os resultados não podem ser aplicados, pois a estrutura de Gödel trata de um número infinito de elementos, o que impossibilita o mapeamento. 

Conclusão: se o universo for finito de fato, é possível que um dia encontremos a tal Teoria do Tudo, e quem sabe possamos então descobrir qual é a pergunta formal cuja resposta é 42... =p

ps: o título do paper de Gödel é "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I". Existe uma série de livros os quais são traduções desse paper (não completas, em geral), com comentários adionais. Um deles é o "On Formally Undecidable Propositions of Principia Mathematica and Related Systems", publicado pela Dover Publications.