Бинарные отношения на множестве
Напомним, что произведением двух непустых множеств и называется множество упорядоченных пар , где и .
Определение 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) Транзитивность: пусть .
Следовательно, исследуемое бинарное отношение является отношением эквивалентности.