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