Re: [obm-l] Axiomas de Peano

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

On Fri, Jun 21, 2002 at 02:32:34AM +0000, Rogerio Fajardo wrote:
> Aproveitando que o assunto é axiomas de peano, é possível definir aritmética 
> usando só os axiomas de peano (usando lógica de 1ªordem e os símbolos 0 e 
> sucessor de)? Dá pra fazer uma espécie de teorema da recursão nos axiomas de 
> Peano? Ou será necessário usar lógica de segunda ordem, ou esquema de prova?

Boa pergunta.

O seguinte é um modelo para os axiomas de Peano apenas com o conceito
de sucessor e apenas com lógica de primeira ordem:

{0, 1, 2, ...,..., w - 2, w - 1, w, w + 1, w + 2, ...}

Mais, valem neste modelo exatamente os mesmos enunciados de lógica
de primeira ordem (ressaltando, se a linguagem tiver apenas o conceito
de sucessor). A coisa muda totalmente de figura se + e * fizerem parte
da linguagem, junto com os axiomas:

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

Aí fica muito mais difícil (mas, por Gödel e Lowenheim-Skolem, ainda possível)
obter modelos estranhos.

Para quem não está entendendo, o último axioma de Peano é freqüentemente
fraseado assim:

  Se X é um subconjunto de N com 0 pertencente a X e com s(X) contido em X
  então X = N.

Este axioma pressupõe o conceito de conjunto, ou seja, pressupõe uma teoria
de conjuntos. Esta é uma pressuposição bem forte: dada a teoria dos conjuntos
podemos *construir* os naturais, então para que os axiomas? Uma solução
é usar lógica de 2a ordem: a própria lógica e linguagem incorporam
uma versão fraca do conceito de conjunto. A lógica de 2a ordem tem suas
dificuldades.

A versão mais autocontida (usando lógica de 1a ordem sem teoria dos conjuntos)
seria trocar conjuntos por fórmulas. Assim, o último axioma
vira uma família de axiomas (um para cada fórmula).
Seja p(n) é uma fórmula com uma variável livre n; temos o axioma:

  Se p(0) e (para todo n, ( p(n) => p(n+1) ) ) então (para todo n, p(n))

[]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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================