Teorema de Craig - Craig's theorem

Na lógica matemática , o teorema de Craig afirma que qualquer conjunto recursivamente enumerável de fórmulas bem formadas de uma linguagem de primeira ordem é (primitivamente) recursivamente axiomatizável . Este resultado não está relacionado ao conhecido teorema de interpolação de Craig , embora ambos os resultados tenham o nome do mesmo lógico, William Craig .

Axiomatização recursiva

Let Ser uma enumeração dos axiomas de um conjunto recursivamente enumerável T de fórmulas de primeira ordem. Construir outro conjunto T * consistindo em ${\ displaystyle A_ {1}, A_ {2}, \ dots}$

${\ displaystyle \ underbrace {A_ {i} \ land \ dots \ land A_ {i}} _ {i}}$

para cada número inteiro positivo i . Os fechamentos dedutivos de T * e T são, portanto, equivalentes; a prova mostrará que T * é um conjunto recursivo. Um procedimento de decisão para T * se presta de acordo com o seguinte raciocínio informal. Cada membro do T * é ou da forma ${\ displaystyle A_ {1}}$

${\ displaystyle \ underbrace {B_ {j} \ land \ dots \ land B_ {j}} _ {j}.}$

Uma vez que cada fórmula tem comprimento finito, é verificável se é ou não ou da referida forma. Se for da referida forma e consistir em j conjuntos, estará em T * se o conjunto (recorrente) for ; caso contrário, não está em T *. Novamente, é possível verificar se o conjunto é de fato , passando pela enumeração dos axiomas de T e, em seguida, verificando símbolo por símbolo se as expressões são idênticas. ${\ displaystyle A_ {1}}$${\ displaystyle A_ {j}}$${\ displaystyle A_ {n}}$

Axiomatizações recursivas primitivas

A prova acima mostra que para cada conjunto recursivamente enumerável de axiomas há um conjunto recursivo de axiomas com o mesmo fechamento dedutivo. Um conjunto de axiomas é recursivo primitivo se houver uma função recursiva primitiva que decide a participação no conjunto. Para obter uma aximatização recursiva primitiva, em vez de substituir uma fórmula por ${\ displaystyle A_ {i}}$

${\ displaystyle \ underbrace {A_ {i} \ land \ dots \ land A_ {i}} _ {i}}$

em vez disso, substitui-o por

${\ displaystyle \ underbrace {A_ {i} \ land \ dots \ land A_ {i}} _ {f (i)}}$ (*)

onde f ( x ) é uma função que, dado i , retorna um histórico de computação mostrando que está no conjunto recursivamente enumerável original de axiomas. É possível para uma função recursiva primitiva analisar uma expressão de forma (*) para obter e j . Então, como o predicado T de Kleene é recursivo primitivo, é possível para uma função recursiva primitiva verificar que j é de fato um histórico de computação, conforme necessário. ${\ displaystyle A_ {i}}$${\ displaystyle A_ {i}}$

Implicações filosóficas

Se é uma teoria axiomatizável recursivamente e dividimos seus predicados em dois conjuntos disjuntos e , então aqueles teoremas que estão no vocabulário são recursivamente enumeráveis ​​e, portanto, com base no teorema de Craig, axiomatizáveis. Carl G. Hempel argumentou com base nisso que, uma vez que todas as previsões da ciência estão no vocabulário de termos de observação, o vocabulário teórico da ciência é, em princípio, eliminável. Ele próprio levantou duas objeções a esse argumento: 1) os novos axiomas da ciência são praticamente incontroláveis ​​e 2) a ciência usa o raciocínio indutivo e a eliminação de termos teóricos pode alterar as relações indutivas entre sentenças observacionais. Hilary Putnam argumenta que esse argumento é baseado em uma concepção errônea de que o único objetivo da ciência é a previsão bem-sucedida. Ele propõe que a principal razão pela qual precisamos de termos teóricos é que desejamos falar sobre entidades teóricas (como vírus, estrelas de rádio e partículas elementares). ${\ displaystyle T}$${\ displaystyle V_ {A}}$${\ displaystyle V_ {B}}$${\ displaystyle T}$${\ displaystyle V_ {A}}$

Referências

• William Craig . "On Axiomatizability Within a System", The Journal of Symbolic Logic , Vol. 18, No. 1 (1953), pp. 30-32.
• Hilary Putnam . "Teorema de Craig", The Journal of Philosophy , Vol. 62, No. 10 (1965), pp. 251.260.