Программа курса ``Введение в математическую логику'', 20.12.00

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

Равномощность множеств. Свойства счетных множеств.

Сравнение мощностей. Теорема Кантора --- Бернштейна

Теорема Кантора |P(A)|>|A|.

Частично упорядоченные множества, линейно упорядоченные множества
вполне упорядоченные множества, начальные отрезки и их свойства.

Трансфинитная индукция и трансфинитная рекурсия.

Теорема о сравнении вполне упорядоченных множеств

Аксиома выбора. Теорема Цермело.

Лемма Цорна.

Равенства  |A|+|A|=|A| x |A|=|A|
для бесконечных множеств A.

Пропозициональная логика.

Пропозициональные формулы.

Таблица истинности формулы. Возможность представления
любой булевой функции некоторой  формулой. Дизъюнктивные и
конъюнктивные нормальные формы.
Эквивалентные формулы, выполнимые формулы и тавтологии.

Исчисление высказываний (ИВ) (аксиомы, правила вывода, понятие
выводимой формулы из данного множества формул)

Вывод формулы A --> A

Лемма о дедукции для ИВ

Выводы в ИВ

Лемма о таблице истинности.

Теорема о полноте ИВ

Логика первого порядка

Определение формулы данной сигнатуры

Интерпретации данной сигнатуры

Понятие истинности формулы в данной интерпретации.

Выразимые в данной интерпретации предикаты.

Доказательства невыразимости с помощью автоморфизмов.

Элиминация кванторов в интерпретации <Z,S,=> (или в интерпретации
<Z,0,S,=>. Невыразимость отношения ``быть меньше'' в этой
интерпретации.

Исчисление предикатов (ИП):
аксиомы, правила вывода. Допустимость применения правила обобщения.

Теорема о корректности исчисления предикатов.
Теорема Геделя о полноте (без доказательства).

Примеры выводов в исчислении предикатов:
вывод формул
\exists y\forall x \phi --> \forall x\exists y \phi,
\forall x A(x) --> \forall y A(y),
\exists x A(x) --> \exists y A(y) (где A ---
одноместный предикатный символ),
\lnot\forall x \phi <--> \exists x \lnot\phi,
\lnot\exists x \phi <--> \forall x \lnot\phi.

Теорема о том, что замена любой подформулы на доказуемо
эквивалентную формулу даёт доказуемо эквивалентную формулу.

Аксиомы равенства.

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

Теорема Геделя о полноте для исчисления предикатов с равенством
(без доказательства).

Выводимость из посылок для исчисления предикатов.
Свойства этого понятия.

Понятие теории, модели теории, непротиворечивости и
совместности теорий. Теорема Гёделя о полноте в сильной форме (без
доказательства).

Литература

Н. Верещагин, А. Шень. Математическая логика и теория алгоритмов.
Начала теории множеств.
Москва: изд-во МЦНМО, 1999.

Н. Верещагин, А. Шень. Математическая логика и теория алгоритмов.
Исчисления и языки.
Москва: изд-во МЦНМО, 2000.

Краткие (40 стр.) конспекты лекций в postscript формате и
в формате для печати на принтерах Laser Jet фирмы Нewlett Packard
с разрешением 600dpi доступны по Интернет в
http://lpcs.math.msu.ru/~ver