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

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)}, по этой композиции можно судить о транзитивности отношения Р: если Р ∘ Р Í Р, то отношение транзитивно, поскольку в нашем случае это не так, то данное отношение не транзитивно.