Глава 1. Элементы теории множеств.
1. Множество. Примеры. Обозначения. Семейство. Универсум и пустое множество. Способы задания множеств: перечисление, описательный (предикатный), конструктивный (по процедуре).
Парадокс Рассела и его разрешение (ограничение на вид предиката, типизация множеств, аксиома регулярности).
2. Подмножество и свойства операции включения. Равенство множеств. Собственное подмножество. Булеан (определение и обозначение, пояснение обозначения для конечного случая). Теорема о булеане (с доказательством).
3. Операции над множествами: пересечение, объединение, дополнение, разность, симметрическая разность. Иллюстрация на диаграммах Эйлера-Венна. Покрытия и Разбиения. Примеры. Свойства операций над множествами* и их доказательство (два способа). Доказать любым способом пару свойств. Утверждение про подмножества.
4. Представление двоичным кодом. Реализация операций для этого случая. Генерация всех подмножеств универсума. Алгоритм* представления бинарного кода Грея.
5. Представление множеств упорядоченными списками (два поля). Упорядочение по полю информации. Алгоритмы*: проверка включения слиянием, вычисление объединения слиянием, процедура добавления в конец списка, вычисление пересечения слиянием. Проиллюстрировать работу одного из алгоритмов.
6. Представление множеств итераторами (процедурами, которые перебирают элемента и делают с ними то, что нужно). Итератор пересечения, итератор разности, объединения на основе итератора принадлежности*.
7. Упорядоченные пары/наборы, их равенство. Декартово произведение, декартова степень. Примеры. Теорема о количестве элементов в декартовом произведении конечных множеств.
8. Бинарное отношение (2-местный предикат) – тройка <R, A, B>, где R – подмножество AxB. Область отправления (определения), область прибытия (значения). Местность отношения, унарные и n-местные отношения. Примеры.
9. Два графических способа представления отношений и матричный способ. Обратное, Дополняющее, Тождественное и Универсальное отношения и их матрицы. Композиция отношений (степень), ее св-ва (3 штуки). Ядро отношения. Примеры.
10. Свойства отношений. Теорема (критерий) о свойствах (с д-вом). Примеры.
11. Замыкания отношений. Алгоритм* Уоршалла.
12. Классификация отношений: функциональность (префиксная форма записи, аргумент, значение), тотальность (частичность, определение области определения и обдасти значения, сужение и продолжение функции), инъективность, сюрьективность (примеры, сводная таблица).
13. Биекция. Теорема о биекции. Суперпозиция функций, ее св-ва. Алгебраическая операция. Последовательность.
14. Отношения эквивалентности. Определение и классы эквивалентности. Три леммы о классах эквивалентности (непустота, совпадение и непересечение) и теорема о разбиении. Фактормножества..
15. Конструктивный способ задания натуральных чисел. Аксиоматический* (Дедекинда-Пеано) способ задания. Аксиома математической индукции, ее использование для определений.
16. Принцип мат. индукции. Применение принципа мат. индукции. Примеры.
17. Определение мощности через биекцию и классы эквивалентности. Примеры. Конечные и бесконечные множества (по содержанию собственного равномощного подмножества). Теорема о множестве, имеющем бесконечное подмножество, следствие из нее.
18. Добавление и удаление элементов. Теорема о равномощности конечных множеств отрезку натурального ряда. Теорема о конечности отрезка натурального ряда. Следствие о неравномощности различных отрезков натурального ряда. Кардинал (количество эл-тов, счетность, континуум).
19. Теорема Кантора-Бернштейна о равномощности (только схема доказательства). Следствие о трех альтернативах. Операции на кардинальных числах. Равномощность множеств натуральных и рациональных чисел.
20. Неравномощность множеств натуральных и действительных чисел (теорема Кантора о булеане с доказательством). Теорема о континуальности множества вещественных чисел (схема доказательства).
21. Отношение порядка. Строгий и нестрогий, полный и частичный порядок, обозначения. Примеры. Частичная и линейная упорядоченность. Отношение Парето на декартовом произведении.
22. Минимальные/максимальные, наибольшие/наименьшие элементы. Теорема о существовании минимального элемента. Дополнение частичного порядка до линейного.
23. Верхние и нижние границы, inf и sup. Лексикографический порядок. Теорема о лексикографическом порядке. Диаграммы Хассе. Монотонные функции. Полный порядок. Вполне упорядоченное множество. Примеры, изоморфность в.у.м.
24. Система аксиом Цермело-Френкеля*. Пример определения операций на ее основе. ZFC. Аксиома выбора.