#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Logic Online Seminar (https://www.mathnet.ru/eng/conf876), Monday 16:00 MSK (UTC+3), MIAN Room 313 + Kontur Talk (очный доклад)

4.08.2025 М. Жуковский (Университет Шеффилда, https://www.maksimzhukovskii.com/): Сложность первого порядка конечных случайных структур
C 1969 года большое количество работ было посвящено логике первого порядка случайных структур. На языке графов классический закон нуля или единицы, доказанный Глебским, Коганом, Легоньким, и Талановым в 1969 году (и независимо Фейгиным в 1976 году) утверждает, что любое предложение первого порядка либо истинно на (асимптотически) почти всех графах на {1,...,n}, либо ложно. С тех пор множество логических законов было доказано для различных распределений на графах и других конечных структур. Как правило, различают три сценария: упомянутый закон нуля или единицы, закон сходимости (то есть для любого предложения существует предел истинности), и отсутствие сходимости. Для последовательности случайных структур над сигнатурой, содержащей только предикатные символы, мы определяем её сложность первого порядка как некоторое подмножество в банаховом пространстве ℓ∞/c0. 0-1 закон и закон сходимости в логике первого порядка соответствуют сложностям {0,1} и подмножеству R. Мы предложили иерархию классов сложности и ввели стохастическую сводимость, позволяющую переносить результаты о сложности между различными случайными структурами. С помощью этого инструмента нам удалось вывести несколько новых логических предельных законов для биномиальных случайных структур, а также свести некоторые известные результаты к другим.

Совместная работа с Данилой Деминым.

➰ ВК