Попков Роман Андреевич

Язык:

Существует всего один объект —

Отношение принадлежности:

ZF1

(Экстенсиональность) — множество определяется своими элементами:

Собственное подмножество:

ZF2

(Аксиома существования) — Не существует двух разных пустых множеств, т.к. по ZF1 они определяются элементами, которых в пустом множестве нет.

Обозначение:

ZF3

(Аксиома пары) — : неупорядоченная пара

Упорядоченная пара:

Упорядоченная тройка:

Упорядоченная -ка:

Теорема

Доказательство: упражнение

ZF4

(Аксиома объединения)

Вывод: всё что конечно, точно является множеством

ZF5

(Аксиома бесконечности)

ZF6

(Схема аксиомы выделения)

Пример: ,

Теорема (Парадокс Рассела)

"Не существует множества всех множеств"

Доказательство: Пусть существует множество всех множеств . По выделим в нём подмножество:

Тогда: — противоречие.

Теорема

— универсум класс

Определим операции:

ZF7

(Аксиома степени / булеан)

Упражнение:

ZF8

(Аксиома регулярности)

В частности:

ZFC

(Аксиома выбора)

Для любого множества , состоящего из непустых непересекающихся подмножеств, существует множество, содержащее ровно один элемент из каждого подмножества.

Декартово произведение множеств

Упражнение: Почему — множество?

Декартова степень:

Отношения

— отношение между и

— бинарное отношение на множестве

Диагональ:

Отображения (функции)

— отображение из в , если:

— область определения

— область значений/кообласть

Отображение определяется тройкой: , ,

Отображения и равны, если:

1. и

Пример:

Это разные отображения!

Множество всех отображений из в :

Обозначения чисел:

Образ и прообраз

Для :

Для :

Пример:

Типы отображений

Пусть — отображение.

1. Инъекция (Injection):
   Каждому образу соответствует ровно один прообраз (у всех разный )
2. Сюръекция (Surjection) (отображение на):
   Каждому образу соответствует не менее одного прообраза (все покрыты)
3. Биекция (Bijection):
   Взаимно однозначное соответствие (1 to 1 map)

Композиция отображений

Теорема (Ассоциативность композиций)

Если определены композиции и , то они равны.

Доказательство:

Следовательно, .

Замечание: В общем случае , т.е.

Пример:

• — отражение относительно оси
• — поворот на относительно начала координат

, где

Тождественное отображение

Обратные отображения

Пусть и .

• — левое обратное
• — правое обратное

Теорема

Если у отображения есть и левое обратное, и правое обратное, то они равны.

Доказательство:

Пусть — левое обратное:

Пусть — правое обратное:

Тогда:

Следовательно, .

Теорема

Пусть — отображение.

1. Если , то обратимо слева — инъекция
2. обратимо справа — сюръекция
3. обратимо — биекция

Отношение эквивалентности

— отношение эквивалентности , если выполнены:

1. Рефлексивность: для всех
2. Симметричность:
3. Транзитивность:

Класс эквивалентности

Для определим класс эквивалентности:

Теорема

1. Любое отношение эквивалентности разбивает множество на непересекающиеся классы эквивалентности
2. Любое разбиение множества порождает некоторое отношение эквивалентности

Фактор-множество

Фактор-множество — множество всех классов эквивалентности.

Трансверсаль

Трансверсаль — множество, содержащее ровно один элемент из каждого класса эквивалентности. Существует для любого отношения эквивалентности (по аксиоме выбора).