ПРОГРАММА КУРСА

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

2012–2013 учебный год

Лектор – член-корр. РАН, д.ф.-м.н. С.С. Гончаров

Обучение по основному курсу Математическая логика ведется в течение двух

семестров: во втором семестре первого курса и в первом семестре второго курса обучения студентов ММФ НГУ. В конце каждого семестра предусмотрены зачет и экзамен.

1-й семестр курса лекций Элементы теории множеств 1. Основные понятия теории множеств. Операции над множествами.

2. Упорядоченные пары, декартово (прямое) произведение множеств.

3. Отношения и функции над множествами, образы, прообразы и композиция, аксиома выбора и бесконечные прямые произведения множеств.

4. Отношения эквивалентности, предпорядка, порядка, линейного порядка и фактор-множества. Лемма Цорна (без доказательства).

5. Вполне упорядоченные множества, ординалы и кардиналы, трансфинитная индукция, натуральные числа и ординалы в теории множеств, аксиома существования бесконечного множества и построение множества натуральных чисел. Теорема о сравнимости ординалов. Теорема о сравнимости вполне упорядоченных множеств. Теорема Цермело (без доказательства).

6. Теоремы Кантора и Кантора–Бернштейна. Операции на кардиналах и ординалах. Теорема о мощности квадрата (из теоремы Цермело).

Исчисление высказываний 1. Высказывания и их истинностная и теоретико-множественная семантика и теорема о следовании в истинностной семантике из следования в теоретико-множественной.

2. Секвенциальное исчисление высказываний. Линейный и древовидный выводы и их эквивалентность. Теорема о построении вывода для квазивывода. Теорема о двузначности секвенциального исчисления высказываний. Основные эквивалентности, нормальные формы. Доказательство теоретико-множественного следования.

3. Гильбертовское исчисление высказываний. Теорема дедукции. Теорема о доказуемости из секвенциального следования в гильбертовском исчислении. Доказательство тождественной истинности в теоретико-множественной семантике формул, доказуемых в гильбертовском исчислении высказываний.

4. Теорема об эквивалентности исчислений и семантик. Теорема о существовании конъюнктивной и дизъюнктивной нормальных форм в секвенциальном исчислении высказываний.

5. Теорема о характеризации доказуемых формул в секвенциальном исчислении высказываний и теорема Гёделя о полноте.

Теория моделей 1. Предикаты, сигнатуры, модели (алгебраические системы).

2. Синтаксис языка исчисления предикатов (термы, формулы, свободные и связанные вхождения переменных).

3. Семантика языка исчисления предикатов (истинность формул на модели и значение термов).

4. Гомоморфизмы, изоморфизмы, подмодели. Связь теоретико-модельных свойств с универсальными, экзистенциальными и позитивными формулами.

5. Элементарные расширения и подсистемы. Элементарные вложения. Объединение элементарных цепей.

6. Фильтры, главные и неглавные, максимальные и ультрафильтры.

Фильтрованные произведения и теорема Лося.

7. Теорема компактности Мальцева. Метод диаграмм и теорема Мальцева о расширении.

2-й семестр курса лекций Исчисление предикатов 1. Предикатное исчисление в секвенциальной и гильбертовской формах.

2. Теорема о подстановке. Основные эквивалентности.

3. Теорема дедукции для гильбертовского исчисления. Теорема об эквивалентности секвенциального и гильбертовского исчислений.

4. Пренексная и предваренная нормальные формы. Теорема о приведении к нормальной форме.

5. Непротиворечивые множества формул и их свойства.

6. Теорема о существовании расширений Хенкина.

7. Каноническая модель теории Хенкина.

8. Теорема о существовании модели.

9. Теорема Гёделя о полноте классического исчисления предикатов.

Аксиоматическая теория множеств Цермело–Френкеля 1. Аксиоматика Цермело–Френкеля ZF.

2. Теорема об эквивалентности аксиомы выбора, леммы Цорна, теоремы Цермело и теоремы о мощности квадрата.

Аксиоматическая теория Пеано 1. Аксиоматика Пеано и ее свойства.

2. Стандартные и нестандартные модели арифметики Пеано.

3. Концевые расширения. Формулы с ограниченными кванторами и -формулы.

Теория вычислимости и теорема Гёделя о неполноте 1. Примитивно рекурсивные и частично рекурсивные и вычислимые функции. Операторы суммирования, произведения, ограниченной минимизации. Составное определение. Теорема о -представимости в стандартной модели арифметики.

2. Теорема о представимости в аксиоматике Пеано.

3. Гёделевская нумерация термов и формул и ее свойства.

4. Примитивная рекурсивность и возвратная рекурсия. Операторы суммирования, произведения, ограниченной минимизации. Примитивная рекурсивность основных операций и отношений над термами и формулами: множества формул, множества термов, операции подстановки, множества аксиом гильбертовского исчисления предикатов, правил вывода, доказательств.

