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

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

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

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

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

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

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

Пример:

1) На множестве натуральных чисел рассмотрим отношение , согласно которому a~b(), если a и b взаимно простые числа. Т.о. отношение  ={(2,3); (2,5)}; (2,7); (5,6),…}, а пара (6,9) . Понятно, что такое отношение не является рефлексивным, т.к. никакое натуральное число не является взаимно простым с самим собой, например, (5,5). Рассматриваемое отношение не является также и транзитивным, т.к. существуют пары, например, (6,5) и (5,12), но пара (6,12). Очевидно, что  – симметричное отношение, т.к. всегда, если a взаимно просто с b, то и b взаимно просто с a. Однако, оно не антисимметрично, т.к. из того, что (5,6) и (6,5) не следует, что 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)}, по этой композиции можно судить о транзитивности отношения Р: если Р ∘ Р  Р, то отношение транзитивно, поскольку в нашем случае это не так, то данное отношение не транзитивно.