1 курс. Логика и алгоритмы

Лектор проф.Л.Д.Беклемишев, преподаватель проф. В.Б.Шехтман

 Содержание лекций

Лекция 1.

1. Основные понятия и обозначения: множество, принадлежность, включение, равенство множеств, булевы операции.
2. Множество-степень ℘(X). Тождества булевой алгебры для ℘(X). Диаграммы Эйлера-Венна.
3. Бесконечные объединения и пересечения. Примеры: 1) Открытые подмножества R и R². Объединение открытых множеств открыто. 2) Канторовское множество. Его замкнутость и нигде не плотность.
4. Упорядоченные пары, равенство упорядоченных пар. Декартово произведение множеств A×B.
5. Бинарные отношения как подмножества A×B. Булевы операции над отношениями. Композиция отношений. Обратное отношение.
6. Функции. Инъективность, сюръективность, биективность. Обратная функция.

Лекция 2.

1. Отношения эквивалентности. Соответствие между разбиениями множества и отношениями эквивалентности на нём. Фактормножество.
2. Равномощность множеств (обозначение A∼B).
3. Множество X^Y всех функций f : X→ Y. Биекция между ℘(X) и 2^X.
4. Счётные множества. Подмножество счётного множества конечно или счётно. Всякое бесконечное множество имеет счётное подмножество. Объединение счётного множества счётных множеств счётно.
5. Счётность N×N, N^k и N* (множества всех конечных последовательностей натуральных чисел).
6. Объединение бесконечного множества X и счётного множества равномощно X. Равномощность R и 2^N.

Лекция 3.

1. Сравнение мощностей множеств. Теорема Кантора-Бернштейна.
2. Счётность множества (вещественных) алгебраических чисел.
3. Несчётность R, множество ℘(X) не равномощно X. Примеры других континуальных множеств: иррациональные числа, N^N. Примеры множеств, превосходящие континуум по мощности.
4. Континуальность канторовского множества.
5. Континуум-гипотеза (формулировка и история вопроса).
6. Парадоксы наивной теории множеств (парадокс Кантора, парадокс Рассела).

Лекция 4.

1. Частично упорядоченные множества. Терминология: строгий и нестрогий порядок, линейный порядок, максимальный элемент, наибольший элемент, верхняя грань множества, цепь в частично упорядоченном множестве. Диаграммы конечных множеств.
2. Операции суммы и произведения линейно упорядоченных множеств. Обратный порядок. Примеры: ω+ω, ω⋅ω. Вложение и изоморфизм линейно упорядоченных множеств.
3. Вполне упорядоченные множества. Начальные отрезки. Вполне упорядоченное множество не изоморфно никакому своему начальному отрезку. Из любых двух вполне упорядоченных множеств одно изоморфно начальному отрезку другого.
4. Аксиома выбора. Теорема Цермело (всякое множество может быть вполне упорядочено). Лемма Цорна (формулировки). Следствие о том, что любые два множества сравнимы по мощности.

Лекция 5.

1. Вывод леммы Цорна из аксиомы выбора.
2. Вывод теоремы Цермело из леммы Цорна.
3. Вывод аксиомы выбора из теоремы Цермело.
4. Логика высказываний, понятие формулы.
5. Таблицы истинности, булевы функции.

  Записки лекций 4, 5

Конспект лекций Л.Д. Беклемишева по курсу "Введение в математическую логику" на мех-мате МГУ.

Рекомендуемая литература

Критерии оценки за листки

Листок 1     Листок 2   Листок 3  Листок 4  Листок 7  Листок 8   Листок 9  Листок 10

Программа коллоквиума 28.11.2011

Ведомости сдачи листков и итоговые оценки

Ведомость 1, группа 1  Ведомость 1, группа 2  Ведомость 2, группа 1   Ведомость 2, группа 2

Итог группа 1    Итог группа 2