МАТЕМАТИЧЕСКАЯ ЛОГИКА

Лектор: член-корр. РАН , профессор С.С.Гончаров
(Есть экз. билеты и текст лекций в формате pdf, 610 Kb)

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. Теорема Чёрча о неразрешимости исчисления предикатов

Семинары

2 семестр

1. Теоретико-множественные отношения на множествах.
2. Частично-упорядоченные множества и отношения эквивалентности.
3. Мощности множеств.
4. Теоретико-множественная семантика высказываний и таблица истинности.
5 - 6. Исчисление высказываний секвенциальное. Нормальная форма.
7 - 8. Исчисление высказываний гильбертовского типа. Независимость аксиом.
9. Контрольная работа .
10. Модели, гомоморфизмы, подмодели, произведения моделей.
11. Язык исчисления предикатов и его семантика.
12. Формульные множества и аксиоматизируемые классы. Элементарные подмодели.
13. Квазитождества и тождества. Свободные системы, конгруэции и фактор-системы.
14. Теорема компактности Мальцева и ее применения.
15. Арифметика Пеано и ее модели.
16. Контрольная работа.

3 семестр

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.