En lógica matemática , el teorema de Craig establece que cualquier conjunto recursivamente enumerable de fórmulas bien formadas de un lenguaje de primer orden es (primitivamente) recursivamente axiomatizable . Este resultado no está relacionado con el conocido teorema de interpolación de Craig , aunque ambos resultados llevan el nombre del mismo lógico, William Craig .
Axiomatización recursiva
Dejar ser una enumeración de los axiomas de un conjunto T recursivamente enumerable de fórmulas de primer orden. Construya otro conjunto T * que consta de
para cada entero positivo i . Los cierres deductivos de T * y T son, por tanto, equivalentes; la prueba mostrará que T * es un conjunto recursivo. Un procedimiento de decisión para T * se presta según el siguiente razonamiento informal. Cada miembro de T * es o de la forma
Dado que cada fórmula tiene una longitud finita, se puede comprobar si es o no o de dicha forma. Si es de dicha forma y consta de j conjunciones, está en T * si la conjunción (recurrente) es; de lo contrario, no está en T *. De nuevo, se puede comprobar si la conjunción es de hecho pasando por la enumeración de los axiomas de T y luego verificando símbolo por símbolo si las expresiones son idénticas.
Axiomatizaciones recursivas primitivas
La demostración anterior muestra que para cada conjunto recursivamente enumerable de axiomas hay un conjunto recursivo de axiomas con el mismo cierre deductivo. Un conjunto de axiomas es recursivo primitivo si hay una función recursiva primitiva que decide la pertenencia al conjunto. Para obtener una maximatización recursiva primitiva, en lugar de reemplazar una fórmula con
uno en su lugar lo reemplaza con
- (*)
donde f ( x ) es una función que, dado i , devuelve un historial de cálculo que muestra queestá en el conjunto original de axiomas recursivamente enumerables. Es posible que una función recursiva primitiva analice una expresión de forma (*) para obtenery j . Entonces, debido a que el predicado T de Kleene es recursivo primitivo, es posible que una función recursiva primitiva verifique que j es de hecho un historial de cálculo como se requiere.
Implicaciones filosóficas
Si es una teoría recursivamente axiomatizable y dividimos sus predicados en dos conjuntos disjuntos y , entonces esos teoremas de que estan en el vocabulario son recursivamente enumerables y, por tanto, según el teorema de Craig, axiomatizables. Carl G. Hempel argumentó basándose en esto que dado que todas las predicciones de la ciencia están en el vocabulario de los términos de observación, el vocabulario teórico de la ciencia es, en principio, eliminable. Él mismo planteó dos objeciones a este argumento: 1) los nuevos axiomas de la ciencia son prácticamente inmanejables, y 2) la ciencia utiliza el razonamiento inductivo y la eliminación de términos teóricos puede alterar las relaciones inductivas entre oraciones observacionales. Hilary Putnam sostiene que este argumento se basa en la idea errónea de que el único objetivo de la ciencia es la predicción exitosa. Propone que la razón principal por la que necesitamos términos teóricos es que deseamos hablar de entidades teóricas (como virus, estrellas de radio y partículas elementales).
Referencias
- William Craig . "Sobre la axiomatizabilidad dentro de un sistema", The Journal of Symbolic Logic , vol. 18, núm. 1 (1953), págs. 30-32.
- HIlary Putnam . "Teorema de Craig", The Journal of Philosophy , vol. 62, núm. 10 (1965), págs. 251.260.