Satisfacción de primer orden que no tiene modelos finitos

Sabemos por el teorema de Church que determinar la satisfacción de primer orden es indecidible en general, pero existen varias técnicas que podemos usar para determinar la satisfacción de primer orden. Lo más obvio es buscar un modelo finito. Sin embargo, hay una serie de declaraciones en la lógica de primer orden que podemos demostrar que no tienen modelos finitos. Por ejemplo, cualquier dominio en el que opera una función inyectiva y no sobreyectiva es infinito.

¿Cómo demostramos la satisfacción de las declaraciones de primer orden cuando no hay modelos finitos o se desconoce la existencia de modelos finitos? En la demostración automatizada de teoremas podemos determinar la satisfacción de varias maneras:

Podemos negar la oración y buscar una contradicción. Si se encuentra uno, demostramos la validez de primer orden de la declaración y, por lo tanto, la satisfabilidad.
Usamos saturación con resolución y nos quedamos sin inferencias. Más a menudo que no, tendremos una cantidad infinita de inferencias para hacer, por lo que esto no es confiable.
Podemos usar el forzamiento, que supone la existencia de un modelo y también la consistencia de la teoría.

No conozco a nadie que implemente el forzamiento como una técnica mecanizada para la prueba automatizada de teoremas, y no parece fácil, pero me interesa si se ha hecho o se ha intentado, ya que se ha utilizado para demostrar la independencia de varias declaraciones. en teoría de conjuntos, que en sí misma no tiene modelos finitos.

¿Existen otras técnicas conocidas para buscar la satisfacción de primer orden que sean aplicables para el razonamiento automatizado o alguien ha trabajado en un algoritmo de forzado automatizado?

reference-request lo.logic automated-theorem-proving Dezakin
fuente

El enfoque de Infinox podría ser relevante para su pregunta (sin responderla). La idea es utilizar demostradores de teoremas para demostrar la inexistencia de modelos finitos. Ver, por ejemplo, gupea.ub.gu.se/bitstream/2077/22058/1/gupea_2077_22058_1.pdf

selig

Respuestas:

Aquí hay un enfoque divertido de Brock-Nannestad y Schürmann:

Verdaderas abstracciones monádicas

La idea es tratar de traducir oraciones de primer orden en lógica monádica de primer orden , "olvidando" algunos de los argumentos. Ciertamente, la traducción no está completa : hay algunas oraciones consistentes que se vuelven inconsistentes después de la traducción.

Sin embargo, la lógica monádica de primer orden es decidible . Por lo tanto, se puede verificar si la traducción de una fórmula es consistente: $\overline F$ $F$

\bar{F} ⊬ ⊥

$\overline F\not\vdash\bot$

puede verificarse mediante un procedimiento de decisión e implica

F ⊬ ⊥

$F\not\vdash\bot$

Lo que implica que tiene un modelo, según el teorema de integridad. $F$

Este tema puede aplicarse de manera algo más general: identifique una sublógica decidible de su problema, luego traduzca su problema en él, de una manera que conserve la verdad. En particular, los solucionadores SMT modernos como Z3 se han vuelto sorprendentemente buenos para demostrar la satisfacción de las fórmulas con cuantificadores (por defecto , pero pueden funcionar bien en las fórmulas ). $\Sigma^0_1$ $\Pi^0_2$

Forzar parece estar muy lejos del alcance de los métodos automatizados en la actualidad.

cody
fuente

Esto me parece sorprendente. Estoy tratando de imaginar traducir la teoría de conjuntos de NBG en lógica monádica, pero no puedo imaginar que sea tan fácil. Me imagino que funciona bien para campos cerrados reales o aritmética previa a la hamburguesa como teorías de primer orden decidibles con modelos finitos, pero me resulta difícil imaginar que funciona para algo tan expresivo como la teoría de conjuntos.

dezakin

Todo es difícil con NGB en razonamiento automatizado. Tenga en cuenta que el objetivo del artículo no es utilizar una sola traducción, sino probar muchas traducciones posibles en busca de un modelo.

cody