Курс математической логики, КТ, весна 2022

Материалы

• Конспект 2018 года

• Конспект 2011 года

• Теоретические домашние задания

• Краткая инструкция по утилите make

Лекция 1

Исчисление высказываний

• Немного об истории вопроса
• Язык исчисления высказываний
• Доказательство высказываний, выводимость

Где почитать

• Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Языки и исчисления. https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf
• Конспекты 2011 и 2018 года по логике.
• О противоречиях в математическом анализе: Джордж Беркли, «Аналитик. Беседа, адресованная неверному математику: где исследуется, являются ли объект, принципы и выводы современного анализа более отчетливо задуманы или более явно выведены, чем религиозные мистерии и точки веры» --- М.: Мысль, 1978

Лекция 2

Теоремы об исчислении высказываний

• Теория моделей, оценка высказываний.
• Следование, корректность, полнота
• Теорема о дедукции
• Теорема о корректности И.В.
• Теорема о полноте И.В.
• Введение в интуиционистское исчисление высказываний

Где почитать

• Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Языки и исчисления. https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf
• Конспекты 2011 и 2018 года по логике.
• Morten Heine B. Sørensen, Pawel Urzyczyn: Lections on the Curry-Howard Isomorphism https://disi.unitn.it/~bernardi/RSISE11/Papers/curry-howard.pdf
• В.Е.Плиско, В.Х.Хаханян, Интуиционистская логика, Мех-Мат МГУ 2009 (http://lpcs.math.msu.su/~plisko/intlog.pdf)

Лекция 3

Модели интуиционистского исчисления высказываний

• Общая топология, базовые определения
• Натуральный вывод
• Решётки

Где почитать

• О. Я. Виро, О. А. Иванов, Н. Ю. Нецветаев, В. М. Харламов. Элементарная топология. --- М.: Издательство МЦНМО, 2010
• В.Е.Плиско, В.Х.Хаханян, Интуиционистская логика, Мех-Мат МГУ 2009 (http://lpcs.math.msu.su/~plisko/intlog.pdf)
• Morten Heine B. Sørensen, Pawel Urzyczyn: Lections on the Curry-Howard Isomorphism https://disi.unitn.it/~bernardi/RSISE11/Papers/curry-howard.pdf

Лекция 4

Теоремы об интуиционистской логике

• Алгебра Линденбаума
• Дизъюнктивность ИИВ
• Модели Крипке
• Нетабличность ИИВ

Где почитать

• В.Е.Плиско, В.Х.Хаханян, Интуиционистская логика, Мех-Мат МГУ 2009 (http://lpcs.math.msu.su/~plisko/intlog.pdf)
• Morten Heine B. Sørensen, Pawel Urzyczyn: Lections on the Curry-Howard Isomorphism https://disi.unitn.it/~bernardi/RSISE11/Papers/curry-howard.pdf

Лекция 5

Исчисление предикатов

• Язык исчисления предикатов
• Оценки формул исчисления предикатов
• Свобода вхождения, свобода для подстановки
• Теорема о дедукции для исчисления предикатов
• Следование

Где почитать

• Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Языки и исчисления. https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf
• Конспекты 2011 и 2018 года по логике.
• Слайды к лекции (05-lection-predicate)

Лекция 6

Теорема Гёделя о полноте исчисления предикатов

• Непротиворечивые множества формул
• Модели для непротиворечивых множеств формул
• Теорема Гёделя о полноте исчисления предикатов
• Следствие о полноте исчисления предикатов

Где почитать

• П.Дж. Коэн, Теория множеств и континуум-гипотеза --- М.: Изд-во <<Мир>>, 1969.
• Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Языки и исчисления. https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf
• Конспекты 2011 и 2018 года по логике.
• Слайды к лекции (06-lection-completeness)

Лекция 7

Неразрешимость исчисления предикатов, аксиоматика Пеано и формальная арифметика

• Машина Тьюринга
• Теорема о неразрешимости исчисления предикатов
• Аксиоматика Пеано
• Формальная арифметика

Где почитать

• П.Дж. Коэн, Теория множеств и континуум-гипотеза --- М.: Изд-во <<Мир>>, 1969.
• Конспекты 2011 и 2018 года по логике.

Лекция 8

Представимость рекурсивных функций в формальной арифметике. Теорема Гёделя о неполноте арифметики.

• Рекурсивные функции.
• Представимость рекурсивных функций в формальной арифметике.
• Рекурсивность представимых в формальной арифметике функций.
• Самоприменимость.
• Формулировка первой теоремы Гёделя о неполноте арифметики.

Где почитать

• П.Дж. Коэн, Теория множеств и континуум-гипотеза --- М.: Изд-во <<Мир>>, 1969.
• Конспекты 2011 и 2018 года по логике.
• Э. Мендельсон, Введение в математическую логику --- М.: Изд-во <<Наука>>, 1971.

Лекция 9

Теоремы Гёделя о неполноте арифметики

• Омега-непротиворечивость.
• Первая теорема Гёделя о неполноте арифметики.
• Теорема Гёделя о неполноте арифметики в форме Россера.
• Consis
• Условия выводимости Гильберта-Бернайса-Лёфа.
• Лемма об автоссылках, другая формулировка теоремы Гёделя о неполноте арифметики.
• Вторая теорема Гёделя о неполноте арифметики.

Где почитать

• П.Дж. Коэн, Теория множеств и континуум-гипотеза --- М.: Изд-во <<Мир>>, 1969.
• Конспекты 2011 и 2018 года по логике.
• Гилберт Д., Бернайс П., Основания математики --- М.: Изд-во <<Наука>>, 1982.

Лекция 10

Теория множеств

• История возникновения теории
• Аксиомы теории множеств
• Ординалы

Где почитать

• П.Дж. Коэн, Теория множеств и континуум-гипотеза --- М.: Изд-во <<Мир>>, 1969.
• Конспекты 2011 и 2018 года по логике.
• Френкель А.А., Бар-Хиллел И. Основания теории множеств. --- УРСС, 2010

Лекция 11

Теория множеств, мощность множеств

• Равномощные множества
• Кардинальные числа
• Теорема Кантора
• Теорема Кантора-Бернштейна

Где почитать

• П.Дж. Коэн, Теория множеств и континуум-гипотеза --- М.: Изд-во <<Мир>>, 1969.
• Конспекты 2011 и 2018 года по логике.
• Френкель А.А., Бар-Хиллел И. Основания теории множеств. --- УРСС, 2010
• Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Начала теории множеств. https://www.mccme.ru/free-books/shen/shen-logic-part1.pdf

Лекция 12

Теорема Лёвенгейма-Сколема

• Счётная аксиоматизация теории
• Теорема Лёвенгейма-Сколема
• Парадокс Сколема

Где почитать

• П.Дж. Коэн, Теория множеств и континуум-гипотеза --- М.: Изд-во <<Мир>>, 1969.
• Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Языки и исчисления. https://www.mccme.ru/free-books/shen/shen-logic-part2-2.pdf

Лекция 13

Непротиворечивость формальной арифметики

• Система S_\infty
• Сведение непротиворечивости формальной арифметики к непротиворечивости S_\infty
• Непротиворечивость S_\infty

Где почитать

• Э. Мендельсон, Введение в математическую логику --- М.: Изд-во <<Наука>>, 1971.