Arquivo de etiquetas: Teorema da Incompletude

A teoria da incompletude e o teorema de Gödel

Os teoremas da incompletude de Gödel são dois teoremas da lógica matemática que estabelecem limitações inerentes de todos menos aos mais triviais sistemas axiomáticos capazes de fazer aritmética. 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, sempre há em uma teoria consistente proposições verdadeiras que não podem ser demonstradas nem negadas.”
  • 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.”