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