Кузнецов Степан Львович
«Математическая логика 2»
Описание курса:
Цель курса – познакомить начинающих студентов-логиков, а также других желающих, с основами математической логики, в большем объёме и с большими деталями, чем основной семестровый курс "Введение в математическую логику и теорию алгоритмов".
Курс представляет собой вторую часть годового курса (первую часть осенью 2019 г. читала Т.Л. Яворская); в то же время, изложение будет независимым от первого семестра. Курс состоит из трёх основных разделов.
Раздел I посвящён формальной арифметике и теореме Гёделя о неполноте. Это самый объёмный раздел курса. Планируется дать полное детальное доказательство 2-й теоремы о неполноте. В частности, планируется изложить доказательства условий на предикат доказуемости (условий Гильберта – Бернайса), которые обычно оставляют без доказательства. В изложении планируется следовать книге Г. Булоса “The logic of provability”.
Раздел II посвящён интуиционистской логике первого порядка, его целью является доказательство теоремы о полноте этой логики относительно семантики Крипке. Материал этого раздела даёт углублённый взгляд на материал, прочитанный в осеннем семестре. А именно, полнота интуиционистской логики первого порядка получается в некотором смысле совмещением двух идей: (а) полноты по Крипке интуиционистской логики высказываний и (б) теоремы Гёделя о полноте классической логики предикатов. Изложение планируется вести, опираясь на книгу Д. Габбая, Д. Скворцова и В. Шехтмана “Quantification in nonclassical logic”.
Раздел III содержит основы теории множеств, необходимый элемент в арсенале начинающего логика. Планируется изложить аксиоматическую теорию множеств ZF, методы трансфинитной индукции и рекурсии, аксиому выбора и её эквиваленты (лемма Цорна, теорема Цермело). Ориентир здесь – начальные главы книги Т. Йеха “Set theory”.
План курса:
Раздел I. Арифметика Пеано, теорема Гёделя о неполноте
1. Примитивно-рекурсивные функции. Двойная рекурсия. Возвратная рекурсия. Функция Аккермана.
2. Арифметика Пеано (PA). Представление в PA: деления с остатком, простоты числа, взаимной простоты двух чисел, наибольшего общего кратного.
3. Сигма-1 формулы. Теорема о сигма-1 полноте PA.
4. Китайская теорема об остатках. Бета-функция Гёделя. Лемма Гёделя о бета-функции.
5. Кодирование конечных последовательностей натуральных чисел в PA. Представимость в PA примитивно-рекурсивных функций, их доказуемая тотальность.
6. Гёделева нумерация. Представление синтаксиса PA внутри PA. Гёделев предикат доказуемости.
7. Условия Гильберта-Бернайса.
8. Теорема о неподвижной точке в PA. Вторая теорема Гёделя о неполноте. Теорема Лёба. Теорема Тарского, неразрешимость PA.
Раздел II. Интуиционистская логика первого порядка
1. Интуционистская логика первого порядка (FO-Int). Семантика Крипке, теорема о корректности.
2. Каноническая модель. Лемма о насыщении, лемма об истинности формул в канонической модели.
3. Теорема о полноте FO-Int относительно семантики Крипке. Экзистенциальное свойство FO-Int. Перевод двойного отрицания FO-CL в FO-Int.
4. Принцип сдвига двойного отрицания. Отсутствие свойства конечных моделей у FO-Int. Принцип постоянства области (CD), его невыводимость в FO-Int.
Раздел III. Элементы теории множеств
1. Аксиоматическая теория множество Цермело – Френкеля (ZF). Линейные и полные порядки. Ординалы. Трансфинитная индукция. Теорема о линейности порядка на ординалах. Определения по трансфинитной рекурсии.
2. Аксиома выбора, лемма Цорна, теорема Цермело. Их эквивалентность.
3. Мощности. Теорема о сравнимости мощностей [ZFC]. Теорема о сюръекции [ZFC]. Кардиналы и алефы. Обобщённая лемма Кантора. Континуум-гипотеза.
