Running title • November 2012 • Vol. XXI, No. 1
Façamos um programa Provas em P o qual gere todas as possíveis demonstrações de T. Não é necessário que o programa dê como resultado somente demonstrações, ele pode gerar bastante lixo. O problema é que tal programa não seria executado em tempo finito, afinal são infinitas demonstrações. Para melhorá-lo estabeleçamos ele de maneira que receba um n ∈ N e devolva uma sequência de símbolos presentes em T. Assim para qualquer demonstração existe n tal que demonstração seja Provas aplicado a n. Tal programa Provas pode ser definido da maneira análoga à listagem de todos os programas possíveis que exemplificamos, visto que as demonstrações são finitas.
Por exemplo, suponha que nossa linguagem possui menos que 900 simbolos. Associe a esses símbolos númeoros distintos entre 100 e 999. Quando nosso programa Provas receber um número 100 ≤ a ≤ 999 ele retorna o símblo correspondente. Depois, ao receber o número a 1 a 2 a 3 b 1 b 2 b 3 o programa retorna o símbolo de número a 1 a 2 a 3 concaternado com o símbolo de número b 1 b 2 b 3, e assim por diante. Assim, sendo o símbolo“ A” associado ao número 739 e o símbolo“ B” associado ao número 387, o programa ao receber o número 739387 retornaria“ AB”. Ou seja, nosso programa verificaria se nosso número tem uma quantidade de algarismos múltipla de 3 e em seguida verificaria se grupos de 3 números da esquerda para a direita( ou ao contrário, vai de sua preferência) estão associados a um símbolo. Quando um número não satisfaz esses requisitos, como aconteceria com o número 4253, nosso programa retornaria uma sequência de símbolos fixa, como por exemplo“##”.
Vamos implementar outro programa chamado EhUmaDemonstracao que recebe dois parâmetros: uma sequência de símbolos e uma afirmação ϕ de T. Daí ele deve retornar 1 se a sequência é uma demonstração para ϕ ou 0 caso contrário( uma demonstração para ϕ nada mais é que uma demonstração cuja última afirmação é a própria ϕ, lembre do nosso exemplo da unicidade do elemento neutro, a afirmação final era a hipótese que queríamos provar). Essa é a função que atesta que nossa teoria é axiomatizável.
Definição 4. Dizemos que uma teoria é completa se, para toda afirmação ϕ existe uma demonstração para ϕ ou uma para ¬ ϕ( negação de ϕ).
Suponhamos T completa. Existe um programa Provou que recebe uma afirmação ϕ de T e retorna 1 se ela admite uma demonstração e 0 se ¬ ϕ admite uma demonstração. De fato, podemos explicitar tal programa:
n = 0;
FAZER SE( EhUmaDemonstracao( Provas( n), ϕ) == 1) RETORNA 1; SE( EhUmaDemonstracao( Provas( n), ¬ ϕ) == 1) RETORNA 0; n ++; ENQUANTO( 1 = 1);
Note que o programa só roda em tempo finito porque sabemos que T é completa.
5. De volta à função f
Notamos que se T é completa, para cada afirmação do tipo“ f( n) = 1” ou“ f( n) = 0”( f é a fixada acima), existe uma demonstração para“ f( n) = 1” ou uma para“ f( n) = 0”. Pois, como nossa teoria é completa, se não existe uma demonstração para“ f( n) = 1”, existe uma demonstração para“ f( n) ̸ = 1”, que é justamente“ f( n) = 0”, pois o contra domínio da nossa função possui somente esses dois elementos, 0 e 1.
4