Свойства бинарных отношений, специальные бинарные отношения.

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

Если отношение таково, что из включения обязательно следует, что , то отношение называется симметричным.

Если отношение таково, что из включений и следует, что , то отношение называется транзитивным.

Если отношение таково, что из одновременных включений и следует, что , то отношение называется антисимметричным.

Полагают по определению, что пустое множество является отношением одновременно рефлексивным, симметричным, антисимметричным и транзитивным.

Если отношение рефлексивно, транзитивно и симметрично, то оно называется эквивалентностью. Если же отношение одновременно рефлексивно, транзитивно и антисимметрично, то оно называется частичным порядком.

Если – частичный порядок на множестве A и , то говорят, что элементы сравнимы относительно или просто сравнимы; иногда пишут в этом случае или просто .

Определение. Отношение r на множестве Х называется рефлексивным, если для любого элемента хОХ выполняется хr х.

Определение. Отношение r на множестве Х называется симметричным, если для любых х, уОХ из хr у следует уr х.

Определение. Отношение r на множестве Х называется транзитивным, если для любых х, у, zОХ из хr у и уr z следует хr z.

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

Пример 11.

1. Отношение равенства на множестве целых чисел есть отношение эквивалентности.

2. Отношение подобия на множестве треугольников есть отношение эквивалентности.

3. Отношение «строго меньше» на множестве действительных чисел не рефлексивно, не симметрично и транзитивно на этом множестве.

4. Отношение перпендикулярности прямых не рефлексивно, симметрично, не транзитивно.

Пусть r - отношение эквивалентности на множестве Х.

Определение. Классом эквивалентности, порожденным элементом х, называется подмножество множества Х, состоящее из тех элементов yОY, для которых хrу. Класс эквивалентности, порожденный элементом х, обозначается через [x]:

Определение. Отношение r на множестве Х называется антисимметричным, если для любых х, уОХ из хr у и уr х следует х=у.

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

Пример 12.

1. Отношение «х Ј у» на множестве действительных чисел есть отношение частичного порядка.

2. Схема организации подчинения в учреждении есть отношение частичного порядка на множестве должностей.

Любое частично упорядоченное множество можно представить в виде схемы, в которой каждый элемент изображается точкой на плоскости, и если у покрывает х, то точки х и у соединяют отрезком, причем точку, соответствующую х, располагают ниже у. Такие схемы называются диаграммами Хассе. На рис. 10 показаны две диаграммы Хассе, причем вторая соответствует линейно упорядоченному множеству.

Определение. Множества А и В называются эквивалентными (обозначается А ~ В), если существует биективноеотображение f: А ” В.

Для любых множеств А, В, С выполняются следующие свойства:

1) А ~ А;

2) если А ~ В, то В ~ А;

3) если А ~ В и В ~ С, то А ~ С.