On Thu, Mar 04, 2004 at 11:06:02AM -0300, [EMAIL PROTECTED] wrote: > Isso que vc citou é o famoso teorema da incompletude de > Gödel que afirma que existem proposições e problemas > indecidíveis na matemática (que não podem ser > provadas nem negadas). > Exemplo de uma tal proposição: > > Teorema X: O teorema X não pode ser demonstrado. > Questão: Demonstre o teorema X. > > A questão acima é indecidível. A metamatemática lida > com questões do tipo acima.
Desculpe, mas acho que esta sua explicação do que é uma questão indecidível confunde mais do que esclarece. Uma proposição é indecidível quando nem ela nem a sua negação seguem dos axiomas da teoria (que podem ser dados explicita ou implicitamente). Mas uma proposição é algo claro, sem autoreferências explícitas, como no seu exemplo. A hipótese do contínuo diz que se X é um subconjunto infinito de R então ou existe uma bijeção entre X e N ou entre X e R. Ela é um exemplo de proposição indecidível em ZFC: isto significa que com os axiomas de ZFC não é possível nem demonstrar nem refutar a hipótese do contínuo. Outro exemplo é dado por máquinas de Turing. Uma máquina de Turing é uma espécie de computador idealizado que vai fazendo um monte de operações e que pode parar em tempo finito ou não. O problema da parada consiste em reconhecer (de forma algorítmica) quais máquinas de Turing param e quais não (não se exige uma *demonstração* de que o algoritmo funciona, só o próprio algoritmo) e Turing demonstrou que não existe um tal algoritmo. O que isto prova é que *qualquer* que seja o nosso conjunto de axiomas, desde que ele seja recursivamente enumerável (isto é, desde que exista um algoritmo que cospe todos os axiomas e *apenas* os axiomas), sempre existirão máquinas de Turing x para as quais a proposição "a máquina de Turing x para em tempo finito" é indecidível. Veja aliás http://www.research.att.com/~njas/sequences/Seis.html para ver como são pequenas e simples as máquinas de Turing para as quais ninguém sabe se elas param ou não. O que você parece ter em mente é o exemplo original de Gödel de uma proposição indecidível em PA (aritmética de Peano). O exemplo de Gödel é uma frase G, bem explícita e bem complicada, que fala de números naturais: ela não fala de proposições serem verdadeiras ou falsas, demonstráveis ou refutáveis. É só usando o processo de encodificar a lógica de primeira ordem na aritmética de Peano, criado também por Gödel, que vemos que G pode ser traduzida como "G não é demonstrável em PA". Assim vemos que G é verdadeira mas não é demonstrável em PA. Existem outros exemplos de frases sobre números naturais que são sabidamente verdadeiras e sabidamente não demonstráveis em PA: a demonstração de que a frase é verdadeira é feita em outra teoria, claro, por exemplo em ZFC. Tem um exemplo de uma versão forte do teorema de Ramsey (sobre o qual falamos muito recentemente) que é assim: a coisa está descrita com detalhes no último artigo do Handbook of Mathematical Logic. []s, N. ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================