Программа курса математической логики

для студентов механико-математического факультета
(2-3-й семестры)

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

  1. Основные понятия теории множеств. Операции над множествами.
  2. Упорядоченные пары, декартово (прямое) произведение множеств.
  3. Отношения и функции над множествами, образы, прообразы и композиция.
  4. Отношения эквивалентности, предпорядка, порядка, линейного порядка и фактор-множества.
  5. Вполне упорядоченные множества, ординалы и кардиналы.
  6. Теоремы Кантора и Кантора-Бернштейна.

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

  1. Высказывания и их истинностная и теоретико-множественная семантика.
  2. Секвенциальное исчисление высказываний. Основные эквивалентности, нормальные формы.
  3. Гильбертовское исчисление высказываний. Теорема о дедукции.
  4. Теорема Гёделя о полноте и характеризация доказуемых формул.

Теория моделей

  1. Предикаты, сигнатуры, модели (алгебраические системы).
  2. Синтаксис языка исчисления предикатов (термы, формулы, свободные и связанные вхождения переменных).
  3. Семантика языка исчисления предикатов (истинность формул на модели и значение термов).
  4. Гомоморфизмы, изоморфизмы; подмодели, связь с универсальными и экзистенциальными формулами; позитивные формулы.
  5. Элементарные расширения и подсистемы; элементарные вложения; объединение элементарных цепей.
  6. Фильтрованные произведения и теорема Лося.
  7. Теорема компактности Мальцева.

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

  1. Исчисление (секвенциальная форма).
  2. Основные эквивалентности.
  3. Дизъюнктивная и конъюнктивная нормальные формы.
  4. Предваренная нормальная форма.
  5. Непротиворечивые множества формул.
  6. Теорема о существовании расширений Хенкина.
  7. Каноническая модель теории Хенкина.
  8. Теорема о существовании модели.
  9. Теорема Геделя о полноте классического исчисления предикатов.
  10. Исчисление предикатов гильбертовского типа; теорема о дедукции. Теоремы об эквивалентности двух исчислений.

Аксиоматические теории

  1. Аксиоматическая теория Пеано арифметики. Стандартные и нестандартные модели. Сигма-формулы и их свойства. Концевые расширения.
  2. Аксиоматика Цермело-Френкеля. Теории множеств; вполне упорядочные множества, ординалы и кардиналы.
  3. Эквивалентность аксиомы выбора, леммы Цорна и теоремы Цермело.
  4. Теорема о мощности декартова квадрата бесконечного множества.

Теория вычислимости и теорема Гёделя о неполноте

  1. Примитивно рекурсивные и частично рекурсивные функции. Теорема об элиминации примитивной рекурсии. Функция Гёделя.
  2. Сигма-представимость рекурсивных функций в арифметике Пеано.
  3. Гёделевская нумерация термов и формул конечной сигнатуры. Универсальная функция и рекурсивно неотделимые пары
  4. Перечислимость следствий рекурсивно-аксиоматизируемых теорий и теорем исчисления предикатов.
  5. Неразрешимость расширений аксиом Пеано.
  6. Теорема Гёделя о неполноте.
  7. Теорема Чёрча о неразрешимости исчисления предикатов

Семинары

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.

Программу составил:
член-корр. РАН
профессор
С.С.Гончаров