Математическая логика — 2

Обязательный курс для студентов кафедры математической логики и теории алгоритмов, часть 2 (весна 2020)

Руководители: акад. РАН Л. Д. Беклемишев, доц. В. Н. Крупский, доц. Т. Л. Яворская, асс. С. Л. Кузнецов

Курс в весеннем полугодии читает к. ф.-м. н. С. Л. Кузнецов, по четвергам в 16:45 в ауд. 13-02 в режиме прямой трансляции (см. ниже). Чтение обновлённой версии курса в 2020 г. поддержано грантом фонда «БАЗИС».

Текущие события

• Лекции спецкурса «Математическая логика» в 2019–20 учебном году завершились.
• Московский университет с 17 марта был закрыт на карантин из-за коронавируса. Лекции №№ 6–16 второй части курса были прочитаны в прямой трансляции с помощью платформ YouTube и MathNet. Лектор благодарит отдел компьютерных сетей и информационных технологий Математического института им. В. А. Стеклова РАН и лично Д. Е. Чебукова за организационно-техническую поддержку.
• Онлайн-встреча (вебинар) с общим обзором курса и ответами на вопросы студентов состоялась в четверг 14 мая в 16:00 на платформе Zoom. Встречу провели С. Л. Кузнецов и Т. Л. Яворская. Доступна видеозапись.
• Приём экзаменов по курсу также будет организован дистанционно. Студенты, желающие (или обязанные) сдавать экзамен, благоволят обратиться к одному из руководителей курса — например, к С. Л. Кузнецову по электронной почте sk@mi-ras.ru

Лекция № 1 (прочитана 13.02.2020); видео на YouTube

Примитивно-рекурсивные функции. Кодирование последовательностей \( [a_0, a_1, \ldots, a_{\ell - 1} ] \mapsto p_0^{a_0+1} p_1^{a_1+1} \ldots p_{\ell - 1}^{a_{\ell-1} + 1} \). Кодирование пар. Совместная рекурсия. Возвратная рекурсия. Функция Аккермана.

Лекция № 2 (прочитана 20.02.2020); видео на YouTube

Арифметика Пеано PA (формулировка как теории 1-го порядка). Доказательства простейших свойств натуральных чисел в PA. Доказуемо тотальные функции в теориях 1-го порядка, теорема о консервативном расширении новым функциональным символом для такой функции (псевдотермы). Деление с остатком в PA. Две леммы о взаимной простоте: \( \mathrm{PA} \vdash a, b > 1 \wedge a, b \mbox{ вз. просты} \to \exists x, y \, (ax + 1 = by) \) и \( \mathrm{PA} \vdash p \mbox{ простое} \wedge p \mid a b \to p \mid a \vee p \mid b \).

Лекция № 3 (прочитана 27.02.2020); видео на YouTube

Наименьшее общее кратное (НОК) для конечного набора чисел (значений псевдотерма) в PA, его доказуемая тотальность. Китайская теорема об остатках (доказательство в PA). Бета-функция Гёделя, леммы Гёделя о бета-функции. Ограниченные кванторы, класс формул Δ₀. Класс формул Σ₁, его замкнутость (с точностью до эквивалентности в PA) относительно конъюнкции, дизъюнкции, квантора существования и ограниченного квантора всеобщности.

Лекция № 4 (прочитана 05.03.2020); видео на YouTube

Σ₁-полнота PA. Доказуемая тотальность примитивно-рекурсивных функций в PA, доказуемость рекурсивных условий.

Лекция № 5 (прочитана 12.03.2020)

Гёделева нумерация термов и формул. Предикат доказательства. Предикат доказуемости. Функция подстановки, её примитивно-рекурсивность. 1-е и 2-е условия доказуемости Гильберта – Бернайса – Лёба. Параметрическая версия 2-го условия доказуемости.

Лекция № 6 (прочитана 23.03.2020); видео на MathNet

Доказуемая параметрическая Δ₀-полнота. Доказуемая Σ₁-полнота. 3-е условие доказуемости Гильберта – Бернайса – Лёба. Теорема о неподвижной точке.

Лекция № 7 (прочитана 27.03.2020); видео на MathNet

Гёделевы теории, расширяющие PA, предикат доказуемости для гёделевой теории. 1-я и 2-я теоремы Гёделя о неполноте. Россеровский предикат доказуемости, теорема Гёделя – Россера. Теорема Лёба и формализованная теорема Лёба. Теорема Тарского о невыразимости арифметической истинности. Алгоритмическая неразрешимость PA.

Лекция № 8 (прочитана 06.04.2020); видео на MathNet; слайды

Интуиционистская логика первого порядка (FO-Int). BHK-семантика. Модели Крипке для FO-Int. Теорема корректности. Формула сдвига двойного отрицания и отсутствие свойства конечных моделей у FO-Int. Принцип постоянства области (CD).

Лекция № 9 (прочитана 09.04.2020); видео на MathNet; слайды

Полнота FO-Int по Крипке. Следствия из теоремы полноты. Полнота FO-Int+CD относительно моделей Крипке с постоянными областями.

Лекция № 10 (прочитана 13.04.2020); видео на MathNet; слайды

Теоремы Харропа (дизъюнктивная и экзистенциальная). Теорема Эрбрана.

Лекция № 11 (прочитана 16.04.2020); видео на MathNet; слайды

Погружение классической логики в интуиционистскую: переводы Куроды и Гёделя – Генцена.

