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

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

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

28.12.2022 старостам разослан список студентов, получивших бонусы.

Решённые задачи из листочков (см.ниже) высылайте мне на электронную почту ansidiana@yandex.ru или в телеграм @ansidiana. Необходимо будет коротко обсудить свои решения (без состоявшегося обсуждения баллы не ставятся).
Также задачи можно сдавать Максиму Вишникину — договаривайтесь с ним о встрече в университете, его почта maxim.vishnikin@gmail.com.

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

Дедлайн указан для групп 208/210 (до косой черты — для группы 208, после косой черты — для группы 210). Задачи после черты сложные — их можно сдавать вплоть до конца семестра.

Листок 1. Теория множеств. Сдать до 27.09/25.09.
Листок 2. Логические языки. Сдать до 11.10/09.10.
Листок 3. Модальная логика. Сдать до 25.10/23.10.
Листок 4. Компактность. Сдать до 08.11/06.11.
Листок 5. Теория моделей. Сдать до 22.11/20.11.
Листок 6. Выразимость. Сдать до 06.12/04.12.
Листок 7 (дополнительный). By myself. Можно сдавать до конца семестра.
Листок 8. Вычислимость. Сдать до 20.12/18.12.

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

• Семинар 1, 12.09/10.09. Наивная теория множеств [ВШ-1, 1.1], равномощные множества [ВШ-1, 1.3], теорема Кантора-Бернштейна [ВШ-1, 1.5], вполне упорядоченные множества [ВШ-1, 2.4], аксиома выбора, теорема Цермело и трансфинитная индукция [ВШ-1, 2.5-2.7].
• Семинар 2, 26.09/24.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], минимальная модальная логика К [CZ, 3.6], модальная логика S4 [CZ, 3.8].
• Семинар 4, 24.10/22.10. Теории с равенством [ВШ-2, 5.1], спектр замкнутой формулы [ВШ-2, 5.2]. Теорема о компактности (ВШ-2, 4.5).
• Семинар 5, 07.11/05.11. Теоремы Лёвенгейма-Сколема (ВШ-2, 5.2 и 3.11). Элементарная эквивалентность [ВШ-2, 3.9]. Полные теории, категоричные в данной мощности теории, признак Лося-Воота, разрешимые теории [ВШ-2, 5.3 и 5.4].
• Семинар 6, 21.11/19.11. Выразимые предикаты [ВШ-2, 3.3], доказательство невыразимости при помощи автоморфизмов [ВШ-2, 3.5].
• Семинар 7, 05.12/03.12. Вычислимые функции [ВШ-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, 19.12/17.12. Колмогоровская сложность [ВУШ, достаточно прочитать раздел «О чём эта книга?»]. Исчисление логики отношений [ВШ-2, 4.2-4.4]. Аксиомы теории множеств [ФБ, глава II].

Задачи для подготовки к экзамену.

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

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