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

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

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