Имеет ли теория первого порядка конечной структуры ограниченный ранг кванторов?

11

Пусть - любая конечная структура. Имеет ли его теории первого порядка Т : = Т Н ( ) имеют ограниченную кванторное ранг, в том смысле , что существует д ∈ N такое , что для всех ф Е Т с ц г ( φ ) > д существует φ ' ∈ T с д г ( ф ' ) ≤ д и ф ' ≡ ф ?AT:=TH(A)q∈Nφ∈Tqr(φ)>qφ′∈Tqr(φ′)≤qφ′≡φ

co.combinatorics lo.logic relational-structures Д. Русин
источник
Разве это не вопрос к Mathoverflow, а не к теории CS?
Андрей Бауэр
6
@ Андрей, теория конечных моделей и описательная сложность также считаются частью TCS.
Каве
1
Отлично, так как однажды сказал Боб Харпер: математика - это особый случай информатики.
Андрей Бауэр
Информатика также является частным случаем математики, и они также являются частными случаями логики, и наоборот.
Февраль

Ответы:

12

Теория любой конечной структуры полна модели. На самом деле, легко увидеть, что любая формула эквивалентна экзистенциальной формуле с одним квантификатором на каждый элемент структуры, после чего все квантификаторы исходной формулы могут быть смоделированы с помощью конъюнкций и дизъюнкций. В частности, количество квантификаторов (следовательно, ранг квантификаторов) ограничено размером структуры.

Эмиль Йержабек
источник
На самом деле нужен еще один универсальный квантификатор, который позволяет выразить отсутствие дополнительных элементов. Во всех ответах есть одно предположение, которое следует сделать явным: наличие равенства, т. Е. То, что x = y является допустимой атомарной формулой.
Томас С
Дополнительный квантификатор не требуется. Помните, что мы не пытаемся аксиоматизировать теорию структуры, но найти формулу, эквивалентную данной по модулю теории. А наличие равенства является универсальным стандартом для классической логики первого порядка. Его отсутствие должно быть указано.
Эмиль Йержабек
Ах. Вы правы. "Теория Модуло". Относительно равенства: поскольку мы пытаемся объяснить простые вещи людям, не относящимся к Logic, не помешает сделать структуру явной. Еще одно замечание: замена квантификаторов на конъюнкции и дизъюнкции вполне хороша. Однако есть альтернативы: поскольку формула с, скажем, m свободными переменными определяет m-арное отношение A, новая формула, после угадывания всех элементов и проверки, что есть что (по модулю автоморфизмов), также явно «перечисляет» все кортежи, для которых старая формула дает «истина».
Томас С
3

Чтобы сделать то, что сказал Эмиль, немного конкретнее: рассмотрим формулу, выражающую существование k различных объектов. Это показывает, что нам нужно неограниченное количество квантификаторов.

Теперь у вас есть формула с q кванторами, и в вашей модели есть k объектов. Вы можете выразить формулу, заявив, что существует k различных объектов, и связь между ними может быть выражена в виде CNF.

Кава
источник