Тема 2. Множества

6. Множество, элемент, принадлежность, пустое, универсальное, конечное, бесконечное, обозначения, способы задания, равенство множеств.

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

8. Подмножество, включение, свойство транзитивности, собственное (несобственное) подмножество, число k-элементных и число всех подмножеств n-элементного множества.

9. Операции над множествами: объединение, пересечение, разность, дополнение, симметрическая разность, диаграммы Эйлера-Венна. Доказательство равенств множеств. Основные тождества с множествами (законы алгебры множеств — идемпотентности, коммутативности, ассоциативности, дистрибутивности, поглощения, де Моргана).

10. Кортеж (вектор), компонента, длина, пара, тройка, n-ка, равенство кортежей, кортеж над множеством, число кортежей длины k над n-элементным множеством, проекция кортежа.

11. Булевы векторы и представление ими подмножеств универсального множества. Сравнение булевых векторов и отношение включения между подмножествами. Операции над булевыми векторами и над представляемыми ими подмножествами.

12. Разбиение множества. Рекуррентная формула для числа разбиений конечного множества.

13. Декартово (прямое) произведение множеств, степень множества, число элементов произведения конечных множеств, проекция подмножества декартова произведения.

14. Мощность множества. Равномощные множества. Кардинальное число множества. Счётные множества и их свойства. Примеры несчётных множеств. Теорема Кантора-Бернштейна. Множества мощности континуум.

Тема 3. Отношения

15. Определение отношения, его арность. Связь отношений с предикатами. Бинарные отношения. Булева матрица и граф бинарного отношения.

16. Операции над отношениями. Теоретико-множественные операции. Обращение и умножение бинарных отношений. Возведение в степень и транзитивное замыкание бинарного отношения.

17. Операции над булевыми матрицами и представляемыми ими бинарными отношениями. Графическая интерпретация операций над отношениями.

18. Свойства операций над бинарными отношениями.

19. Важнейшие свойства бинарных отношения: рефлексивность, симметричность, транзитивность, антисимметричность. Простейшие тесты для них.

20. Отношение эквивалентности и разбиение на классы. Фактор-множество. Главная теорема математики.

21. Матрица и граф отношения эквивалентности.

22. Операции над эквивалентностями.

23. Отношение частичного порядка. Сравнение по порядку. Линейный порядок. Минимальный, максимальный, наименьший, наибольший элементы в частично упорядоченном множестве. Диаграмма Хассе. Интервал. Количество интервалов в декартовой степени множества {0, 1, …, k — 1}.

24. Решётки. Операции сложения и умножения в решётке и их свойства. Верхняя и нижняя полурешётки.

25. Отображения и их свойства: инъективность, сюръективность и биективность. Полное и частичное отображения. Функции как отображения. Область определения и область значений. Тождественное отображение. Обратная функция. Произведение отображений. Полный прообраз и ядерная эквивалентность. Подстановки и их количество на конечном множестве.