Бинарные отношения. Примеры бинарных отношений

Бинарные отношения.

Пусть A и B – произвольные множества. Возьмем по одному элементу из каждого множества, a из A, b из B и запишем их так: <a, b> (сначала элемент первого множества, затем элемент второго множества – т.е. нам важен порядок, в котором берутся элементы). Такой объект будем называть упорядоченной парой. Равными будем считать только те пары, у которых элементы с одинаковыми номерами равны. <a, b> = <c, d>, если a = c и b = d. Очевидно, что если a ≠ b, то <a, b> ≠ <b, a>.

Декартовым произведением произвольных множеств A и B (обозначается: AB) называется множество, состоящее из всех возможных упорядоченных пар, первый элемент которых принадлежит A, а второй принадлежит B. По определению: AB = {<a, b> | aA и bB}. Очевидно, что если A≠B, то AB ≠ BA. Декартово произведение множества A само на себя n раз называется декартовой степенью A (обозначается: Aⁿ).

Пример 5. Пусть A = {x, y} и B = {1, 2, 3}.

AB = {<x, 1>, <x, 2>, <x, 3>, <y, 1>, <y, 2>, <y, 3>}.

BA = {<1, x>, <2, x>, <3, x>, <1, y>, <2, y>, <3, y>}.

AA = A² = {<x, x>, <x, y>, <y, x>, <y, y>}.

BB = B² = {<1, 1>, <1, 2>, <1, 3>, <2, 1>, <2, 2>, <2, 3>, <3, 1>, <3, 2>, <3, 3>}.

Бинарным отношением на множестве M называется множество некоторых упорядоченных пар элементов множества M. Если r – бинарное отношение и пара <x, y> принадлежит этому отношению, то пишут: <x, y> r или x r y. Очевидно, r Í M².

Пример 6. Множество {<1, 2>, <2, 2>, <3, 4>, <5, 2>, <2, 4>} является бинарным отношением на множестве {1, 2, 3, 4, 5}.

Пример 7. Отношение ³ на множестве целых чисел является бинарным отношением. Это бесконечное множество упорядоченных пар вида <x, y>, где x ³ y, x и y – целые числа. Этому отношению принадлежат, например, пары <5, 3>, <2, 2>, <324, -23> и не принадлежат пары <5, 7>, <-3, 2>.

Пример 8. Отношение равенства на множестве A является бинарным отношением: I_A = {<x, x> | x Î A}. I_A называется диагональю множества A.

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

Областью определения бинарного отношения r называется множество D(r) = { x | существует такое y, что xry }. Областью значений бинарного отношения r называется множество R(r) = { y | существует такое x, что xry }.

Отношением, обратным к бинарному отношению r Í M², называется бинарное отношение r^-1 = {<y, x> | <x, y> Î r}. Очевидно, что D(r^‑1) = R(r), R(r^‑1) = D(r), r^‑1 Í M².

Композицией бинарных отношений r₁ и r₂, заданных на множестве M, называется бинарное отношение r₂ o r₁ = { <x, z> | существует y такое, что <x, y> Î r₁ и <y, z> Í r₂ }. Очевидно, что r₂ o r₁ Í M².

Пример 9. Пусть бинарное отношение r задано на множестве M = {a, b, c, d}, r = {<a, b>, <a, c>, <c, c>, <c, d>}. Тогда  D(r) = {a, c}, R(r) = {b, c, d}, r^‑1 = {<b, a>, <c, a>, <c, c>, <d, c>}, r o r = {<a, c>, <a, d>, <c, c>, <c, d>}, r^‑1 o r = {<a, a>, <a, c>, <c, a>, <c, c>}, r o r^‑1 = {<b, b>, <b, c>, <c, b>, <c, c>, <c, d>, <d, c>, <d, d>}.

Пусть r – бинарное отношение на множестве M. Отношение r называется рефлексивным, если x r x для любого x Î M. Отношение r называется симметричным, если вместе с каждой парой <x, y> оно содержит и пару <y, x>. Отношение r называется транзитивным, если из того, что x r y и y r z следует, что x r z. Отношение r называется антисимметричным, если оно не содержит одновременно пары <x, y> и <y, x> различных элементов x ¹ y множества M.

Укажем критерии выполнения этих свойств.

Бинарное отношение r на множестве M рефлексивно тогда и только тогда, когда I_M Í r.

Бинарное отношение r симметрично тогда и только тогда, когда r = r^‑1.

Бинарное отношение r на множестве M антисимметрично тогда и только тогда, когда r Ç r^‑1 = I_M.

Бинарное отношение r транзитивно тогда и только тогда, когда r o r Í r.

Пример 10. Отношение из примера 6 является антисимметричным, но не является симметричным, рефлексивным и транзитивным. Отношение из примера 7 является рефлексивным, антисимметричным и транзитивным, но не является симметричным. Отношение I_A обладает всеми четырьмя рассматриваемыми свойствами. Отношения  r^‑1 o r и r o r^‑1 являются симметричными, транзитивными, но не являются антисимметричными и рефлексивными.

Отношением эквивалентности на множестве M называется транзитивное, симметричное и рефлексивное на М бинарное отношение.

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

Пример 11. Отношение из примера 7 является отношением частичного порядка. Отношение I_A является отношением эквивалентности и частичного порядка. Отношение параллельности на множестве прямых является отношением эквивалентности.