Re: Defini��o de N�mero e teorema de Godel

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

On Thu, 3 Jun 1999, Paulo Santa Rita wrote:

> A colega "Braz�o" talvez tenha esquecido de acrescentar que logo ap�s a 
> demonstra��o de Godel muitos m�tematicos conjeturaram que as proposi��es 
> indemonstr�veis que porventura existissem na "Aritm�tica habitual! seriam 
> t�o ex�ticas que n�o seriam de interesse para um "matem�tico normal".
> Passaram-se muito poucos anos para que se mostrasse que tal conjetura � 
> falsa. Foi Paul Cohen, que, entre outras coisas mostrou a independ�ncia da 
> hipotese do cont�nuo, que apresentou as primeiras proposi��es "bastantes 
> razoaveis" que s�o inacess�veis polos axiomas habituais.

Os axiomas "habituais" no caso dos exemplos de Cohen s�o os axiomas
da teoria dos conjuntos (ZFC); em teoria dos conjuntos h� muitas muitas
muitas proposi��es ZFC-indecid�veis. Vale observar que n�o � claro se
ZFC-indecid�vel implica em ser humanamente indecid�vel: talvez matem�ticos
no futuro venham a aceitar como "evidentes" alguns novos axiomas que
permitam demonstrar ou refutar a hip�tese do cont�nuo. O pr�prio G�del
dedicou-se muito (depois do resultado de Cohen) a tentar "provar" ou
"refutar" a hip�tese do cont�nuo. "Provar", significando, � claro, algo 
muito diferente de apresentar uma ZFC-demonstra��o.

H� hoje exemplos interessantes de proposi��es aritm�ticas que s�o
ZFC-teoremas mas que s�o indecid�veis na aritm�tica de Peano (PA),
i.e., que s� podem ser demonstrados usando conjuntos infinitos.
Um exemplo disso � uma varia��o do teorema de Ramsey.

Primeiro os enunciados dos teoremas de Ramsey usuais.

Teorema de Ramsey finito:
Para quaisquer k, l, m  existe um n (dependendo de k, l, m) tal que
se tomamos um conjunto X de n elementos
(|X| = n, por exemplo X = {0,1,...,n-1})
e pintamos cada subconjunto de X  com l elementos com uma dentre m cores
(isto �, definimos uma fun��o f: X^[l] -> {0,1,...,m-1},
onde X^[l] = {Z subconjunto de X | |Z| = l}) 
ent�o existe um subconjunto Y de X com k elementos
(|Y| = k) tal que todo subconjunto de Y com l elementos tem a mesma cor
(i.e., a restri��o de f a Y^[l] � constante).

Um caso especial � o conhecido problema: em uma reuni�o de 6 pessoas
h� sempre ou 3 que se conhecem mutuamente ou 3 que se desconhecem
mutuamente. Isto equivale a dizer que para k = 3, l = l, m = 2 podemos
tomar n = 6. � dif�cil encontrar o valor m�nimo de n para k, l e m dados
e a resposta s� � conhecida para valores de k, l e m muito baixos.
Mas este teorema pode ser formulado e demonstrado sem maiores dificuldades
na aritm�tica de Peano, i.e., pode ser demonstrado sem fazer uso de
conjunto infinitos.

No teorema abaixo N representa {0,1,...}, o conjunto dos naturais.

Teorema de Ramsey infinito:
Para quaisquer l e m e para qualquer fun��o f: N^[l] -> {0,1,...,m-1}
existe um subconjunto infinito Y de N tal que a restri��o de f a Y^[l]
� constante.

O teorema de Ramsey infinito n�o pode evidentemente ser formulado
(muito menos demonstrado) na aritm�tica de Peano.
Tamb�m n�o � dif�cil ver que o teorema de Ramsey finito � corol�rio do
infinito, mas sob o ponto de vista da aritm�tica de Peano isto � "roubar".
Vamos agora ver uma fam�lia de vers�es mais fortes do teorema de Ramsey
que tamb�m segue facilmente do teorema de Ramsey infinito.
O fato surpreendente � que muitos teoremas desta fam�lia n�o podem ser
demonstrados na aritm�tica de Peano, i.e., n�o podem ser demonstrados
*sem* usar conjuntos infinitos ou algum outro recurso estranho �
aritm�tica.

Seja h: N -> N uma fun��o (podemos nos restringir a fun��es descrit�veis
na aritm�tica de Peano).

Teorema de Ramsey finito-h:
Para quaisquer k, l, m  existe um n (dependendo de k, l, m) tal que   
se tomamos um conjunto X de n elementos
(|X| = n, por exemplo X = {0,1,...,n-1})
e pintamos cada subconjunto de X  com l elementos com uma dentre m cores
(isto �, definimos uma fun��o f: X^[l] -> {0,1,...,m-1},
onde X^[l] = {Z subconjunto de X | |Z| = l})
ent�o existe um subconjunto Y de X com as seguintes propriedades:

todo subconjunto de Y com l elementos tem a mesma cor
(i.e., a restri��o de f a Y^[l] � constante).

se y � o menor elemento de Y ent�o Y tem k+h(y) elementos.

A raz�o pela qual este teorema n�o pode ser demonstrado em aritm�tica
de Peano � que n cresce muito muito r�pido em fun��o de k, l e m,
mais r�pido do que � poss�vel com fun��es descrit�veis na aritm�tica de
Peano.

H� uma exposi��o completa deste resultado no �ltimo cap�tulo do Handbook
of Mathematical Logic.

[]s, N.
http://www.mat.puc-rio.br/~nicolau