Re: lógica e fundamentos

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

On Wed, 30 Aug 2000, Rogerio Fajardo wrote:

> Olá, pessoal
> 
>      Sou aluno do 1° ano de Bacharelado de Matemática e comecei a me 
> interessar muito por lógica e fundamentos da matemática. Tenho algumas 
> dúvidas que gostaria que alguém me tirasse. A primeira é a seguinte: toda a 
> matemática é construída a partir de axiomas, que não são provados, e a 
> partir deles são deduzidas as verdades matemáticas dentro desse sistema. Mas 
> essa relação de implicação é uma verdade matemática, e precisa de axiomas 
> para o provar. Como se dá isso? Os teoremas da lógica dispensam provas? 
> Outra coisa: a incompletude de Gödel, que diz que a aritmética não pode ser 
> deduzida a partir de sistemas de axiomas, só vale para sistema do tipo 
> mecânico?
> 
>                                   grato pela atenção,
>                                               Rogério

Oi Rogério, este assunto é profundo e difícil de ser tratado com justiça
em um e-mail mas aí vão algumas considerações:

A afirmação de que "toda a matemática é construída a partir de axiomas,
que não são provados, e a partir deles são deduzidas as verdades matemáticas"
não é errada mas dá uma idéia muito incompleta do que seja a matemática.
A quase totalidade das áreas da matemática só veio a ser axiomatizada
muito tardiamente: no início existiam intuições, motivações físicas,
problemas, idéias mais ou menos soltas, enfim, quase tudo menos axiomas.
Em alguns casos, como no da geometria euclidiana clássica, existem
conjuntos de axiomas antigos mas que são patéticamente inadequados
pelos padrões atuais e muitos questionam-se até se Euclides estava
sequer *tentando* dar um conjunto de axiomas no sentido moderno do termo
ou se estava apenas anotando alguns fatos que iria usar sem demonstrar.

Por outro lado, a maioria dos matemáticos não conhece nem se interessa por
conhecer uma axiomatização cuidadosa da teoria dos conjuntos: eles usam
o que precisam de teoria dos conjuntos (ou de outras áreas da matemática)
mas têm pouco interesse em discutir sobre que axiomas se apóia o próprio
trabalho. Quanto à lógica, a situação é similar: a maioria dos matemáticos
não conhece nem tem interesse em conhecer lógica de primeira ordem
cuidadosamente.

A questão de qual o fundamento último do saber matemático e lógico
é de natureza filosófica e dentre os matemáticos e filósofos que se
interessam pelo tema as respostas seriam variadas. Mas a meu ver
a lógica matemática pretende discutir o pensamento humano matematicamente,
um pouco como a física discute certos aspectos da natureza também
matematicamente. Nem a lógica nem a física tentam dar respostas
quintessenciais; tais respostas, se humanamente possíveis,
cabem a outras áreas do saber, talvez à filosofia.

Finalmente, quanto ao teorema de Gödel.
O teorema que você parece ter em mente é o da incompletude.
Os sistemas de axiomas usuais em lógica de primeira ordem
para a teoria dos conjuntos (ZFC, os de Zermelo-Fraenkel+Escolha)
ou a aritmética (PA, Aritmética de Peano --- aqui indução deve ser formulada
sem usar conjuntos!) são ambos demonstravelmente incompletos
(supondo-os livres de contradição).
Um exemplo de afirmativa que não pode ser nem provada nem refutada em ZFC
é a hipótese do contínuo (para todo subconjunto X infinito não enumerável
de R existe uma bijeção entre X e R).
Um exemplo de afirmativa sobre naturais verdadeira em ZFC
mas não demonstrável em PA é uma versão do teorema de Ramsey.

Seja X um conjunto finito e defina X^[n] como sendo o conjunto de todos
os subconjuntos de X com precisamente n elementos.
Seja f: X^[n] -> Y uma função; dizemos que um subconjunto Z de X
é f-homogêneo se a restrição de f a Z^[n] for constante.

Teorema de Ramsey finito:
Dados naturais n, m e l então existe N tal que se |X| >= N e |Y| = m
então toda função f: X^[n] -> Y admite um subconjunto homogêneo Z
com l elementos.

Se X = {0,1,2,...,N-1}, dizemos que Z é relativamente grande
se |Z| >= min(Z).

Teorema de Ramsey finito forte:
Dados naturais n, m e l então existe N tal que se X = {0,1,2,...,N-1}
e |Y| = m então toda função f: X^[n] -> Y admite um subconjunto homogêneo Z
relativamente grande com pelo menos l elementos.

O teorema de Ramsey forte acima não pode ser demonstrado na aritmética
de Peano apesar de ser facilmente demonstrável fazendo uso de conjuntos
infinitos.

Mas voltando: será que estes fatos indicam deficiências nestes sistemas
de axiomas? Gödel demonstrou que não: todo sistema de axiomas em lógica
de primeira ordem onde você saiba reconhecer um axioma (será que foi isso
que você tinha em mente com "mecânico"?) e que seja forte o suficiente
para falarmos de números naturais é incompleto (desde que não seja
inconsistente).

Um outro exemplo de afirmação verdadeira (em ZFC) mas não demonstrável
em PA é a consistência de PA. O que não é tão óbvio é como sequer
formular a consistência de PA dentro de PA: afinal, PA fala de naturais
e não de axiomas e teoremas! Para isso é preciso 'emular' a lógica
dentro da aritmética, um processo um pouco trabalhoso.

A razão histórica para Gödel ter considerado a possibilidade de provar
a consistência de PA dentro de PA é que o programa de Hilbert pretendia
eliminar as restrições que certos matemáticos faziam à teoria dos conjuntos
provando a consistência de ZFC dentro de PA: pelo teorema de Gödel,
é impossível dar tal demosntração.

[]s, N.