Математическая логика I

Краткое описание курса

Курс служит введением в математическую логику. Освещаются основы теории вычислимости, теории формальных систем, теоремы об элиминации кванторов, основы теории моделей.

Содержание курса

1. Пропозициональная логика. ДНФ, КНФ. Базисы. Полные базисы, условия полноты. Вычислимые функции. Разрешимые и перечислимые множества. Их свойства.
2. Универсальные функции. Существование универсальной функции и несуществование всюду определённой универсальной. Теорема Успенского--Райса. Конструкция не-главной вычислимой универсальной функции.
3. Теорема Клини о неподвижной точке. Следствие (д-во т. Успенского--Райса). Машины Тьюринга. Busy beaver.
4. Исчисление высказываний. Лемма о дедукции. Корректность и полнота исчисления высказываний. Теорема о компактности. Исчисление секвенций.
5. Язык логики первого порядка. Термы, атомарные формулы, формулы. Интерпретации. Свободные и связанные вхождения переменных. Оценки и значения формул. Исчисление предикатов. Подстановки. Корректные подстановки.
6. Корректность исчисления высказываний. Лемма о дедукции. Лемма о константах. Противоречивость, выполнимость, модель. Теорема о полноте исчисления высказываний. Теорема о компактности.
7. Арифметическая иерархия. Классы $\Sigma_n$ и $\Pi_n$. Теорема Эрбрана. Сколемизация. Выразимые предикаты и выразимые множества. Арифметические предикаты. Автоморфизмы и их связь с выразимостью. Примеры выразимых и невыразимых предикатов.
8. Элиминация кванторов. Леммы для синтаксической элиминации кванторов. Элиминация кванторов в следующих теориях: теория с сигнатурой (=,s,0) в модели Z, теория линейных порядков (плотных, дискретных, с максимальными и/или минимальными элементами), арифметика Пресбургера, теория безатомных булевых алгебр, теория алгебраически замкнутых полей.
9. Элиминация кванторов в теории целозамкнутых полей (полей, элементарно эквивалентных R). Теорема Тарского.
10. Основные определения теории моделей. L-структуры, подструктуры и расширения. Теории и модели. Логические следствия. Выразимые множества. Примеры теорий и выразимых множеств. Выводимость и теорема о полноте. Теорема о компактности. Следствия: невыразимость множества точек кручения, нестандартная модель натуральных чисел.

Основная литература

1. Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. В 3-х тт. М., МЦНМО, 2008.
2. D. Marker. Model Theory: An Introduction. Springer-Verlag New York, 2002.
3. H.-D. Ebbinghaus, J. Flum, W. Thomas. Mathematical Logic. Springer-Verlag New York, 1984.