Una técnica para decidir satisfiability en los fragmentos de la lógica de primer orden

Question

Por Goedels integridad teorema de satisfiability en la lógica de primer orden es $\Pi_1$. Así que para obtener decidability en algún fragmento, es suficiente para demostrar que satisfiability es $\Sigma_1$ en este fragmento. Me pregunto si la siguiente técnica de trabajo.

Deje $\cal F$ ser un conjunto de primer orden fórmulas y $\cal M$ una contables conjunto de estructuras. Supongamos que podemos demostrar que si una frase $\phi \in \cal F$ es válido, que tiene un modelo de $M \in \cal M$. Además, supongamos que el $M \models \phi$ es decidable (o al menos semi-decidable). A continuación, el satisfiability para $\cal F$ $\Sigma_1$ y, por tanto, decidable.

¿Alguien sabe los resultados a lo largo de estas líneas?

Answer 1

Estás buscando el tema conocido como modelo computable de la teoría, que es el modelo de la teoría, pero con una vista a la computabilidad de los modelos y teorías que surgen. Muchos de los argumentos que en el modelo computable la teoría de la naturaleza y el sabor de la observación en su pregunta.

En particular, el Eficaz Integridad Teorema (consulte la página 18 de la Harizanov el libro con el que he enlazado) es la afirmación de la inversa de su observación. Es decir, si una teoría de la $T$ es decidable en el sentido de que tenemos un eficaz procedimiento para determinar el $T\vdash \varphi$, $T$ tiene un decidable modelo, un modelo de $M$ construido en $\mathbb{N}$, en el que la satisfacción de la relación de $M\models\varphi[\vec n]$ es decidable. En particular, mediante la aplicación de un uniforme de la versión de ese argumento, si $T$ es decidable, a continuación, para cada una de las $\varphi$ que $T+\varphi$ es consistente, podemos construir un decidable modelo de $M_\varphi\models T+\varphi$. Estos modelos, por tanto, funcionan exactamente como en su argumento.