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

Список всех тем лекций

Лекция 1. Примитивно-рекурсивные функции.
Примитивно-рекурсивные функции Кодирование последовательностей Совместная рекурсия Возвратная рекурсия Функция Аккермана

Лекция 2. Арифметика Пеано.
Арифметика Пеано Определение функции, доказуемо-тотальные функции Теорема Гёделя Теорема: всякая примитивно-рекурсивная функция доказуемо-тотальна в арифметике Пеано Доказуемо-тотальность функции взятия остатка в арифметике Пеано и определение взаимной простоты двух чисел Если p - простое и делит произведение, то делит один из множителей

Лекция 3. Китайская теорема об остатках.
Определение наименьшего общего кратного чисел + упражнения Китайская теорема об остатках и её доказательство β-функция Гёделя Кодирование пар Ограниченные кванторы замкнут относительно ∧, ∨, ∃, ∀x

Лекция 4. Кодирование примитивно-рекурсивных функций в PA.
- полна Кодирование примитивно-рекурсивных функций в арифметике Пеано: доказательство существования и единственности

Лекция 5. Гёделева нумерация.
Гёделева нумерация Определение термы и формулы Предикат доказательства Условия доказуемости Подстановки и параметры

Лекция 6. Параметрическая Δo-полнота.
Доказуемая Σ1-полнота и параметрическая Δo-полнота Теорема о неподвижной точке План следующей лекции

Лекция 7. Гёделева теория.
Гёделева теория Предикат доказательства Предикат доказуемости Теорема о неподвижной точке Первая теорема Гёделя о неполноте Лемма о непротиворечивости Вторая теорема Гёделя о неполноте Доказательство леммы о непротиворечивости Теорема Гёделя–Россера Задачи Теорема Лёба Теорема Тарского Теорема: Арифметика Пеано (PA) алгоритмически неразрешима План следующей лекции

Лекция 8. Теория множеств. Часть 1.
Основные понятия Парадокс Рассела Аксиоматическая теория множеств Цермело-Френкеля Аксиома индукции Функции и классы Декартово произведение Принцип рекурсии Анонс следующей лекции

Лекция 9. Теория множеств. Часть 2.
Аксиоматика теории множеств (краткий обзор предыдущей лекции) Порядок натуральных чисел Арифметика Пеано Теорема Гёделя о неполноте Вполне упорядоченное множество Теорема о сравнении

Лекция 10. Ординалы.
Вполне упорядоченное множество Теорема о сравнимости Аксиома регулярности Виды ординалов Теорема рекурсии Анонс следующей лекции

Лекция 11. Мощности множеств. Часть 1.
Равномощные множества Теорема Цермело Аксиома выбора Лемма Цорна Теорема о равносильности утверждений (теоремы Цермело, аксиомы выбора и леммы Цорна)

Лекция 12. Мощности множеств. Часть 2.
Кардинал множества Теорема Кантора Задачи (аксиома выбора) Теорема Кантора Иерархия ординалов Операции на кардиналах Литература по теме Кратко о пройденном в курсе "Математическая логика"