6. Бинарные отношения и операции над ними

ОПРЕДЕЛЕНИЕ. Пусть А₁, А₂, . . . , А_n – некоторые множества. Их прямым или декартовым произведением называется множество упорядоченных наборов из n элементов, т.е.

А₁А₂ . . . А_n = {(а₁, а₂, . . . , а_n) | a_iA_i }.

Если все множества A_i совпадают A = А₁ = А₂ = . . . = А_n, то прямое произведение А₁А₂ . . . А_n = Aⁿ называют прямой n-ой степенью множества А.

Задача 1.. Доказать, что

(PQ) \ (AB) = ((P \ A)Q)  (P(Q \ B).

Решение.

1) Докажем включение (PQ)\(AB)((P\A)Q) (P(Q\B)).

Пусть (x,y)(PQ) \ (AB), тогда (x,y)(PQ) и (x,y)(AB). Это означает, что xP, yQ и либо xA, либо yB. В первом случае имеем xP, yQ , xA, следовательно, (x, y)(P \ A)Q. Аналогично для второго случая получим, что (x, y)P(Q \ B). Следовательно, (x, y)((P \ A)Q)  (P(Q \ B)).

2) Докажем теперь обратное включение.

Так как (x, y)((P \ A)Q)  (P(Q \ B)), то (x, y)(P \ A)Q  или

(x, y)P(Q \ B). В первом случае получим, что xP, xA, yQ, во втором – xP, yQ , yB. Следовательно, в обоих случаях получим, (x, y)(PQ) и (x, y)(AB), что и означает требуемое.

Бинарным отношением между элементами множеств А и В называется любое подмножество R  AB. Если множества A и B совпадают А = В, то R называют бинарным отношением на множестве А.

Если (x, y)R, то это обозначают еще xRy и говорят, что между элементами x и y установлено бинарное отношение R.

Диагональ множества AA, т.е. множество ={(x,x) | xA}, называется единичным бинарным отношением или отношением равенства в A.

Областью определения бинарного отношения R называется множество _R = { xA |  yB, (x, y) R }.

Областью значений бинарного отношения R называется множество _R = { yB |  xA, (x, y)R }.

Образом множества X относительно отношения R называется множество

R(X) = { yB | (x, y)R, xX };

прообразом X относительно R называется R ^–1(X).

Операции над бинарными отношениями определяются подобно операциям над соответствующими множествами. Пусть А – произвольное множество на котором введены бинарные отношения R, R₁, R₂,...

3) Обратное отношение R ^–1 = { (x, y) | (y, x)R}.

4) Дополнение к отношению ={ (x, y) | (x, y)(AA) \ R}.

5) Двойственное отношение R^d = .

6) Композиция (суперпозиция) отношений R = R₁oR₂  содержит пару (x, y) тогда и только тогда, когда существует такое zA, что (x, z)R₁ и (z, y)R₂.

Задача 2. Найти  _R, _R, R ^–1, R o R, R o R ^–1, R ^–1 o R для отношения R = { (x, y) | x,yN, x делит y }

Решение. _R={ xN  | yN,  x делит y }= N, так как для любого натурального x найдется yN, например y = x, такой, что x делит y.

_R={ yN | xN, x делит y}=N, так как для любого натурального y найдется xN, например x = 1, такой, что x делит y.

R ^–1 ={ (x, y) | x, yN, y делит x }.

RoR={ (x, y)N ² |  zN, x делит z и z делит y } = R, так как для любой пары (x, y)N ², такой, что x делит y, такое значение z существует, например z = x.

RoR ^–1={ (x, y)N ² |  zN, x делит z и y делит z }=N ². Такое натуральное z существует для любой пары (x, y)N ², например z=xy.

R ^–1oR={ (x, y)N ² |  zN, z делит x и z делит y } = N ². Такое натуральное z существует для любой пары (x, y)N ², например z = 1.

Задача 3. Доказать тождествоR = (R^–1 \ R)  (R  R^d).

Решение.

1) Покажем, чтоR  (R^-1 \R)  (R  R^d). Пусть (x, y)R, т.е. (x, y)R. Для пары (y, x) возможны два случая: либо (y, x)R, либо (y, x)R. В первом случае получаем, что (x, y)R^–1 и (x, y)R, следовательно, (x,y) R^–1 \ R. Для второго случая спра-ведливо (x, y)R и (x, y) R^–1 = R^d, что означает (x, y)R R^d. В обоих случаях получим, что (x, y) (R^-1 \ R)  (R  R^d).

2). Докажем теперь обратное включение. Так как (x,y) ( R^–1 \ R)  (R  R^d), то (x, y) R^–1 \R или (x, y)R  R^d. В обоих случаях то, что (x, y)R следует непосредственно из определений пересечения или разности множеств.

Задача 15(г).

Решение.Пусть y_RR, т.е. существует такой xA, что  (x,y) 

R₁oR₂. Следовательно, найдется такое z, что (x,z)R₁ и (z,y) R₂, но это по определению означает, что z  _R и  z_R. Поэтому, z_R_R. Так как (z,y) R₂, то по определению образа множества относительно отношения, получим y R₂(_R_R). R₁^d.

2) Докажем обратное. Пусть y R₂(_R_R), тогда существует элемент x_RR, что (x,y)  R₂. Следовательно, x_Rи x_R xR следует, что найдется такой z, что (z,x)  R₁, а так как (x,y) R₂, то (z,y)  R₁oR₂. Поэтому y_RR .