Программа курса математической логики
для студентов механико-математического факультета
(2-3-й семестры)
Элементы теории множеств
- Основные понятия теории множеств. Операции над множествами.
- Упорядоченные пары, декартово (прямое) произведение множеств.
- Отношения и функции над множествами, образы, прообразы и композиция.
- Отношения эквивалентности, предпорядка, порядка, линейного
порядка и фактор-множества.
- Вполне упорядоченные множества, ординалы и кардиналы.
- Теоремы Кантора и Кантора-Бернштейна.
Исчисление высказываний
- Высказывания и их истинностная и теоретико-множественная
семантика.
- Секвенциальное исчисление высказываний.
Основные эквивалентности, нормальные формы.
- Гильбертовское исчисление высказываний.
Теорема о дедукции.
- Теорема Гёделя о полноте и характеризация доказуемых
формул.
Теория моделей
- Предикаты, сигнатуры, модели (алгебраические системы).
- Синтаксис языка исчисления предикатов (термы, формулы,
свободные и связанные вхождения переменных).
- Семантика языка исчисления предикатов (истинность формул
на модели и значение термов).
- Гомоморфизмы, изоморфизмы; подмодели, связь с
универсальными и экзистенциальными формулами; позитивные формулы.
- Элементарные расширения и подсистемы; элементарные
вложения; объединение элементарных цепей.
- Фильтрованные произведения и теорема Лося.
- Теорема компактности Мальцева.
Исчисление предикатов
- Исчисление (секвенциальная форма).
- Основные эквивалентности.
- Дизъюнктивная и конъюнктивная нормальные формы.
- Предваренная нормальная форма.
- Непротиворечивые множества формул.
- Теорема о существовании расширений Хенкина.
- Каноническая модель теории Хенкина.
- Теорема о существовании модели.
- Теорема Геделя о полноте классического исчисления предикатов.
- Исчисление предикатов гильбертовского типа; теорема о
дедукции. Теоремы об эквивалентности двух исчислений.
Аксиоматические теории
- Аксиоматическая теория Пеано арифметики. Стандартные и
нестандартные модели. Сигма-формулы и их свойства. Концевые
расширения.
- Аксиоматика Цермело-Френкеля. Теории множеств; вполне
упорядочные множества, ординалы и кардиналы.
- Эквивалентность аксиомы выбора, леммы Цорна и теоремы
Цермело.
- Теорема о мощности декартова квадрата бесконечного множества.
Теория вычислимости и теорема Гёделя о неполноте
- Примитивно рекурсивные и частично рекурсивные функции.
Теорема об элиминации примитивной рекурсии. Функция Гёделя.
- Сигма-представимость рекурсивных функций в арифметике Пеано.
- Гёделевская нумерация термов и формул конечной сигнатуры.
Универсальная функция и рекурсивно неотделимые пары
- Перечислимость следствий рекурсивно-аксиоматизируемых
теорий и теорем исчисления предикатов.
- Неразрешимость расширений аксиом Пеано.
- Теорема Гёделя о неполноте.
- Теорема Чёрча о неразрешимости исчисления предикатов
Семинары
II семестр
1.Теоретико-множественные отношения на множествах.
2.Частично-упорядоченные множества и отношения
эквивалентности.
3.Мощности множеств.
4.Теоретико-множественная семантика высказываний и таблица
истинности.
5-6.Исчисление высказываний секвенциальное. Нормальная
форма.
7--8.Исчисление высказываний гильбертовского типа.
Независимость аксиом.
9.Контрольная работа.
10.Модели, гомоморфизмы, подмодели, произведения моделей.
11.Язык исчисления предикатов и его семантика.
12.Формульные множества и аксиоматизируемые классы.
Элементарные подмодели.
13.Квазитождества и тождества. Свободные системы,
конгруэнтности и фактор-системы.
14.Теорема компактности Мальцева и ее применения.
15.Арифметика Пеано и ее модели.
16.Контрольная работа.
III семестр
1-3.Исчисление предикатов секвенциальное.
4-5.Гильбертовское исчисление предикатов.
6.Истинность доказуемых формул.
7.Устойчивость универсальных формул относительно подмоделей,
экзистенциональных формул относительно расширений и позитивных формул
относительно гомоморфизмов.
8.Аксиоматическая теория множеств.
9.Ординалы и их свойства.
10.Контрольная работа.
11-12. Примитивно-рекурсивные и частично рекурсивные функции.
13.Арифметика Пеано, ее модели и сигма-формулы. Представимость
рекурсивных функций в арифметике Пеано.
14.Гёделевская нумерация термов и формул.
15.Неразрешимые проблемы. Теоремы неполноты расширений
арифметики.
16.Контрольная работа
Литература
1.Ю.Л.Ершов, Е.А.Палютин. Математическая логика, М.:
Наука, 1979.
2.Э.Мендельсон. Введение в математическую логику,
М.: Наука, 1971.
3.Ю.Л.Ершов. Определимость и вычислимость, НИИ МИОО НГУ,
Научная книга,1996
4.П.С.Новиков. Элементы математической логики, М.: Наука,
1973.
5.С.Клини. Математическая логика, М.:Мир, 1973.
6.С.Клини. Введение в метаматематику, ИЛ, 1957.
Программу составил:
член-корр. РАН
профессор
С.С.Гончаров