Введение в математическую логику и теорию алгоритмов

Автор программы курса: Беклемишев Лев Дмитриевич

Аннотация

В курсе рассматриваются базовые понятия математической логики и теории алгоритмов. Изучается аксиоматика теории множеств и её применение в различных областях математики. Рассматривается классическая логика высказываний и предикатов, начала теории моделей (теорема о компактности, теорема Лёвенгейма-Сколема). Представлены основные результаты теории алгоритмов.

Необходимые базовые знания для прохождения курса.

Курс математики основной школы.

План курса

Лекция 1. Теория множеств Цермело-Френкеля. Аксиомы равенства, пары, объединения, степени, выделения. Функции, упорядоченные пары, декартово произведение.

Лекция 2. Бинарные отношения, отношение эквивалентности, фактор-множество. Множества целых и рациональных чисел. Свойства функций (функциональность, тотальность, инъективность, сюръективность). Сечения и определение вещественных чисел.

Лекция 3. Построение натуральных чисел как минимального по включению индуктивного множества. Принцип индукции, порядковой индукции, наименьшего числа. Аксиомы Дедекинда-Пеано. Принцип Дирихле.

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

Лекция 5. Трансфинитная рекурсия.

Лекция 6. Аксиома выбора, теорема Цермело, лемма Цорна. Пример применения леммы Цорна: всякое векторное пространство имеет базис.

Лекция 7. Доказательство эквивалентности аксиомы выбора, теоремы Цермело и леммы Цорна. Аксиома регулярности, аксиома подстановки.

Лекция 8. Логика высказываний. Синтаксис логики высказываний. Семантика, истинностные значения формул. Дизъюнктивная и конъюнктивная нормальные формы.

Лекция 9. Логика предикатов. Примеры моделей: арифметика, кольца, модель Пуанкаре геометрии Лобачевского. Термы и формулы логики предикатов. Семантика логики предикатов.

Лекция 10. Гомоморфизмы, изоморфизмы, автоморфизмы моделей. Предварённая нормальная форма.

Лекция 11. Модель теории. Нормальные модели. Теорема Тарского о полноте и разрешимости элементарной геометрии. Аксиомы и правила вывода исчисления предикатов.

Лекция 12. Теорема о дедукции. Теорема Гёделя о полноте. Теорема Гёделя-Мальцева о компактности. Нестандартные модели арифметики.

Лекция 13. Теорема Лёвенгейма-Сколема об элементарной подмодели. Теорема Мальцева о повышении мощности. Понятие алгоритма. Тезис Чёрча-Тьюринга. Машина Тьюринга.

Лекция 14. Функции, вычислимые на машине Тьюринга. Разрешимые и перечислимые множества.

Лекция 15. Эквивалентные определения перечислимого множества. Теорема Поста. Разрешимые теории. Универсальная вычислимая функция.

Лекция 16. Перечислимое неразрешимое множество. Неразрешимость проблемы остановки. Главная универсальная функция. Теорема Успенского-Райса.

Литература

1. Крупский В.Н., Плиско В.Е. Математическая логика и теория алгоритмов. — М.: Академия, 2013. — 416 с.
2. Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов.
3. Часть 1. Начала теории множеств, издание 5-е, исправленное. — М.: МЦНМО, 2017. — 112 с.
4. Часть 2. Языки и исчисления, издание 5-е, исправленное. — М.: МЦНМО, 2017. — 240 с.
5. Часть 3. Вычислимые функции, издание 5-е, исправленное. — М.: МЦНМО, 2017. — 160 с.
6. Мендельсон Э. Введение в математическую логику. — М.: Наука, 1971. — 320 с.
7. Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. 2-е изд. — М.: Физматлит, 2002. — 128 с.
8. Колмогоров А. Н., Драгалин А. Г. Математическая логика. — М.: УРСС, 2004. — 240 с.
9. Лавров И. А., Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов, 3-е изд. — М.: Физматлит, 1995. — 256 с.
10. Клини С. К. Математическая логика. — М.: Мир, 1973. — 480 с.
11. Лавров И. А. Математическая логика. — М.: Академия, 2006. — 240 с.
12. Крупский В. Н., Плиско В. Е. Теория алгоритмов. — М.: Академия, 2009. — 208 с.

Дополнительная информация

Отчётность по курсу: сдача устного экзамена в конце семестра. 

.