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

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

(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.

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

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