Операции над бинарными отношениями

Мы уже знаем, что бинарные отношения являются множествами и, следовательно, можно говорить о равенстве бинарных отношений и о включении одного бинарного отношения в другое: j = y, j Í y.

На бинарные отношения, заданные на некотором множестве переносятся общие операции над множествами. Пусть j и y - бинарные отношения заданные на множестве A. Тогда

1) jÇy - есть бинарное отношение в A являющееся пересечением отношений j и y,

2) jÈy - есть бинарное отношение в A являющееся объединением отношений j и y,

3) j\y - есть бинарное отношение в A являющееся разностью отношений j и y,

4) ` j - есть бинарное отношение в A являющееся дополнением к бинарному отношению j в A, т.е. ` j = A²\j.

Примеры. Определим следующие бинарные отношения

j₁ = {(n,m) Î ²: n ³ m },

j₂ = {(n,m) Î ²: n > m },

j₃ = {(n,m) Î ²: n < m },

j₄ = {(n,m) Î ²: 4n = m² },

тогда между ними имеют место следующие отношения включения:

j₂ Ì j₁; j₁ Èj₂ = j₁, j₁ Çj₂ = j₂, j₁\j₂ = {(n,m) Î ²:n = m } последнее бинарное отношение является отношением равенства в ну и т.д.

Можно определить еще одну операцию над парой заданных на множестве A бинарных отношений j и y.

Определение. Назовем суперпозицией (композицией) этих двух бинарных отношений бинарное отношение (мы будем обозначать его как jy ) определенное следующим образом: (a,c) Î jy Û когда в множестве A найдется хотя бы один элемент b такой, что (a,b) Î j и (b,c) Î y.

Примеры. Для бинарных отношений определенных в предыдущем примере показать, что справедливы следующие равенства:

1) j₁ j₂ = j₂ j₁ = j₂. Действительно, поскольку n ³ m₁, а m₁ > m, то n > m; обратно, если n > m₁ m₁ ³ m, то n > m.

2) j₁j₃ = ². Рассмотрим произвольную пару (n,m) Î ², возможны два случая a)n ³ m; b)n < m. Рассмотрим случай a) (n,m-1) Î j₁, (m-1,m) Î j₃Þ (n,m) Î j₁j₃

в случае b) (n,n-1) Î j₁, (n-1,m) Î j₃Þ (n,m) Î j₁j₃. Итак, мы показали, что ² Í j₁j₃ и следовательно j₁j₃ = ².

3) j₁j₄ ¹ j₄j₁. Этот пример показывает, что суперпозиция бинарных отношений, вообще говоря, не обладает свойством коммутативности.

Доказательство. Поскольку (3,1) Î j₁ и (1,2) Î j₄ мы получаем, что пара (3,2) Î j₁j₄ Теперь надо показать, что пара (3,2) Ï j₄j₁ перепишем бинарное отношение j₄ как j₄ = {((m²)/ 4,m): $k Î , m = 2k} следовательно (3,n) Ï j₄ причем для любого n; откуда получаем, что пара (3,2) Ï j₄j₁, ибо в противном случае (3,n) Î j₄, что невозможно. Доказательство окончено.

Однако легко показать, что

jEM = EM j = j; jÆ = Æj = Æ,

здесь E_M - бинарное отношение равенства в множестве M.

Немного сложнее доказательство следующих равенств. Пусть в множестве A заданы бинарные отношения y и j_i, i Î I, здесь I - конечный или бесконечный набор индексов. Тогда

( È i Î I ji)y = È i Î I (ji y),

y( È i Î I ji) = È i Î I (yji),

заметим, что в вышеприведенных соотношениях значки È нельзя заменить на Ç.

Докажем первое утверждение. Пусть (a,b) Î (È_{i Î I}j_i)y Û $c: (a,c) Î È_{i Î I}j_i и (c,b) Î yÛ $i₀ Î I: (a,c) Î j_i0 Þ (a,b) Î j_i0y Þ (a,b) Î È_{i Î I} (j_iy).

Утверждение. Для любых бинарных отношений j, y,r заданных на некотором множестве A справедливо следующее равенство

(jy)r = j(yr).

Оно означает, что суперпозиция бинарных отношений обладает свойством ассоциативности.

Доказательство.

Пусть пара (a,b) Î (jy)rÞ $c:(a,c) Î jy и (c,b) Î r. Это означает, что $d: (a,d) Î j и (d,c) Î yÞ(d,b) Î yr и (a,b) Î j(yr). Итак мы доказали, что если (a,b) Î (jy)r, то из этого следует, что (a,b) Î j(yr). Обратное включение доказывается аналогично.

Это утверждение говорит о том, что какими бы двумя различными способами мы ни расставляли скобки в выражении j₁ j₂... j_n, чтобы получить суперпозицию двух отношений мы получим равные отношения.

Определение. Пусть на множестве A задано бинарное отношение j, тогда отношением обратным к j называется отношение j^-1 также заданное на A, которое состоит из тех и только тех пар (b,a), для которых справедливо, что (a,b) Î j.

Пример. Пусть на множестве A = {0,1,2,3 } задано бинарное отношение j = {(0,1);(2,3);(1,3)}, тогда j^-1 = {(1,0);(3,2);(3,1) }

Кроме того, справедливы следующие равенства: