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