Лекция № 12 (прочитана 20.04.2020); видео на MathNet; слайды

Теории с разрешимым равенством и функциональными символами: полнота по Крипке. Интуиционистская арифметика.

Для знакомства с интуиционистской логикой первого порядка (с несколько другой, синтаксической точки зрения) также советуем послушать следующие лекции академика Л. Д. Беклемишева по курсу «Вычислительная теория доказательств и лямбда-исчисление»:

№ 15 (23.03.2020):

Интуиционистское исчисление первого порядка (гильбертовский и генценовский формат).

№ 16 (26.03.2020):

Негативная интерпретация классической логики в интуиционистской.

№ 17 (07.04.2020):

Примитивно-рекурсивная арифметика.

№ 18 (14.04.2020):

Интуиционистская арифметика.

Лекция № 13 (прочитана 23.04.2020); видео на MathNet

Аксиоматика теории множеств Цермело – Френкеля. Натуральные числа и упорядоченные пары по Куратовскому. Вполне упорядоченные множества.

Лекция № 14 (прочитана 27.04.2020); видео на MathNet

Теорема о сравнимости вполне упорядоченных множеств. Ординалы и их свойства.

Лекция № 15 (прочитана 30.04.2020); видео на MathNet

Теорема об изоморфности любого вполне упорядоченного множества ординалу. Трансфинитная индукция и трансфинитная рекурсия. Операции на ординалах. Аксиома выбора (AC), теорема Цермело (ZT), лемма Цорна (ZL). Вывод AC из ZT и ZT из ZL.

Лекция № 16 (прочитана 07.05.2020); видео на MathNet

Вывод ZL из AC. Мощности и кардиналы. Алефы. Обобщённая лемма Кантора (равномощность бесконечного множества его декартову квадрату). Арифметика кардиналов.

Конспекты и задачи

• Конспект лекций по теоремам Гёделя о неполноте (лекции №№ 2–7).
• Слайды лекций по интуиционистской логике первого порядка: № 8, № 9, № 10, № 11, № 12.
• Задачи 2016 г.
• Задачи по интуиционистской логике первого порядка (обновлено 22.04.2020)

План курса и литература

I. Арифметика Пеано, теорема Гёделя о неполноте

1. Примитивно-рекурсивные функции. Двойная рекурсия. Возвратная рекурсия. Функция Аккермана.
2. Арифметика Пеано (PA). Представление в PA: деления с остатком, простоты числа, взаимной простоты двух чисел, наибольшего общего кратного.
3. Σ₁ формулы. Теорема о Σ₁-полноте PA.
4. Китайская теорема об остатках. Бета-функция Гёделя. Лемма Гёделя о бета-функции.
5. Кодирование конечных последовательностей натуральных чисел в PA. Представимость в PA примитивно-рекурсивных функций, их доказуемая тотальность.
6. Гёделева нумерация. Представление синтаксиса PA внутри PA. Гёделев предикат доказуемости.
7. Условия Гильберта-Бернайса.
8. Теорема о неподвижной точке в PA. Вторая теорема Гёделя о неполноте. Теорема Лёба. Теорема Тарского, неразрешимость PA.

• G. Boolos. The logic of provability. Cambridge University Press, 1993. (введение, главы 2 и 3)
• W. Rautenberg. A concise introduction to mathematical logic. Springer, 2010. (главы 6 и 7)
• Конспект 2016 г., сс. 59–77.

II. Интуиционистская логика первого порядка

1. Интуционистская логика первого порядка (FO-Int). Семантика Крипке, теорема о корректности.
2. Каноническая модель. Лемма о насыщении, лемма об истинности формул в канонической модели.
3. Теорема о полноте FO-Int относительно семантики Крипке. Экзистенциальное свойство FO-Int. Перевод двойного отрицания FO-CL в FO-Int.
4. Принцип сдвига двойного отрицания. Отсутствие свойства конечных моделей у FO-Int. Принцип постоянства области (CD), его невыводимость в FO-Int.

• D. Gabbay, V. Shehtman, D. Skvortsov. Quantification in nonclassical logic, vol. 1. Draft of the 2nd edition, 2012.
• В. Е. Плиско, В. Х. Хаханян. Интуиционистская логика. — М.: Изд-во при мех.-мат. ф-те МГУ, 2009.
• Конспект лекций по курсу “Logic II” (Пенсильванский университет, весна 2017 г.), лекции 11–15: конспект; задачи.

III. Элементы теории множеств

1. Аксиоматическая теория множество Цермело – Френкеля (ZF). Линейные и полные порядки. Ординалы. Трансфинитная индукция. Теорема о линейности порядка на ординалах. Определения по трансфинитной рекурсии.
2. Аксиома выбора, лемма Цорна, теорема Цермело. Их эквивалентность.
3. Мощности. Теорема о сравнимости мощностей [ZFC]. Теорема о сюръекции [ZFC]. Кардиналы и алефы. Обобщённая лемма Кантора. Континуум-гипотеза.

• T. Jech. Set theory, The Third Millenium Edition. Springer, 2006. (§§ 1—5)
• K. Hrbacek, T. Jech. Introduction to set theory (3rd ed.). Marcel Dekker Inc., 1999. (§§ 1—9)
• Конспект 2016 г., сс. 3–25.

Если вы не имеете доступа к одной из книг, напишите лектору курса.