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