5. Вычислимо перечислимые множества и их свойства. Перечислимость вычислимо аксиоматизируемых теорий и вычислимая аксиоматизируемость вычислимо перечислимо аксиоматизируемых теорий. Теорема об универсальной функции и нормальной форме Клини. Вычислимая перечислимость доказуемых формул.

6. Теорема о неразрешимости непротиворечивых расширений аксиоматики Пеано.

7. Теорема Гёделя о неполноте. Теорема Чёрча о неразрешимости исчисления предикатов.

План семинарских занятий 1-й семестр семинаров 1. Теоретико-множественные отношения на множествах.

2. Частично упорядоченные множества и отношения эквивалентности.

3–4. Вполне упорядоченные множества, ординалы и мощности множеств.

5. Теоретико-множественная семантика высказываний и таблица истинности.

6. Исчисление высказываний секвенциальное. Нормальная форма.

7–8. Исчисление высказываний гильбертовского типа. Независимость аксиом.

9. Контрольная работа.

10. Модели, гомоморфизмы, подмодели, произведения моделей.

11. Язык исчисления предикатов и его семантика.

12. Формульные множества и аксиоматизируемые классы. Элементарные подмодели.

13. Квазитождества и тождества. Свободные системы, конгруэнтности и фактор-системы.

14. Теорема компактности Мальцева и ее применения.

15. Арифметика Пеано и ее модели.

16. Контрольная работа.

2-й семестр семинаров 1. Гильбертовское исчисление предикатов.

2. Истинность доказуемых формул.

3–4. Секвенциальное исчисление предикатов.

5. Приведение к пренексной и приведенной нормальной форме.

6. Устойчивость -формул относительно подмоделей, -формул относительно расширений и позитивных формул относительно гомоморфизмов. Аксоматика Пеано и типы индукции в арифметике.

7. Аксиоматическая теория множеств. Ординалы и их свойства.

8. Контрольная работа.

9–10. Примитивно рекурсивные и частично рекурсивные функции.

11–12. Арифметика Пеано ее модели и -формулы. Представимость рекурсивных функций в стандартной модели и теории арифметики Пеано.

13. Гёделевская нумерация термов и формул.

14–15. Неразрешимые проблемы. Теорема о неполноте расширений арифметики. Теоремы о разрешимости и неразрешимости теорий.

16. Контрольная работа.

1. Ершов Ю. Л., Палютин Е. А. Математическая логика. М.: Наука, 1979.

2. Мендельсон Э. Введение в математическую логику. М.: Наука, 1971.

3. Ершов Ю. Л. Определимость и разрешимость. Новосибирск: НИИ МИОО НГУ, Научная книга, 1996.

4. Максимова Л. Л., Лавров И. А. Задачи по теории множеств, математической логики и теории алгоритмов. М.: Физматлит, 2001.

1. Справочная книга по математической логике / Под ред. Дж. Барвайса. М.: Наука, 1982. Т. 1–4.

2. Кейслер Г., Чен Ч. Ч. Теория моделей. М.: Мир, 1977.

3. Гончаров С. С., Ершов Ю. Л. Конструктивные модели. Новосибирск: Научная книга, 1999.

4. Гончаров С. С. Счетные булевы алгебры и разрешимость. Новосибирск: Научная книга, 1996.

5. Роджерс Х. Теория рекурсивных функций и вычислимость. М.:

Мир, 1972.

6. Соар Р. Вычислимо перечислимые множества и степени. Казань:

Казанское мат. общ-во, 2000.

7. Ершов Ю. Л. Проблемы разрешимости и конструктивные модели.

М.: Наука, 1980.

8. Куратовский К., Мостовский А. Теория множеств. М.: Мир, 1970.

9. Мальцев А. И. Алгоритмы и рекурсивные функции. М.: Наука, 1986.

10. Шёнфилд Дж. Математическая логика. М.: Наука, 1975.

11. Робинсон А. Введение в теорию моделей и метаматематику алгебры. М.: Наука, 1967.

12. Чёрч А. Введение в математическую логику. М.: Изд-во иностр.

лит., 1960.

13. Новиков П. С. Элементы математической логики. М.: Наука, 1973.

14. Клини С. Математическая логика. М.: Мир, 1973.

15. Клини С. Введение в метаматематику. М.: Изд-во иностр. лит., 1957.

16. Булос Дж., Джеффри Р. Вычислимость и логика. М.: Мир, 1994.

17. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М.: Мир, 1983.

18. Handbook of Recursive mathematics, Studies in logic and the foundation of mathematics. Edited by Yu. Ershov, S. Goncharov, A. Nerode, J. Remmel, ass. editor V. Marek, Elsevier. Amsterdam; Lausanne; N. Y.;

Oxford; Shanon; Singapore; Tokyo, 1998. V. 1–2.