Аннотация:
C 1969 года большое количество работ было посвящено логике первого порядка случайных структур. На языке графов классический закон нуля или единицы, доказанный Глебским, Коганом, Легоньким, и Талановым в 1969 году (и независимо Фейгиным в 1976 году) утверждает, что любое предложение первого порядка либо истинно на (асимптотически) почти всех графах на $\{1,...,n\}$, либо ложно. С тех пор множество логических законов было доказано для различных распределений на графах и других конечных структур. Как правило, различают три сценария: упомянутый закон нуля или единицы, закон сходимости (то есть для любого предложения существует предел истинности), и отсутствие сходимости.
Для последовательности случайных структур над сигнатурой, содержащей только предикатный символы, мы определяем ее сложность первого порядка как некоторое подмножество в банаховом пространстве $\ell^{\infty}/c_0$. 0-1 закон и закон сходимости в логике первого порядка соответствуют сложностям $\{0,1\}$ и подмножеству $\mathbb{R}$. Мы предложили иерархию классов сложности и ввели стохастическую сводимость, позволяющую переносить результаты о сложности между различными случайными структурами. С помощью этого инструмента нам удалось вывести несколько новых логических предельных законов для биномиальных случайных структур, а также свести некоторые известные результаты к другим.
Совместная работа с Данилой Деминым.
|
