Re: [obm-l] Indecidibilidade(O que sao PA e ZFC?)

O que sao PA e ZFC?

ronaldogandhi@ig.com.br wrote:

>Desculpe, mas acho que esta sua explicação do que é uma
>questão indecidível confunde mais do que esclarece.

Tem toda razão, eu preciso ler mais sobre isso.
Mas nada que um bom professor (como vc) não
possa esclarecer. Fiz uma pesquisa no Google e
encontrei essa mensagem sua bastante interessante:

http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.200008/msg00240.html

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

Pelo que eu entendi, abaixo
vc deu um exemplo abaixo de uma proposição que é
indecidível em PA mas que é decidível
e verdadeira em ZFC:

>Um exemplo de afirmativa sobre naturais verdadeira em ZFC
>mas não demonstrável em PA é uma versão do teorema de Ramsey.
>Teorema de Ramsey finito forte:
>Dados naturais n, m e l então existe N tal que se X =
>{0,1,2,...,N-1} e |Y| = m então toda função f: X^[n] -> Y
>admite um subconjunto homogêneo Z relativamente grande
>com pelo menos l elementos.
> O teorema de Ramsey forte acima não pode ser demonstrado
>na aritmética de Peano apesar de ser facilmente
>demonstrável fazendo uso de conjuntos infinitos.

Essa é frase 'G' que você citou no e-mail
anterior, certo? Vc também citou a hipótese do
Contínum que não é demonstrável em ZFC:

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

A dúvida apareceu é se existe algum sistema no qual
a hipótese do contínum seja demonstrável. Se não é
possível demonstrá-la nem em PA e
nem em ZFC, existe algum outro sistema no qual
ela seja demonstrável?
Ou teríamos que considerá-la verdadeira (axioma)
e construir outro sistema a partir dela?
Desculpe se isto estiver indo meio off-topic...
ou dizendo bobagens. Eu realmente tenho muitas
dúvidas...

>Para isso é preciso 'emular' a lógica
>dentro da aritmética, um processo um pouco trabalhoso.

Vou dar uma olhada no livro de Gödel para tentar
entender como isso é feito... parece interessante.

[]s
Ronaldo L. Alonso

_________________________________________________________
Voce quer um iGMail protegido contra vírus e spams?
Clique aqui: http://www.igmailseguro.ig.com.br
Ofertas imperdíveis! Link: http://www.americanas.com.br/ig/

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