Бинарные отношения на множестве

 

Напомним, что произведением двух непустых множеств и называется множество упорядоченных пар , где и .

Определение 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) Транзитивность: пусть .

Следовательно, исследуемое бинарное отношение является отношением эквивалентности.