Os teoremas da incompletude de Gödel são dois teoremas da lógica matemática que estabelecem limitações inerentes a quase todos os sistemas axiomáticos, exceto aos mais triviais. Os teoremas, provados por Kurt Gödel em 1931, são importantes tanto para a lógica matemática quanto para a filosofia da matemática. Os dois resultados são amplamente, mas não universalmente, interpretados como indicações de que o programa de Hilbert para encontrar um conjunto completo e consistente de axiomas para toda a matemática é impossível, dando uma resposta negativa para o segundo problema de Hilbert.
O primeiro teorema da incompletude afirma que nenhum sistema consistente de axiomas, cujos teoremas podem ser listados por um “procedimento efetivo” (e.g., um programa de computador que pode ser qualquer tipo de algoritmo), é capaz de provar todas as verdades sobre as relações dos números naturais (aritmética). Para qualquer um desses sistemas, sempre haverá afirmações sobre os números naturais que são verdadeiras, mas que não podem ser provadas dentro do sistema. O segundo teorema da incompletude, uma extensão do primeiro, mostra que tal sistema não pode demonstrar sua própria consistência.
Teorema 1: "Qualquer teoria axiomática recursivamente enumerável e capaz de expressar algumas verdades básicas de aritmética não pode ser, ao mesmo tempo, completa e consistente. Ou seja, em uma teoria consistente, sempre há proposições que não podem ser demonstradas nem verdadeiras, nem falsas". Teorema 2: "Uma teoria, recursivamente enumerável e capaz de expressar verdades básicas da aritmética e alguns enunciados da teoria da prova, pode provar sua própria consistência se, e somente se, for inconsistente."
História
No final do século XIX, a filosofia do conhecimento era considerada um bloco monolítico e muitos intelectuais da época consideravam que haveria pouca coisa fundamentalmente nova a ser descoberta. No Congresso Internacional de Matemática de Paris, em 1900, o jovem e genial David Hilbert, imbuído das ideias correntes, apresentou um surpreendente trabalho resumindo as 23 questões ainda "em aberto", as quais, após resolvidas, completariam todo o escopo da matemática.
Hilbert pretendia, como de fato foi parcialmente conseguido, desencadear um esforço geral da comunidade científica a fim de completar a fundamentação lógica da matemática. Nos poucos anos que se seguiram a maior parte das questões por ele propostas foram adequadamente resolvidas.
Em 1931, quando ainda vigorava a proposta de Hilbert de obter a completa construção da teoria matemática através da lógica formal, Gödel publicou o seu trabalho "Sobre as Proposições Indecidíveis", pondo fim a essa expectativa. Na Universidade de Princeton, o prestigiado Neumann, que trabalhava com afinco na proposta de Hilbert, imediatamente mergulhou nos trabalhos de Gödel, dando-lhe grande apoio.
Paralelamente, na Física, estava em pleno andamento o desenvolvimento da teoria quântica e quatro anos antes (1927) Heisenberg já divulgara seu "principio da incerteza", colocando um limite físico na experimentação microscópica direta. Foi mais um golpe nas hipóteses determinísticas da ciência.
Posteriormente, Church e Turing demonstraram que não existe nenhum algoritmo capaz de provar se "uma proposição qualquer faz ou não parte de uma teoria".
Curiosamente, até 1963, nem Gödel nem qualquer outro matemático havia apresentado alguma proposição que ilustrasse os teoremas da indecidibilidade. Somente então o jovem Paul Cohen, de Stanford, desenvolveu uma técnica para teste de proposições indecidíveis. Cohen mostrou que a hipótese do continuum, justamente uma das questões fundamentais da matemática, era indecidível.
Contexto Como afirmações da teoria formal estão escritas na forma simbólica, é possível verificar mecanicamente que uma prova formal de um conjunto finito de axiomas é válida. Essa tarefa, conhecida como verificação automática de provas, é relacionada a demonstração automática de teoremas. A diferença é que ao invés de construir uma nova prova, o verificador de prova simplesmente checa se a prova formal fornecida (ou em instruções que podem ser seguidas para criar a prova formal) é correta. Esse processo não é meramente hipotético; sistemas tais como Isabelle ou Coq são usados para formalizar provas e então verificar sua validade.
Muitas teorias de interesse incluem um conjunto infinito de axiomas, contudo. Neste caso, para verificar uma prova formal, deve ser possível determinar se a afirmação que é tida como axioma é realmente um axioma. Essa questão surge nas teorias de primeira ordem da aritmética, como a aritmética de Peano, porque o princípio da indução matemática é expresso como um conjunto infinito de axiomas (um esquema axiomático).
A teoria axiomática é tida como efetivamente gerada se seu conjunto de axiomas é um conjunto recursivamente enumerável. Isto significa que há um programa de computador que, em princípio, pode enumerar todos os axiomas da teoria sem listar qualquer afirmação que não é axioma. Isto é equivalente à existência de um programa que enumera todos os teoremas da teoria sem enumerar qualquer afirmação que não é teorema. Exemplos de teorias efetivamente geradas com conjunto infinito de axiomas incluem a aritmética de Peano e a teoria dos conjuntos de Zermelo-Fraenkel.
Ao escolher um conjunto de axiomas, um objetivo é que seja possível provar quantos resultados corretos forem possíveis, sem provar algum resultado incorreto. Um conjunto de axiomas é completo se, para qualquer afirmação na linguagem axiomática, ou a afirmação ou sua negação é demonstrável a partir dos axiomas. Um conjunto de axiomas é (simplesmente) consistente se não existir nenhuma afirmação tal que ambas a afirmação e sua negação são demonstráveis a partir dos axiomas. No sistema padrão da lógica de primeira ordem, um conjunto inconsistente de axiomas provará toda afirmação em sua linguagem (isso às vezes é chamado de princípio da explosão), e é, então, automaticamente completa. Um conjunto de axiomas que é tanto completo quanto consistente, contudo, prova um conjunto maximal de teoremas não-contraditórios. O teorema da incompletude de Gödel mostra que em certos casos não é possível obter uma teoria efetivamente gerada, completa e consistente.
Primeiro teorema da incompletude O primeiro teorema da incompletude de Gödel apareceu primeiro em 1931 como “Teorema VI” no artigo de Gödel chamado On Formally Undecidable Propositions in Principia Mathematica and Related Systems I.
O teorema formal é escrito em linguagem bastante técnica. Pode ser parafraseado em português como:
A verdadeira mas indemonstrável afirmação referida pelo teorema é, às vezes, referida como “sentença de Gödel” para a teoria. A prova constrói uma sentença específica de Gödel para cada teoria efetivamente gerada, porém há infinitas afirmações na linguagem da teoria que compartilha a propriedade de ser verdade mas indemonstrável. Por exemplo, a conjunção entre uma sentença de Gödel e qualquer sentença logicamente válida terá essa propriedade.
Para cada teoria formal consistente T que possui uma pequena quantidade necessária da teoria dos números, a sentença de Gödel G correspondente afirma: “G não pode ser provada dentro da teoria T”. Essa interpretação de G nos leva à seguinte análise informal: se G fosse demonstrável sob os axiomas e regras de inferência de T, então T teria um teorema, G, que efetivamente se contradiz, e então a teoria T seria inconsistente. Isto significa que se a teoria T é consistente, então G não pode ser provada dentro dela, e assim a teoria T é incompleta. Além disso, a alegação que G faz sobre sua própria indemonstrabilidade é correta. Nesse sentido, G não é somente indemonstrável como também é verdadeira, e a “demonstrabilidade dentro da teoria T” não é o mesmo que verdade. Essa análise informal pode ser formalizada para fazer uma prova rigorosa do teorema da incompletude. A prova formal revela exatamente a hipótese necessária para a hipótese T para que a natureza contraditória de G nos leve a uma genuína contradição.
Cada teoria efetivamente gerada tem sua própria sentença de Gödel. É possível definir uma teoria T’ maior que contém T inteira mais G como um axioma adicional. Isto não resultará numa teoria completa, porque o teorema de Gödel também se aplicará a T’, e assim T’ não pode ser completa. Nesse caso, G é um teorema em T’, porque é um axioma. Como G somente afirma que não é provável em T, nenhuma contradição é apresentada por sua indemonstrabilidade em T’. No entanto, como o teorema da incompletude se aplica a T’, existirá uma nova afirmação de Gödel, G’, para T’, mostrando que T’ também é incompleta. G’ se diferenciará de G, pois se referirá a T’ e não, a T.
Para provar o primeiro teorema da incompletude, Gödel representou as afirmações por números. Então a teoria em mãos, que se supõe provar certos fatos sobre números, também prova fatos sobre suas próprias afirmações, visto que é efetivamente gerada. Questões sobre a indemonstrabilidade das afirmações são representadas como questões sobre as propriedades de números, que poderiam ser decidiveis pela teoria se ela fosse completa. Nesses termos, a sentença de Gödel afirma que nenhum número natural existe com certa propriedade. Um número com essa propriedade codificaria uma prova da inconsistência da teoria. Se existisse tal número, então a teoria seria inconsistente, ao contrário da hipótese da consistência. Então, assumindo que a teoria é consistente, não existe esse número.
Significado do primeiro teorema da incompletude O primeiro teorema da incompletude mostra que qualquer sistema formal consistente, que inclui o suficiente da teoria dos números naturais, é incompleto: existem afirmações verdadeiras expressáveis em sua linguagem que são indemonstráveis dentro do sistema. Então, nenhum sistema formal (satisfazendo as hipóteses dos teoremas), que visa a caracterizar os números naturais, pode realmente fazer isso, pois existirão afirmações verdadeiras que o sistema não pode provar. Esse fato é, algumas vezes, pensado como tendo severas consequências para o programa de logicismo proposto por Gottlob Frege e Bertrand Russell, que visa a definir os números naturais em termos da lógica (Hellman 1981, p. 451-468). Bob Hale e Crispin Wright discutem que não é um problema para a lógica, porque os teoremas da incompletude se aplicam igualmente à lógica de primeira ordem assim como faz para a aritmética. Eles discutem que apenas aqueles que acreditam que os números naturais estão para ser definidos em termos da lógica de primeira ordem têm esse problema.
A existência de um sistema formal incompleto não é, particularmente, uma surpresa. O sistema pode estar incompleto simplesmente porque nem todos os axiomas necessários foram descobertos. Por exemplo, a geometria Euclideana sem o postulado das paralelas é incompleto; não é possível provar ou deixar de provar o postulado a partir dos axiomas restantes.
O teorema de Gödel mostra que, em teorias que incluem uma pequena parte da teoria dos números, uma completa e finita lista de axiomas não pode nunca ser criada, ou sequer uma lista infinita que pode ser enumerada por um programa de computador. Cada vez que uma nova afirmação é adicionada como um axioma, há outras afirmações verdadeiras que ainda não podem ser provadas, mesmo com o novo axioma. Se axiomas forem sendo adicionados, isso tornará o sistema completo, com o custo de tornar o sistema inconsistente.