[obm-l] Indecidibilidade

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Thu, Mar 04, 2004 at 11:06:02AM -0300, ronaldogandhi@ig.com.br 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
=========================================================================