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

Материалы

• Конспект

• Вопросы к теоретическому зачёту

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

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

• Репозиторий: описание и образцы решения 0-й практической задачи

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

• Текущая таблица результатов

Лекция 1

Введение издалека: общая топология

• Определения и примеры
• Связность

Где почитать

• Глава 2 из конспекта
• Виро О.Я., Иванов О.А., Нецветаев Н.Ю., Харламов В.М., Элементарная топология

Лекция 2

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

• Язык исчисления высказываний
• Общезначимость
• Выводимость
• Теорема о дедукции

Где почитать

• Главы 3-4 из конспекта

Разбор домашнего задания №1

Лекция 3

Исчисление высказываний: теоремы

• Теорема о дедукции
• Теорема о корректности
• Теорема о полноте

Интуиционистское исчисление высказываний: введение

• BHK-интерпретация логических связок
• Теоретико-множественная интерпретация логических связок
• Формализация интуиционистской логики: варианты 10 аксиомы.
• Топологическая интерпретация логических связок

Где почитать

• В.Е.Плиско, В.Х.Хаханян, Интуиционистская логика, Мех-Мат МГУ 2009 (http://lpcs.math.msu.su/~plisko/intlog.pdf)

Лекция 4

Интуиционистское исчисление высказываний

• Ещё раз о философии, мотивация определений
• Теорема Гливенко (формулировка)
• Решётки: общее определение, дистрибутивная, импликативная

Где почитать

• В.Е.Плиско, В.Х.Хаханян, Интуиционистская логика, Мех-Мат МГУ 2009 (http://lpcs.math.msu.su/~plisko/intlog.pdf)

Лекция 5

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

• Алгебры Гейтинга и Булевы алгебры
• Алгебра Линденбаума
• Полнота Алгебр Гейтинга как моделей ИИВ

Где почитать

• В.Е.Плиско, В.Х.Хаханян, Интуиционистская логика, Мех-Мат МГУ 2009 (http://lpcs.math.msu.su/~plisko/intlog.pdf)

Лекция 6

Качественные свойства ИИВ

• Модели Крипке
• Модель Крипке есть алгебра Гейтинга
• Нетабличность ИИВ
• Гёделевы алгебры
• Гёделевизация алгебры Линденбаума
• Гомоморфизм алгебр Гейтинга

Где почитать

• В.Е.Плиско, В.Х.Хаханян, Интуиционистская логика, Мех-Мат МГУ 2009 (http://lpcs.math.msu.su/~plisko/intlog.pdf)

Лекция 7

Дизъюнктивность ИИВ и исчисление предикатов

• Дизъюнктивность ИИВ (⊢α∨β влечёт ⊢α или ⊢β)
• Язык исчисления предикатов

Лекция 8

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

• Структуры и модели в ИП, предметное множество
• Свободные и связанные вхождения, свобода для подстановки
• Аксиомы и правила вывода в ИП
• Теорема о дедукции
• Теорема о корректности ИП (начало)

Где почитать

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

Лекция 9

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

• Теорема о корректности ИП
• Непротиворечивое множество замкнутых формул / замкнутых бескванторных формул
• Модель для непротиворечивого множества з.ф. / з.б.ф.
• Следствие в ИП
• Теорема Гёделя о полноте ИП (формулировка)

Где почитать

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

Лекция 10

Формальная арифметика и рекурсивные функции

• Аксиоматика Пеано
• Теория 1 порядка
• Формальная арифметика
• Примитивно-рекурсивные функции

Где почтитать

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

Лекция 11

Представимость функций в формальной арифметике

• Минимизация. Рекурсивные функции.
• Бета-функция Гёделя.
• Представимость рекурсивных функций в формальной арифметике.

Где почтитать

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

Лекция 12

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

• Гёделева нумерация.
• Любая представимая в формальной арифметике функция рекурсивна.
• Формулировка и идея доказательства первой теоремы Гёделя о неполноте арифметики.

Где почтитать

• Э. Мендельсон. Введение в математическую логику. М. "Наука", 1971

Лекция 13

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

• Первая теорема Гёделя о неполноте формальной арифметики (с доказательством).
• Первая теорема Гёделя о неполноте формальной арифметики в форме Россера.
• Условия выводимости Гильберта-Бернайса-Лёба.
• Вторая теорема Гёделя о неполноте формальной арифметики (с кратким изложением доказательства).

Где почтитать

• Э. Мендельсон. Введение в математическую логику. М. "Наука", 1971

Лекция 14

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

• Мотивация создания теории множеств.
• Краткое изложение аксиоматики Цермело-Френкеля.