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

2004-03-17 Por tôpico Nicolau C. Saldanha
desculpem a demora em responder...

On Fri, Mar 05, 2004 at 02:55:31PM -0300, Johann Peter Gustav Lejeune Dirichlet wrote:
> O que sao PA e ZFC?

PA = Aritmética de Peano.

São os axiomas de Peano, mas não exatamente da forma como você
provavelmete já viu. O que aparece, para citar o primeiro exemplo
que me vem na cabeça, no livro de Análise, vol 1, do Elon (proj Euclides)
é um sistema de axiomas que supõe que você já sabe anteriormente
o que é um conjunto (ou que você estudou teoria dos conjuntos antes,
ou que você tem uma idéia intuitiva do que seja teoria dos conjuntos
e aceita tomar isso como ponto de partida). Isso é satisfatório
para um livro de análise mas não é satisfatório se você for estudar lógica.

A razão crucial para isso é que o último axioma é, a menos de pequenas
mudanças:

  Para todo *subconjunto* X de N, se:
   * 0 pertence a X,
   * para todo n, se n partence a X então s(n) também pertence a X,
  então X = N.

Aqui s(n) denota o sucessor de n, mais conhecido como n+1.
Isto não é uma frase sobre números naturais, é uma frase sobre conjuntos.
Mais tecnicamente, isto não é uma frase em lógica de primeira ordem
numa linguagem em que os únicos objetos são os números naturais.

A mesma coisa vale para os axiomas de corpo ordenado completo que você
encontra no mesmo livro. Os axiomas de corpo ordenado estão em lógica
de primeira ordem (só falam de números, ou, mais importante, só *quantificam*
sobre números). O último axioma, que diz que o corpo ordenado é completo,
foge deste padrão:

  Para todo *subconjunto* X de R, se X é não vazio e limitado,
  então existe um número m [o supremo de X] com as seguintes propriedades:
   * para todo x, se x pertence a X então x <= m;
   * para todo eps > 0 existe x em X com x > m - eps.

Novamente quantificamos sobre conjuntos.

Recapitulando, então, quando um lógico fala de PA ele não topa tomar
como intuitivamente entendida uma teoria tão forte quanto a teoria
dos conjuntos. Seria meio contraditório: na teoria dos conjuntos podemos
construir os naturais: 0 = {}, 1 = {0}, 2 = {0,1}, ... Então não precisamos
propriamente de axiomas novos, estamos estudando um objeto construido
muito explicitamente e cujas propriedades podem ser demonstradas (espera-se)
a partir dos axiomas da teoria dos conjuntos.

Depois de toda esta longa explicação do que PA não é, finalmente
uma explicação do que PA é. A linguagem tem os símbolos:

 0, s, +, *, =

além da lógica de primeira ordem usual:
 
 não, e, ou, para todo, existe

e parêntesis, claro. (Se ... então ...) e (... se e somente se ...)
podem ser reescritos usando 'não', 'e' e 'ou'. Mais adiante vou usar
um 'implica', mas você pode entender isso como uma abreviação.
Não é preciso um axioma que diga

 0 é um natural.

Primeiro, pq falta a palavra "natural". Aliás, falta até a palavra "é".
Segundo, pq *todo* objeto nesta teoria vai ser um natural. Os axiomas serão
mais ou menos o que você deve esperar:

 (para todo n)(não (s(n) = 0))
 (para todo n)((n = 0) ou (existe m)(s(m) = n))

e por aí vai. Você precisa de axiomas para explicar como funcionam + e *:

 (para todo n)(n + 0 = n)
 (para todo n)(para todo m)(n + s(m) = s(n + m))
 (para todo n)(n * 0 = 0)
 (para todo n)(para todo m)(n * s(m) = (n * m) + n)

Não vou tentar dar a lista completa dos axiomas, acho que você pegou a idéia.
Finalmente, o "quinto" axioma de Peano (indução), não é *um* axioma,
é uma família infinita de axiomas. Para cada frase f(n) com uma variável
livre n temos um axioma diferente:

 ((f(0)) e ((para todo n)(f(n) implica f(s(n) implica
 ((para todo n)(f(n)))

A primeira reação pode ser a de que esta linguagem é pobre demais.
Como vamos dizer, por exemplo, que n é primo? Assim:

 (para todo l)(para todo m)(l*m = n implica ((l = 1) ou (m = 1)))

onde 1 é uma abreviação para s(0). Como vamos dizer que n é uma potência
de 2? Assim:

 (para todo l)(para todo m)(l*m = n implica ((m é primo) então (m = 2)))

onde 'm é primo' é uma abreviação para a primeira frase e, obviamente,
2 é uma abreviação para ss0. É bem mais difícil dizer que n é uma potência
de 6, mas o fato é que é possível dizer um monte de coisas em PA.

A variante do teorema de Ramsey que eu mencionei na outra mensagem
pode ser *enunciada* em PA mas não pode ser *demonstrada*. Uma idéia
é que a função cresce rápido demais para ser capturada por esta linguagem.
Outro ponto de vista é que na demonstração falamos (talvez sem sentir)
de conjuntos infinitos.

ZFC são os axiomas usuais da teoria dos conjuntos, mas esta mensagem
já está longa demais.

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


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

2004-03-05 Por tôpico Johann Peter Gustav Lejeune Dirichlet
O que sao PA e ZFC?[EMAIL PROTECTED] 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.28/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.brOfertas imperdíveis! Link:
 http://www.americanas.com.br/ig/=Instruções para entrar na lista, sair da lista e usar a lista emhttp://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html=Yahoo! Mail - O melhor e-mail do Brasil. Abra sua conta agora!