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

N–местным отношением или n–местным предикатом ρ на множествах A₁,A₂,¼,A_n, называется любое подмножество декартова произведения A₁´A₂´¼´A_n. При n=2 отношение называется бинарным. Бинарные отношения чаще рассматриваются, как отношения между элементами одного и того же множества. Пусть это множество М, тогда r Í M´M={(a,b): a,bÎM}.

То, что два элемента a и b находятся в отношении r,записывается так: (a,b)Îr или arb, или a~b(r) – читается: «a находится с b в отношении r». Общая теория бинарных отношений распадается на ряд направлений, изучающих отношения, обладающие теми или иными свойствами.

Бинарное отношение r называется рефлексивным, если любой элемент множества М находится в этом отношении с самим собой, т.е. "aÎM Þ a~a(r).

Отношение r называется транзитивным, если "a, b, с Î M, для которых a~b(r) и b~с(r), обязательно следует, что a~с(r).

Отношение r называется симметричным, если из a~b(r) всегда Þ b~a(r);

Отношение r называется антисимметричным, если одновременное выполнение a~b(r) и b~a(r) возможно только в случае, когда a=b. (Заметим, что пара (a,b), удовлетворяющая данному условию, может вообще не существовать.)

Пример:

1) На множестве натуральных чисел рассмотрим отношение r, согласно которому a~b(r), если a и b взаимно простые числа. Т.о. отношение r ={(2,3); (2,5)}; (2,7); (5,6),…}, а пара (6,9) Ïr. Понятно, что такое отношение не является рефлексивным, т.к. никакое натуральное число не является взаимно простым с самим собой, например, (5,5)Ïr. Рассматриваемое отношение не является также и транзитивным, т.к. существуют пары, например, (6,5)Îr и (5,12)Îr, но пара (6,12)Ïr. Очевидно, что r – симметричное отношение, т.к. всегда, если a взаимно просто с b, то и b взаимно просто с a. Однако, оно не антисимметрично, т.к. из того, что (5,6)Îr и (6,5)Îr не следует, что 5=6.

2) Пусть на множестве В={1, 2, 3, 4} задано бинарное отношение Р={(1,1); (2,3); (3,3); (2,4); (3,4); (4,2)}. Данное отношение не является рефлексивным, т.к. в множестве Р отсутствуют пары (2,2) и (4,4). Отношение Р не является также транзитивным, поскольку, например, пары (3,4) и (4,2) имеются в Р, а пара (3,2) отсутствует. В виду отсутствия пар (3,2) и (4,3) отношение не симметрично. Однако и антисимметричным оно не является, т.к. в нем содержатся пары (2,4) и (4,2), но 4¹2.

Для бинарных отношений, также как и для графиков соответствий определены понятия области значений, области определения, обратного и тождественного отношений, а также композиции отношений. Так для последнего отношения Р областью определения и областью значений является множество В, обратным отношением является Р^–1={(1,1); (3,2); (3,3); (4,2); (4,3); (2,4)}. Найдем композицию Р ∘ Р={(1,1); (2,3); (2,4); (3,3); (3,4); (2,2); (3,2); (4,3)}, по этой композиции можно судить о транзитивности отношения Р: если Р ∘ Р Í Р, то отношение транзитивно, поскольку в нашем случае это не так, то данное отношение не транзитивно.