Семинары по курсу «Введение в математическую логику и теорию алгоритмов», 2023, группы 209/210.

Страница курса.

Ссылка на таблицу с баллами в группах 209/210.

Решённые задачи из листочков (см.ниже) сдавайте Максиму Вишникину. Можно договориться с ним о встрече в университете или о созвоне. Его почта maxim.vishnikin@gmail.com. Сдавать задачи мне тоже можно.

Мои контакты: почта ansidiana@yandex.ru, телеграм @ansidiana.

Листочки с задачами.

Дедлайн указан для групп 209/210 (до косой черты — для группы 209, после косой черты — для группы 210). Задачи после черты довольно сложные, поэтому их можно сдавать вплоть до конца семестра.
Листок 1. Теория множеств. Сдать до 05.10/28.09.
Листок 2. Вполне упорядоченные множества и логические языки.. Сдать до 19.10/12.10.
Листок 3. Элиминация кванторов и модальная логика. Сдать до 02.11/26.10.
Листок 4. Теории с равенством и теорема о компактности. Сдать до 16.11/09.11.
Листок 5. Теория моделей. Сдать до 30.11/23.11.
Листок 6. Выразимость. Сдать до 14.12/07.12.
Листок 7. Вычислимость, разрешимость, перечислимость. Сдать до 21.12/14.12.

Лог семинаров в группах 209/210.

• Семинар 1, 13.09/6.09. Наивная теория множеств [ВШ-1, 1.1], равномощные множества [ВШ-1, 1.3], теорема Кантора [ВШ-1, 1.6], теорема Кантора-Бернштейна [ВШ-1, 1.5], вполне упорядоченные множества [ВШ-1, 2.4], аксиома выбора, теорема Цермело и лемма Цорна [ВШ-1, 2.5-2.8].
• Семинар 2, 27.09/20.09. Формулы [ВШ-2, 3.1], истинность формулы в структуре [ВШ-2, 3.2], выполнимые и общезначимые формулы [ВШ-2, 4.1]. Предварённая нормальная форма [ВШ-2, 4.7].
• Семинар 3, 10.10/08.10. Элиминация кванторов [ВШ-2, 3.6]. Модальная логика, модели Крипке [Шап, лекция 1; CZ, 3.1, 3.2], задание свойств отношения R на множестве W модальной формулой [CZ, 3.5].
• Семинар 4, 24.10/22.10. Теории с равенством [ВШ-2, 5.1], спектр замкнутой формулы [ВШ-2, 5.2]. Теорема о компактности [ВШ-2, 4.5].
• Семинар 5, 08.11/01.11. Изоморфизм и элементарная эквивалентность [ВШ-2, 3.9]. Теоремы Лёвенгейма-Сколема [ВШ-2, 5.2 и 3.11]. Полные теории, категоричные в данной мощности теории, признак Лося-Воота, разрешимые теории [ВШ-2, 5.3 и 5.4].
• Семинар 6, 22.11/15.11. Выразимые предикаты [ВШ-2, 3.3], доказательство невыразимости при помощи автоморфизмов [ВШ-2, 3.5] и элиминации кванторов [ВШ-2, 3.6].
• Семинар 7, 07.12/29.11. Вычислимые функции [ВШ-3, 1.1], разрешимые множества [ВШ-3, 1.2], перечислимые множества [ВШ-3, 1.3], теорема Поста [ВШ-3, 1.4], некоторые свойства перечислимых множеств [ВШ-3, 1.5], универсальная вычислимая функция [ВШ-3, 2.1], диагональная функция [ВШ-3, 2.2], существование перечислимого неразрешимого множества [ВШ-3, 2.3].
• Семинар 8, 14.12. Колмогоровская сложность [ВУШ, достаточно прочитать раздел «О чём эта книга?»]. Формальные грамматики и конечные автоматы [ПП, главы 1, 2]. Запись семинара.

Рекомендуемая литература.

1. [ВШ-1] Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 1. Начала теории множеств
2. [ВШ-2] Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления
3. [ВШ-3] Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции
4. [CZ] Chagrov A., Zakharyaschev M. Modal logic.
5. [Шап] Шапировский И.Б. Конспект курса «Введение в модальную логику».
6. [ВУШ] Верещагин Н. К., Успенский В.А., Шень А. Колмогоровская сложность и алгоритмическая случайность
7. [ФБ] А. Френкель, И. Бар-Хиллел. Основания теории множеств.
8. [ПП] А.Е. Пентус, М.Р.Пентус. Теория формальных языков.