Выполнимость первого порядка, которая не имеет конечных моделей

Из теоремы Черча мы знаем, что определение выполнимости первого порядка вообще неразрешимо, но есть несколько методов, которые мы можем использовать для определения выполнимости первого порядка. Наиболее очевидным является поиск конечной модели. Однако в логике первого порядка есть ряд утверждений, которые, как мы можем продемонстрировать, не имеют конечных моделей. Например, любая область, в которой действует инъективная и не сюръективная функция, бесконечна.

Как мы можем продемонстрировать выполнимость для операторов первого порядка, где нет конечных моделей или существование конечных моделей неизвестно? В автоматическом доказательстве теорем мы можем определить выполнимость несколькими способами:

Мы можем отрицать предложение и искать противоречие. Если он найден, мы доказываем правильность утверждения первого порядка и, следовательно, выполнимость.
Мы используем насыщенность с разрешением и исчерпывающие выводы. Чаще всего у нас будет бесконечное количество выводов, поэтому это ненадежно.
Мы можем использовать принуждение, которое предполагает существование модели, а также последовательность теории.

Я не знаю никого, кто бы применял форсирование как механизированную технику для автоматического доказательства теорем, и это выглядит нелегко, но мне интересно, было ли это сделано или предпринято, так как он использовался для доказательства независимости ряда утверждений в теории множеств, которая сама по себе не имеет конечных моделей.

Известны ли другие методы поиска соответствия первого порядка, применимые для автоматического рассуждения, или кто-то работал над алгоритмом автоматического форсирования?

reference-request lo.logic automated-theorem-proving dezakin
источник

Подход Infinox может иметь отношение к вашему вопросу (не отвечая на него). Идея состоит в том, чтобы использовать доказательства теорем для демонстрации несуществования конечных моделей. Смотрите, например, gupea.ub.gu.se/bitstream/2077/22058/1/gupea_2077_22058_1.pdf

Selig

Ответы:

Вот забавный подход Брока-Наннестада и Шюрмана:

Правдивые монадические абстракции

Идея состоит в том, чтобы попытаться перевести предложения первого порядка в монадическую логику первого порядка , «забыв» некоторые аргументы. Конечно, перевод не завершен : есть некоторые непротиворечивые предложения, которые становятся непоследовательными после перевода.

Однако монадическая логика первого порядка разрешима . Поэтому можно проверить, если перевод $\overline F$ формулы $F$ согласуется:

\bar{F} ⊬ ⊥

$\overline F\not\vdash\bot$

может быть проверено процедурой принятия решения и подразумевает

F ⊬ ⊥

$F\not\vdash\bot$

Отсюда следует, что имеет модель по теореме полноты. $F$

Эта тема может применяться несколько в более общем смысле: определить разрешимую подлогику вашей проблемы, а затем перевести вашу проблему в нее таким образом, чтобы сохранить правду. В частности, современные SMT-решатели, такие как Z3, оказались удивительно хорошими в доказательстве выполнимости формул с квантификаторами (по умолчанию , но могут хорошо работать с формулами ). $\Sigma^0_1$ $\Pi^0_2$

В настоящее время форсирование, по-видимому, далеко недоступно для автоматизированных методов.

Коди
источник

Это кажется мне удивительным. Я пытаюсь представить перевод теории множеств NBG в монадическую логику, но не могу себе представить, что это так просто. Я полагаю, что он хорошо работает для реальных замкнутых полей или арифметики Пресбургера в качестве разрешимых теорий первого порядка с уже конечными моделями, но с трудом представляет, что он работает для чего-то столь же выразительного, как теория множеств.

Дезакин

С NGB все сложно в автоматическом рассуждении. Обратите внимание, что смысл статьи не в том, чтобы использовать один перевод, а в том, чтобы попробовать много возможных переводов в поисках модели.

Коди