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

Cсылка на таблицу с баллами.

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

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

Лог семинаров.

  • Семинар 1, 14.09/07.09. Наивная теория множеств [ВШ-1, 1.1], равномощные множества [ВШ-1, 1.3], теорема Кантора [ВШ-1, 1.6], теорема Кантора-Бернштейна [ВШ-1, 1.5], вполне упорядоченные множества [ВШ-1, 2.4].
  • Семинар 2, 28.09/21.09. Аксиома выбора, теорема Цермело и лемма Цорна [ВШ-1, 2.5-2.8]. Формулы [ВШ-2, 3.1], истинность формулы в структуре [ВШ-2, 3.2], выполнимые и общезначимые формулы [ВШ-2, 4.1].
  • Семинар 3, 12.10/05.10. Элиминация кванторов [ВШ-2, 3.6]. Теорема о компактности [ВШ-2, 4.5].
  • Семинар 4, 26.10/19.10. Модальная логика, модели Крипке [Шап, лекция 1; CZ, 3.1, 3.2], задание свойств отношения R на множестве W модальной формулой [CZ, 3.5]. Теории с равенством [ВШ-2, 5.1], спектр замкнутой формулы [ВШ-2, 5.2].
  • Семинар 5, 09.11/02.11. Изоморфизм и элементарная эквивалентность [ВШ-2, 3.9]. Теоремы Лёвенгейма-Сколема [ВШ-2, 5.2 и 3.11]. Полные теории, категоричные в данной мощности теории, признак Лося-Воота[ВШ-2, 5.3 и 5.4].
  • Семинар 6, 23.11/21.11. Выразимые предикаты [ВШ-2, 3.3], доказательство невыразимости при помощи автоморфизмов [ВШ-2, 3.5] и элиминации кванторов [ВШ-2, 3.6].
  • Семинар 7, 07.12/30.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].

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

Листочки периодически обновляются! (Добавляются комментарии, уточнения к формулировкам и т.д.). Ссылки остаются прежними. Прежде чем сдавать задачи, убедитесь, что посмотрели самую свежую версию!
Дедлайн указан для групп 209/211 (до косой черты — для группы 209, после косой черты — для группы 211). Задачи после черты довольно сложные, поэтому их можно сдавать вплоть до конца семестра.

Дедлайн сдачи задач после черты — 22 декабря.

Листок 1. Теория множеств. Сдать до 29.09/22.09.
Листок 2. Аксиома выбора и формальные языки. Сдать до 13.10/06.10.
Листок 3. Элиминация кванторов. Теорема о компактности. Сдать до 27.10/20.10.
Листок 4. Модальная логика. Теории с равенством. Сдать до 10.11 24.11/03.11.
Листок 5. Теория моделей. Сдать до 24.11/17.11.
Листок 6. Выразимость. Сдать до 08.12/08.12.
Листок 7. Теория алгоритмов. Сдать до 22.12/22.12.

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

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