Бинарные отношения на множестве
Напомним, что произведением двух непустых множеств
и
называется множество упорядоченных пар
, где
и
.
Определение 1. Любое подмножество называется бинарным отношение (или соответствием). Если
, то бинарное отношение называется бинарным отношением на множестве
. Если пара
принадлежит бинарному отношению
, то говорят, что
находится в отношении
к
и пишут
.
Диагональ есть подмножество
, задающее отношение равенства между элементами множества
.
Для задания бинарного отношения используют те же методы, что и для произвольных множеств, кроме того, бинарное отношение, заданное на конечном множестве
, можно задать в виде графа, а бинарное отношение на множестве
можно задать в виде декартовой диаграммы. Под графом бинарного отношения понимают схему, в которой элементы множества
изображаются точками на плоскости, элементы
, такие, что пары
соединяются стрелкой, направленной от
к
, пары
изображаются петлей вокруг точки
.
Пример 1. Бинарное отношение
делится на
, заданное на множестве
, будет иметь вид
(рис. 1).
Под декартовой диаграммой понимают изображение пар в декартовой прямоугольной системе координат.
Пример 2. Для бинарного отношения
, определенного на множестве
, декартова диаграмма будет следующей (рис. 2).
Рис. 1 Рис. 2
Свойства бинарных отношений:
1.Бинарное отношение на множестве
называется рефлексивным, если для
пара
.
2.Бинарное отношение на множестве
называется антирефлексивным, если для
пара
.
3.Бинарное отношение на множестве
называется симметричным, если для
из принадлежности пары
отношению
следует принадлежность этому отношению также пары
.
4.Бинарное отношение на множестве
называется антисимметричным, если для
из принадлежности пар
и
отношению
следует
.
5. Бинарное отношение на множестве
называется транзитивным, если для
из принадлежности пар
и
отношению
следует принадлежность этому отношению также пары
.
Пример 3.Для каждого из следующих бинарных отношений выяснить, какими свойствами оно обладает и какими не обладает.
1) на
;
2) на множестве
;
3) на множестве
;
Решение.
1) Данное отношение не является рефлексивным, так как для элемента пара
;
– не является антирефлексивным, так как имеются пары и
, принадлежащие
;
– не является симметричным, так как , а
;
– не является антисимметричным, так как пары и
принадлежат
, но
;
– не является транзитивным, так как пары и
принадлежат
, а
;
– является связанным, так как пары ,
,
и
принадлежат
, т.е. все различные элементы связаны.
2) Данное отношение является рефлексивным, поскольку для разность
, т.е.
;
– не является антирефлексивным, так как оно является рефлексивным, т.е. содержит все точки прямой ;
– является симметричным, поскольку принадлежность любой пары отношению
означает
, но тогда и
, т.е.
;
– не является антисимметричным, так как, например, пары и
принадлежат
, но
;
– является транзитивным, поскольку для принадлежность
и
отношению
означает
и
, но тогда
, т.е.
;
– не является связанным, так как, например, для получим
и
.
3) Данное отношение не является рефлексивным, так как из всех пар только пара
, а для остальных
не выполняется равенство
;
– не является антирефлексивным, так как пара ;
– не является симметричным, так как
, а
;
– является антисимметричным, поскольку для любых пар и
должны выполняться равенства
и
, т.е.
и
, но это может быть только в том случае, если
;
– не является транзитивным, так как, например, пара
и пара
, но пара
.
Определение 2.Отношение называется отношением порядка, если оно антисимметрично и транзитивно. Отношение порядка означает, что любые два элемента множества А сравнимы.
Отношение нестрогого порядка обладает свойствами антисимметричности, рефлективности, транзитивности и называется отношением частичного порядка на множестве Х.
Отношение строгого порядка обладает свойствами антисимметричности, антирефлексивности, транзитивности и называется отношением линейного порядка на множестве Х.
Определение 3.Рефлексивное, симметричное и транзитивное отношение на множестве
называется отношением эквивалентности на множестве
. Для отношения эквивалентности часто используют запись
.
Пример 4.Пусть некоторое натуральное число. Проверить, является ли отношением эквивалентности следующее бинарное отношение на множестве целых чисел
.
Решение.Проверим три основных свойства для отношения эквивалентности.
1) Рефлексивность: для выполняется
.
2) Симметричность: пусть
.
3) Транзитивность: пусть
.
Следовательно, исследуемое бинарное отношение является отношением эквивалентности.