Станислав Олегович Сперанский

Проблемы алгоритмической разрешимости
теорий для алгебры и анализа*

РЕГИСТРАЦИЯ

Описание курса

Теории классов структур в языке логики первого порядка традиционно называют «элементарными»; они являются одним из основных объектов изучения в математической логике и теории алгоритмов. Элементарная теория данного класса — это совокупность свойств, выразимых в соответствующем языке и присущих всем структурам из класса; её алгоритмическая разрешимость означает возможность эффективной проверки «элементарных» свойств над рассматриваемым классом. Многие известные результаты, а также открытые проблемы в математической логике связаны с изучением вычислительных аспектов элементарных теорий различных классов групп, колец и т.п. и их естественных фрагментов. Это классическое и не теряющее актуальности направление исследований, восходящее к фундаментальным работам А. Тарского и А.И. Мальцева.

Важнейший метод доказательства разрешимости для (элементарных) теорий — метод элиминации кванторов. Одним из наиболее известных результатов здесь является теорема Тарского–Зайденберга об элиминации кванторов в теории упорядоченного поля вещественных чисел, совпадающей с теорией вещественно замкнутых полей. Отсюда следует разрешимость соответствующей теории, а также теории поля комплексных чисел, совпадающей с теорией алгебраически замкнутых полей, и элементарной геометрии. Кроме того, отсюда же можно получить решение известной 17-ой проблемы Гильберта, связанной с представимостью неотрицательных рациональных функций в виде сумм квадратов рациональных функций. Другой известный результат — разрешимость теории упорядоченной группы целых чисел по сложению, установленная Пресбургером. Упомянутые результаты заложили основу для новых направлений исследований и в итоге привели к многочисленным применениям в области информатики. Стоит также отметить, что элиминация кванторов в данной теории позволяет получить ценную информацию об определимости в её моделях.

С другой стороны, разрешимые теории встречаются сравнительно редко; большинство же теорий оказываются неразрешимы. Например, первая теорема Гёделя о неполноте (в форме Россера) влечёт неразрешимость теории дискретно упорядоченных колец, а также всех её непротиворечивых надтеорий. Другой яркий пример — неразрешимость теории конечных простых графов и всех её подтеорий. Для переноса результатов о неразрешимости с одних теорий на другие используется техника интерпретаций и её модификации. В частности, с помощью этой техники можно перейти от простых графов к симметрическим группам.

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

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

План курса

1. Экскурс в логику первого порядка. Теории классов структур. Гёделевская нумерация.
2. Метод элиминации кванторов и его применения. Разрешимость теории упорядоченных делимых абелевых групп.
3. Разрешимость теории упорядоченной группы целых чисел по сложению. Определимость в данной группе. Арифметика Пресбургера.
4. Теорема Тарского–Зайденберга и разрешимость теории упорядоченного поля вещественных чисел.
5. Интерпретации между структурами. Разрешимость теории поля комплексных чисел и элементарной геометрии.
6. Алгебраически замкнутые и вещественно замкнутые поля. Применение элиминации кванторов к решению 17-ой проблемы Гильберта.
7. Интерпретации между классами структур. Интерпретации между теориями.
8. Существенная и наследственная неразрешимости. Перенос результатов о неразрешимости посредством интерпретаций.
9. «Минимальная» арифметика и представимость в ней. Существенная неразрешимость теории дискретно упорядоченных колец.
10. Построение наследственно неразрешимой теорий в сигнатуре арифметики.
11. Наследственная неразрешимость теории конечных простых графов.
12. Наследственная неразрешимость теории конечных симметрических групп (с помощью теории двух эквивалентностей на общем конечном носителе).
13. Элементарный язык вероятностных пространств. Безатомные пространства. Разрешимость теории безатомных вероятностных пространств.
14. Наследственная неразрешимость теории конечных вероятностных пространств.
15. Язык арифметики второго порядка. Монадическая (второпорядковая) определимость в структуре натуральных чисел со сложением. Вычислимая эквивалентность теории дискретных вероятностных пространств и полной арифметики второго порядка.
16. Обзор результатов, связанных с векторными пространствами, метрическими пространствами и нормированными пространствами.

Литература

• Ю.Л. Ершов, Е.А. Палютин. Математическая логика. 6-е издание. Физматлит, 2011.
• Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 2: Языки и исчисления. 4-е издание. Издательство МЦНМО, 2012.
• Х. Роджерс. Теория рекурсивных функций и эффективная вычислимость / Пер. с англ. В.А. Душского, М.И. Кановича и Е.Ю. Ногиной под ред. В.А. Успенского. Мир, 1972. На англ.: H. Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967.
• С. О. Сперанский. On the decision problem for quantified probability logics. Известия РАН. Серия математическая 89(3), im9652, 2025.
• P.J. Cohen. Decision procedures for real and p-adic fields. Communications of Pure and Applied Mathematics XXII, 131–151, 1969.
• H.B. Enderton. A Mathematical Introduction to Logic. 2nd edition. Academic Press, 2001.
• S.O. Speranski. A note on definability in fragments of arithmetic with free unary predicates. Archive for Mathematical Logic 52, 507–516, 2013.
• S.O. Speranski. An ‘elementary’ perspective on reasoning about probability spaces. Logic Journal of the IGPL, jzae042, 2024.