terça-feira, 2 de março de 2010

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
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.


6 comentários:

  1. Descobrir qual é a pergunta formal cuja resposta é 42 realmente será de muita relevância para a humanidade. :P

    Vamos torcer para que o universo seja finito, hehehe.

    ResponderExcluir
  2. Sandi,

    foi uma das exposições mais claras que já vi sobre o afamado teorema! Você está treinando para escrever uma tese ou coisa do tipo? =) Mas o ponto mais alto foi a frase conclusiva: "a matemática, não é algo finito, muito menos uma mera construção da mente humana." (é de arrepiar pensar sobre isso =).
    Você sabe, hoje em dia os físicos-teóricos trabalhando em supercordas tem proposto a existência de multiversos (um conjunto infinito de universos, cada um deles, provavelmente finito).
    Assim, cada um ainda poderia ser matematicamente bem descrito ... mas talvez não o Universo (no sentido matemático) dos universos (físicos).
    Posso pedir seu email de contato? O meu é frigori AT utfpr DOT edu DOT br (em notação anti-spam, hehe). Obrigado!
    Continue o belo trabalho... Até +
    Rafael

    ResponderExcluir
  3. heheh Obrigada Rafael! A exposição foi mais superficial do que eu gostaria, mas este é apenas um blog... =)

    Quanto à conclusão, realmente. O trabalho de Gödel parece indicar esse tipo de conclusão, mas esse assunto é bastante delicado, e Gödel parece não ter sido muito cuidadoso em alguns pontos no desenvolvimento de seu teorema, o que aumenta a possibilidade da existência de bugs nas conclusões (formalmente falando). Mesmo assim, a conclusão filosófica parece válida, e sugere que a matemática é mais básica que a física (o que, filosoficamente, parece lógico)...isso realmente é assustador =)

    A respeito das supercordas e dos multiuniversos eu sei pouco, embora tenha lido uma ou outra coisa a respeito...
    A idéia dos multiuniversos parece bastante interessante. Parece realmente lógico que não seja possível descrevermos completamente todos os universos, pois mesmo que eles não existam de fato, as infinitas possibilidades existem...

    Eis o meu e-mail: sandiflutz AT gmail DOT com

    Obrigada pelo comentários sempre muito relevantes!
    Até mais

    ResponderExcluir
  4. Oi Sandinha

    Não entendi muita coisa quando explicaste os símbolos. Mesmo assim gostei do que eu entendi. O que me ajudou a entender um pouco foi aquele trabalho de conclusão que eu fiz para o Pira.

    Beijo

    ResponderExcluir
  5. Sis, achei muito bom esses posts, bem didáticos, na minha opinião. Gostei bastante do resumo que tu fez. =)

    Aline F. L. W.

    ResponderExcluir