§ 4. ОТНОШЕНИЕ ЭКВИВАЛЕНТНОСТИ

Некоторые виды бинарных отношений.

По некоторым важным свойствам бинарные отношения делятся на виды.

ОПРЕДЕЛЕНИЕ. Бинарное отношение R на множестве А называется рефлексивным на А, если для каждого из

Отношение R рефлексивно на А тогда и только тогда, когда , где . Если отношение R рефлексивно, то каждая вершина его графа имеет петлю. Обратно: граф, каждая вершина которого имеет петлю, представляет некоторое рефлексивное отношение.

В качестве примеров рефлексивных отношений можно указать отношение параллельности на множестве прямых плоскости, отношение равенства на каком-либо множестве чисел и отношение делимости на какой-либо совокупности целых чисел.

ОПРЕДЕЛЕНИЕ. Бинарное отношение R на множестве А называется антирефлекстным на А, если для каждого из т. е. для каждого из А не выполняется условие

Отношение R антирефлексивно на А тогда и только тогда, когда Если отношение R антирефлексивно, то ни одна вершина его графа не имеет петли. Обратно: если ни одна вершина графа не имеет петли, то граф представляет антирефлексивное отношение.

Например, отношение неравенства на каком-нибудь множестве чисел и отношение перпендикулярности на множестве прямых плоскости являются антирефлексивными.

ОПРЕДЕЛЕНИЕ. Бинарное отношение R (на А) называется транзитивным (на А), если для любых из области отношения R (из А) из следует

Отношение R транзитивно тогда и только тогда, когда . Если отношение R транзитивно, то его граф обладает свойством: для каждой пары рёбер имеется замыкающее ребро и наоборот.

Например, отношение делимости на множестве целых чисел является транзитивным. Отношение неравенства не является транзитивным.

ОПРЕДЕЛЕНИЕ. Бинарное отношение R (на А) называется симметричным (на А), если для любых у из области отношения R (из А) из следует

Отношение R симметрично тогда и только тогда, когда Если отношение R симметрично, то каждое ребро его графа не ориентировано. Обратно: граф с неориентированными ребрами представляет некоторое симметричное бинарное отношение.

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

ОПРЕДЕЛЕНИЕ. Бинарное отношение R (на А) называется антисимметричным (на А), если для любых из области отношения R (из А) из следует

Отношение R антисимметрично на А тогда и только тогда, когда Граф антисимметричного отношения не имеет неориентированных ребер, но может иметь петли.

Например, отношение включения на какой-либо совокупности множеств является антисимметричным.

ОПРЕДЕЛЕНИЕ. Бинарное отношение R на множестве А называется связанным на А, если для любых элементов множества А из следует

Отношение R связанно на в том и только в том случае, когда

Бинарное отношение R на связанно на тогда и только тогда, когда для любых из либо либо либо

Граф связанного отношения обладает следующим свойством: любые две (различные) вершины графа соединены ребром. Обратное также верно.

Так, например, обычное отношение «меньше» на какой-либо совокупности чисел является связанным.