Дискретная математика. Множества

В данном курсе можно выделить три главные линии.
Во-первых, в курсе

В общем случае, множество A по схеме свертывания определяется как множество,

Применяя сокращение F(x) для обозначения того, что элемент x обладает свойством

Неограниченное применение схемы свертывания ведет к противоречиям. Например, можно получить «множество

Назовем множество правильным, если оно не является своим элементом, и неправильным

В соответствии с определением для любого множества A справедливо утверждение:
A∈R

Более подробно. Если R правильное, то есть не является своим элементом,

Для обозначения бинарного отношения R на множестве M, будем использовать как

Отношение порядка.

Пусть А– непустое множество.
Определение. Отношение Р ⊆ А

Пример. Пусть А= {a, b, c, d}.
Отношение Р= {(a, a),

Определение. Отношение Р ⊆ А называется частичным порядком, если оно рефлексивно,

Определение. Отношение < ⊆ А называется строгим порядком, если оно определяется

Определение. Пусть ≤ ⊆ А и х, у ∈ А. Элементы

Определение. Частичный порядок ≤ ⊆ А называется линейным порядком, если(∀ х,

Пример. Пара < Z, ≤>, где ≤– отношение делимости на множестве

Определение. Элемент а ∈ А частично упорядоченного множества < А, ≤

Наибольший(наименьший) элемент частично упорядоченного множества
< А, ≤ >(если он существует) обозначается

Теорема. Пусть < А, ≤ > является частично упорядоченным множеством, где

Пример. Частично упорядоченное множество < А, ≤ >, где
А= {a, b,

Пример3.22. Частично упорядоченное множество < B, ≤ >, где
B= {1, 2,

Замечание. Всякий наибольший элемент частично упорядоченного множества является максимальным, а всякий

Операции над отношениями

Так как отношения, заданные на фиксированной паре множеств  являются

Часто вместо объединения, пересечения и дополнения отношений говорят об их дизъюнкции,