Running title • November 2012 • Vol. XXI, No. 1
O Teorema da Incompletude de Gödel
Amanda Figur ∗
Instituto de Ciências Matemáticas e Computação
[email protected]
O Teorema da Incompletude de Gödel
Resumo
“Either mathematics is too big
for the human mind or the
human mind is more than a
machine.” (Kurt Gödel)
♠
Utilizando conhecimentos básicos sobre números naturais, fun-
ções e uma linguagem de programação, vamos demontrar o Primeiro
Teorema da Incompletude de Gödel de maneira simplificada, diferente
da prova original e nos distanciando de grandes discussões filosoficas,
assim como do maquinário de lógica matemática, presentes em outras
demontrações.
1.
Introdução
rovado no início de 1930 e publicado no Über formal unentscheidbare Sätze der Principia
Mathematica und verwandter Systeme, o primeiro Teorema da Incompletude de Gödel foi um
marco para a matemática no século 20, mostrando que a matemática não era um objeto
finalizado e consistente, como muitos acreditavam. Ele enuncia que toda teoria axiomatizável e
completa é inconsistente.
P
• Quando uma teoria é completa? Se para toda afirmação existe uma demonstração para ela ou
para sua negação.
• Quando ela é inconsistente? Quando uma afirmação e sua negação podem ser ambas demons-
tradas.
• O que é uma teoria axiomatizável? Para nós uma teoria “axiomatizável” seria a existência de
um programa executado em tempo finito que verifica se algo é uma demonstração.
Formalizar de maneira mais completa o que é uma teoria é axiomatizável não cabe ao escopo
desse texto. Resumindo, o teorema prova que não existem teorias “ricas o suficiente” que não
gerem contradições.
Neste texto vamos apresentar uma prova simplificada do primeiro Teorema da Incompletude de
Gödel, diferente da original formulada pelo próprio Gödel. Por um lado, a seguinte demonstração
foge de grandes discussões filosóficas acerca de sua prova e, por outro lado, evita o maquinário
pesado de lógica matemática presente em demonstrações mais formais.
Desse ponto de vista é recomendado que você tenha alguns conhecimentos básicos sobre
uma linguagem de programação, números naturais e funções. O que vamos fazer é fixar uma
linguagem de programação à nossa escolha e então fixar uma função f não computável. Em
seguida, vamos definir uma teoria onde seja possível construir a f para utilizar um programa,
chamado EhUmaDemonstracao , que recebe uma afirmação e verifica se ela é uma demonstração,
com a intenção de chegar em uma contradição sobre a não computabilidade de f : se nossa teoria
∗ Obrigado
ao Leandro Aurichi
1