teorema de craig

En lógica matemática , el teorema de Craig (también conocido como truco de Craig ^[1] ) 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

Sea una enumeración de los axiomas de un conjunto recursivamente enumerable de fórmulas de primer orden. Construya otro conjunto que consista en ${\displaystyle A_{1},A_{2},\dots }$ ${\displaystyle T}$ ${\displaystyle T^{*}}$

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

para cada número entero positivo . Las clausuras deductivas de y son, por tanto, equivalentes; la prueba mostrará que es un conjunto recursivo. Un procedimiento de decisión se presta según el siguiente razonamiento informal. Cada miembro de es de la forma ${\displaystyle i}$ ${\displaystyle T^{*}}$ ${\displaystyle T}$ ${\displaystyle T^{*}}$ ${\displaystyle T^{*}}$ ${\displaystyle T^{*}}$

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

Dado que cada fórmula tiene una longitud finita, se puede comprobar si tiene o no dicha forma. Si es de dicha forma y consta de conjuntos, es si el conjunto (recurrente) es ; de lo contrario no está dentro . Nuevamente, se puede verificar si la conjunción es realmente cierta enumerando los axiomas de y luego verificando símbolo por símbolo si las expresiones son idénticas. ${\displaystyle j}$ ${\displaystyle T^{*}}$ ${\displaystyle A_{j}}$ ${\displaystyle T^{*}}$ ${\displaystyle A_{n}}$ ${\displaystyle T}$

Axiomatizaciones recursivas primitivas

La prueba anterior muestra que para cada conjunto de axiomas recursivamente enumerables hay un conjunto recursivo de axiomas con el mismo cierre deductivo. Un conjunto de axiomas es recursivo primitivo si existe una función recursiva primitiva que decide la pertenencia al conjunto. Para obtener una axiomatización recursiva primitiva, en lugar de reemplazar una fórmula con ${\displaystyle A_{i}}$

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

uno en su lugar lo reemplaza con

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

donde es una función que, dado , devuelve un historial de cálculo que muestra que se encuentra en el conjunto original de axiomas enumerables de forma recursiva. Es posible que una función recursiva primitiva analice una expresión de forma (*) para obtener y . Entonces, debido a que el predicado T de Kleene es recursivo primitivo, es posible que una función recursiva primitiva verifique que efectivamente se trata de un historial de cálculo según se requiere. ${\displaystyle f}$ ${\displaystyle i}$ ${\displaystyle A_{i}}$ ${\displaystyle A_{i}}$ ${\displaystyle j}$ ${\displaystyle j}$

Implicaciones filosóficas

Si es una teoría recursivamente axiomatizable y dividimos sus predicados en dos conjuntos disjuntos y , entonces esos teoremas que están en el vocabulario son recursivamente enumerables y, por lo 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 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 razonamientos inductivos 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). ${\displaystyle T}$ ${\displaystyle V_{A}}$ ${\displaystyle V_{B}}$ ${\displaystyle T}$ ${\displaystyle V_{A}}$

Referencias

1. A. Visser, "Teorema de Vaught sobre la axiomatizabilidad mediante un esquema". Boletín de lógica simbólica, vol. 18, núm. 3 (2012).

• 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.