Элементарные (т.е. первопорядковые) теории — ключевой объект изучения в математической логике. Многие известные результаты связаны с изучением алгоритмических свойств элементарных теорий различных классов структур (графов, групп, решёток, колец и т.п.) и их фрагментов.

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

(1) упорядоченной группы целых чисел по сложению;
(2) упорядоченного поля вещественных чисел.

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

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

Программа курса

1.  Краткий экскурс в классическую логику первого порядка.
2.  Краткий экскурс в теорию вычислимости. Кодирование формул и теорий.
3.  Метод элиминации кванторов. Разрешимость теории плотных линейных порядков без концов; сопутствующие результаты об определимости и аксиоматизации.
4.  Разрешимость теории упорядоченной группы целых чисел по сложению; сопутствующие результаты об определимости и аксиоматизации.
5.  Разрешимость теории упорядоченного поля вещественных чисел; сопутствующие результаты об определимости и аксиоматизации.
6.  Сильная неразрешимость теории дискретно упорядоченных колец. Другие результаты о разрешимости и неразрешимости, связанные с кольцами и полями.
7.  Метод интерпретации (относительной элементарной определимости). Наследственная неразрешимость теорий различных классов структур (графов, групп, решёток и т.п.) и их фрагментов.
8.  Степени неразрешимости теорий.

Основная литература
[1] Ю.Л. Ершов, И.А. Лавров, А.Д. Тайманов, М.А. Тайцлин, Элементарные теории. Успехи математических наук, 20 (124) (1965), № 4, с. 37-108.
[2] P.J. Cohen, Decision procedures for real and p-adic fields. Communications of Pure and Applied Mathematics, XXII (1969), p. 131–151.
[3] H.B. Enderton, A Mathematical Introduction to Logic. 2nd ed. Academic Press, 2001.
[4] A. Nies, Undecidable fragments of elementary theories. Algebra Universalis, 35 (1996), p. 8-33.
[5] H. Rogers, Jr., Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967. Рус. пер.: Х. Роджерс, Теория рекурсивных функций и эффективная вычислимость. Пер. с англ. В.А. Душского, М.И. Кановича и Е.Ю. Ногиной под ред. В.А. Успенского. М., Мир, 1972.
[6] A. Tarski, A Decision Method for Elementary Algebra and Geometry. 2nd ed. University of California Press, 1951.
[7] A. Tarski, A. Mostowski, R.M. Robinson, Undecidable Theories. North-Holland Publishing Company, 1971.

Программа

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

Финансовая поддержка
Курс проводится при финансовой поддержке Минобрнауки России (грант на создание и развитие МЦМУ МИАН, соглашение №  075-15-2022-265).

Организации
Математический институт им. В.А. Стеклова Российской академии наук, г. Москва
Математический центр мирового уровня «Математический институт им. В.А. Стеклова Российской академии наук» (МЦМУ МИАН)