Пустое отношение

Операции на отношениях:

Пересечение

Объединение

Произведение

Дополнение:

Обратное отношение к R:

Свойства отношений:

Рефлексивность: xRx, для всех x

Симметричность: xRy => yRx

Транзитивность: xRy, yRz => xRz

Антисимметричность: xRy, yRx => x=y

Бинарное отношение называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Отношение эквивалентности разбивает на семейство подмножеств (классов разбиения). Каждый его элемент принадлежит некоторому из этих подмножеств (именно – R(a)). Совокупность всех классов разбиения обозначается A/R и называется фактор-множеством множества A относительно эквивалентности R.

[a], обозначает класс из A/R к которому принадлежит a. Сам элемент a называют представителем этого класса.

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

Частичным порядком (или просто порядком) называется отношение, которое рефлексивно, антисимметрично и транзитивно.

Порядок обозначается символом .

так же является порядком и обозначается .

Порядок называется линейным, если для любых либо a либо b .

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

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

Каждое подмножество A’ множества частично упорядоченного множества обладает индуцированным порядком. Если порядок A’ линеен, то множество A’ называется цепью в A.

Максимальный, минимальный, наибольший, наименьший элемент.

Нижняя грань ( , точная нижняя грань , верхняя грань , точная верхняя грань .

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