Kurt Gödel

Em 1931, o matemático Kurt Gödel (1906-1978) publicou alguns resultados das suas pesquisas, que mudaram o rumo dos estudos da Ciência Matemática e atingiram profundamente o formalismo. Entre eles está o famoso Teorema de Gödel sobre as proposições indecidíveis, que diz o seguinte: 

A. Se S é um sistema formal suficientemente forte para conter a aritmética elementar, então S é incompleto ou inconsistente; 

B. A eventual consistência de um tal sistema formal não pode ser provada apenas com recursos daquele mesmo sistema. 
Kurt Gödel demonstrou que não é possível construir uma teoria axiomática dos números que seja completa, como pretendia Hilbert. 

A primeira parte do teorema citado significa que existem proposições aritméticas tais que nem elas nem a sua negação são demonstráveis na aritmética adoptada. São proposições indecidíveis. Logo, em qualquer axiomática consistente baseada em aritmética existem sentenças indecidíveis. Como uma proposição e a sua negação são contraditórias - admitindo-se o princípio do terceiro excluído -, então uma delas é verdadeira. Portanto existem sentenças aritméticas verdadeiras, formuláveis numa determinada axiomática baseada em aritmética, que não podem ser provadas. A segunda parte do teorema diz que a prova de ausência de contradição numa axiomática da aritmética não pode ser realizada apenas com os recursos dessa axiomática. 

Para o desenvolvimento dos seus estudos Gödel concebeu uma interessante formulação de símbolos, fórmulas e provas através de números, bem como mostrou que as proposições metamatemáticas - aliás sem isso não poderia ter realizado a sua prova - podem estar adequadamente reflectidas dentro do próprio cálculo, aritmetizando assim a própria metamatemática. 

Gödel acabou com o sonho logicista, visto que não se pode desenvolver toda a aritmética (e muito menos toda a matemática) num sistema que seja ao mesmo tempo consistente e completo. Também acabou com o sonho formalista: existem enunciados matemáticos que são verdadeiros, mas não são susceptíveis de prova, isto é, existe um abismo entre verdade e demonstração. 

Gödel, no entanto, ao longo da demonstração do seu teorema rompeu um limiar crucial entre a lógica e a matemática. Ele mostrou que qualquer sistema formal que seja tão rico quanto um sistema numérico qualquer, que contenha os operadores "+" e "=", pode ser expresso em termos aritméticos. Isto significa que por mais complexa que se torne a matemática (ou qualquer outro sistema formal redutível a ela), ela pode sempre ser expressa em termos de operações a serem executadas sobre números, e as partes do sistema poderão ser manipuladas por regras de contagem e comparação. Outro resultado fundamental do teorema da incompletude de Gödel pode-se considerar como sendo a demonstração de que há algumas funções sobre os inteiros que não podem ser representadas por um algoritmo, ou seja, que não podem ser computadas. Posteriormente verificou-se a existência de uma equivalência entre o Teorema da Incompletude de Gödel e o problema da parada de Turing.