Свойства операций над отношениями

⇐ ПредыдущаяСтр 4 из 8Следующая ⇒

Приведем здесь список основных свойств операций над отношениями и докажем некоторые из них.

1) Ç R_k^–1=( Ç R_k) ^–1.k k

2) È R_k^–1=(È R_k)^–1. k k

3) (R₁o R₂)^–1 = R₁^–1o R₂^–1.

4) (R₁o R₂) o R₃= R₁o (R₂o R₃).

5) (R₁È R₂) o R₃= (R₁o R₃) È ( R₂o R₃).

6) (R₁Ç R₂) o R₃Í (R₁o R₃) Ç ( R₂o R₃).

7) а) если R₁Í R₂ то R₁o R₃Í R₂o R₃;

б) если R₁Í R₂ то R₃o R₁Í R₃o R₂;

в) если R₁Í R₂ то R₁^–1Í R₂^–1.

8) a) (R₁È R₂)^d= R₁^dÇ R₂^d;

б) (R₁Ç R₂)^d = R₁^dÈ R₂^d;

в) (R ^d)^d= R.

ДОКАЗАТЕЛЬСТВО.

Свойство 2.

Пусть пара (x, y)Î (È R_k ) ^–1. Тогда (y, x)Î È R_k. Это означает, что найдется отношение R_j, что (y, x)Î R_j. Отсюда, по определению обратного отношения, (x, y)Î R_j^–1, а значит, (x, y)Î È R_k^–1и (È R_k)^–1Í È R_k^–1.

Докажем обратное включение. Пусть (x, y)Î R_k^–1 Это означает, что найдется такое множество R_j, что (x, y)Î R_j^–1. Следовательно, (y, x)Î R_j и (y, x)Î È R_k, поэтому (x, y)Î (È R_k )^–1. Значит, È R_k^–1Í (È R_k)^–1.

Одновременное выполнение обоих включений означает

равенство множеств, что и требовалось доказать.

Свойство 6.

Пусть (x, y)Î (R₁ Ç R₂) o R₃. По определению композиции это означает, что найдется такое zÎ A, что (x, z)Î (R₁Ç R₂) и (z, y)Î R₃. Первое включение возможно только тогда, когда одновременно выполнено (x, z)Î R₁ и (x, z)Î R₂. Это, в свою очередь означает, с учетом (z, y)Î R₃, что одновременно (x, y)Î R₁o R₃ и (x, y)Î R₂o R₃, а, следовательно, (x, y)Î (R₁o R₃) Ç (R₂o R₃), что и доказывает требуемое соотношение.

ЗАМЕЧАНИЕ. Покажем, почему неверно обратное включение. Пусть (x, y)Î (R₁o R₃) Ç (R₂o R₃), тогда (x, y) Î (R₁o R₃) и (x, y) Î (R₂o R₃). Первое включение означает существование такого элемента z₁ из A, что (x, z₁)Î R₁и (z₁, y)Î R₃, второе – существование такого z₂Î A, что (x, z₂)Î R₂ и (z₂, y)Î R₃, причем необязательно z₁= z₂. Значит, не всегда существует такой элемент z, что (x, z)Î R₁и (x, z)Î R₂, а, следовательно, не будет принадлежности пересечению R₁ и R₂.

Свойство 7в.

Возьмём любую пару (x, y)Î R₁, что эквивалентно (y, х)Î Î R₁^–1. Пусть теперь R₁Í R₂, т.е. из (x, y)Î R₁следует (x, y)Î R₂. Перейдя к обратным отношениям, получим, что из (y, х)Î R₁^–1 вытекает (y, х)Î R₂^–1, что и означает требуемое свойство.

Свойство 8а.

Докажем предварительно равенство =

Пусть (x, y)Î . Следовательно, (y, x) Î `R или, другими словами, (y, x)Ï R. Отсюда, ( x, y)Ï R^–1, что означает и (x, y)Î . Если же (x, y) Î , то (x, y)Ï R^–1 и (y, x)Ï R. Тогда (y, x)Î `R или, что то же самое, (x, y)Î (`R )^–1.

Для доказательства свойства 8а воспользуемся доказанным равенством и известными свойствами операций над множествами и отношениями. _________ _____

(R₁È R₂)^d = ( R₁È R₂)^–1 = R₁È R₂^-=

= (`R₁Ç `R₂) =`R₁^–1 Ç R₂^–1 = R₁^d Ç R₂^d.

КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

1. Доказать, что:

а) d_R= Æ Û R=Æ Û r_R = Æ; б) d_R^–1 =r_R, r_R^–1=d_R;

в) d_R_°_R= R₁^-1(r_RÇ d_R); г*) r_R_°_R= R₂(r_RÇ d_R);

д) если B¹ Æ то d_A_´_B =A; е) если A¹ Æ то r_A_´_B=B.

2. Доказать, что R ¹ R^d для произвольного отношения R.

3*. Доказать тождество`R = (R^–1 \ R) È (`R Ç R^d).

4. Доказать включение R^–1Í RÈ (`R Ç R^–1).

5. Какими свойствами должно обладать бинарное отношение

R, чтобы выполнялось равенство R^–1 =`R?

6. Доказать, что для любых бинарных отношений:

а) Qo(È R_i) = È (Q o R_i); I Î I i Î I б) Q o ( Ç R_i) Í Ç (Q oR_i); i Î I i Î I

в) (È R_i)oQ = È (R_i oQ); i Î I i Î I г) (Ç R_i)oQ Í Ç ( R_ioQ). i Î I i Î I

7. Доказать, что для того, чтобы отношение R Í A´ B было вза-

имно однозначным соответствием между A и B, необходимо и достаточно, чтобы R o R^–1 = R^–1o R = D.

Примеры решения

Задача 1(г).

Пусть yÎ r_R_°_R, т.е. существует такой xÎ A, что (x, y) Î

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

2) Докажем обратное. Пусть yÎ R₂(r_RÇ d_R), тогда существует элемент xÎ r_R_°_R, что (x, y) Î R₂. Следовательно, xÎ r_Rи xÎ d_RxÎ rR следует, что найдется такой z, что (z, x) Î R₁, а так как (x, y)Î R₂, то (z, y) Î R₁oR₂. Поэтому yÎ r_R_°_R.

Задача 3.

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 следует непосредственно из определений пересечения или разности множеств.

3. Способы задания бинарных отношений

Традиционное задание отношений аналогично тому, как это принято в теории множеств, что не всегда удобно. Поэтому, наряду с таким заданием, применяются другие способы.

1. Матричное задание. Оно используется когда А – конечное или счетное множество А = {x_i}. Тогда отношение R можно задавать с помощью матрицы R = {x_ij}, элементы которой определяются соотношением:

2. Задание с помощью графа.

Для конечного или счетного множества А отношение можно задавать с помощью графа Г(R), который является геометрическим образом бинарного отношения. Граф – фигура состоящая из точек (вершин) соединенных линиями (дугами). Вершины графа соответствуют элементам множества А, то есть x_i, а наличие дуги, соединяющей вершины x_i и x_j, означает, что (x_i, x_j)Î R. Чтобы подчеркнуть упорядоченность пары на дуге ставится стрелка.

Основные свойства графа.

1) Г(R^–1) получается из Г(R) изменением направления стрелок на противоположные.

2) Граф Г(А´ А) содержит дуги, соединяющие любую пару (x_i, x_j). Такой граф назывыется полным.

3. Задание верхними и нижними срезами.

Этот способ может быть использован для любых множеств и отношений. Пусть на множестве А задано отношение R. Верхний срез G_R(x) отношения R в точке x Î А - это множество элементов yÎ А таких, что (y, x)Î R, т.е.

G_R(x) = { yÎ A | (y, x)Î R }.

Если рассматривать R как отношение предпочтения, то G_R (x) – это множество элементов, лучших чем х.

Нижний срез H_R(x) отношения R в точке xÎ А – это множество элементов yÎ А, таких, что (x, y)Î R, т.е.

H_R(x) = { yÎ A | (x, y)Î R }.

Свойства нижних и верхних срезов.

Для любого хÎ A и любого отношения R_iÍ A´ A выполняя-ются соотношения.

1. а)G_R_Ç_R(x)=G_R(x)Ç G_R(x); б) H_R_Ç_R(x)=H_R(x)Ç H_R(x)

2. a) G_`_R(x) = A \ G_R(x); б)H_`_R(x) = A \ H_R(x).

3. a) G_R^–1(x) = H_R(x); б) H_R^–1(x) = H_R(x).

4. G_A_´_A(x) = H_A_´_A(x) = A.

КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

1. Пусть X = {2, 3, 4, 5, 6, 7, 8, 9}. Построить матрицу и граф следующих бинарных отношений:

а) R = { (x_i, x_j) | x_i, x_jÎ X, x_i делится на x_j };

б) R = { (x_i, x_j) | x_i, x_jÎ X, x_i > x_j };

в) R = { (x_i, x_j) | x_i, x_jÎ X, x_i и x_j имеют общий делитель};

г) R = { (x_i, x_j) | x_i, x_jÎ X, x_i × x_j £ 15};

д) R = { (x_i, x_j) | x_i, x_jÎ X, $ n: x_j =x_i ⁿ }.

2*. Для бинарных отношений R, определенных в задаче 15 п.1 построить множества G_R(x) и H_R(x).

3. Пусть x=(x₁, x₂) и R = { (x, y) |, x, yÎ R, r(x, y) £ k}. По-

строить верхний и нижний срезы отношения R, если:

а) r(x, y) = ; б) r(x, y) = max | x_i- y_i|; i i

в) r(x, y) = å | x_i - y_i |. i

Пример решения

Задача 2 для отношения, определенного в задаче 15(г) п.1.

G_R(x) ={ yÎ R | 2y ³ 3x }= [ 3x/2, +¥ ),

H_R(x) ={ yÎ R | 2x ³ 3y } = ( - ¥ , 2x/3 ].

Свойства бинарных отношений

1) Рефлексивность.

Отношение R называется рефлексивным, если (х, х)Î R для любого хÎ A.

Примеры рефлексивных отношений: отношения " ³ ", " £ " на множестве R.

2) Антирефлексивность.

Отношение R называется антирефлексивным, если (х, х)Ï R для любого хÎ A.

Примеры антирефлексивных отношений: отношения " < ", " > " на множестве R.

Если R – антирефлексивное отношение, то xÏ G_R(x) и хÏ H_R(x) для любого хÎ A.

3) Симметричность.

Отношение R называется симметричным, если для любых x, yÎ A из того, что (x, y)Î R следует (y, x)Î R и обратно.

Примеры симметричных отношений: отношения " =" и " ¹ ".

Если отношение R симметрично, то для любого хÎ A

а) G_R(x) = H_R(x); б) R = R^–1.

4) Антисимметричность.

Отношение R называется антисимметричным, если для любых x и y из A из одновременного выполнения условий (x, y)Î R и (y, x)Î R следует, что x = y.

Пример антисимметричного отношения. Пусть А – множество людей в данной очереди. Отношение R – " не стоять за кем-

то в очереди" будет антисимметричным.

Пусть х = ВАСЯ, а y = ИВАНОВ. Тот факт, что (x, y)Î R означает, что " ВАСЯ не стоит в очереди за ИВАНОВЫМ", (y, x)Î R – " ИВАНОВ не стоит за ВАСЕЙ". Очевидно, что одновременное выполнение обоих включений может быть, только если ВАСЯ и есть ИВАНОВ, т.е. x = y.

Отношение " ³ " также антисимметрично: если x ³ y и y ³ x, то x=y.

5) Асимметричность.

Отношение R асимметрично, если R Ç R^-1= Æ, т.е. пересечение отношения R с обратным отношением пусто.

Эквивалентное определение асимметричности: из двух отношений (x, y)Î R и (y, x)Î R одно не выполняется.

Примеры асимметричных отношений: " > ", " < ", " быть начальником".

Если R – асимметричное отношение, то из xRy следует y x.

Для любого отношения R вводятся понятия симметричной части отношения R^s= R Ç R^-1 и асимметричной части отношения R^a = R \ R^s. Если отношение R симметрично, то R= R^s, если отношение R асимметрично, то R = R^a.

Примеры. Если R – " ³ ", то R^–1 – " < ", R^s – " =", R^a – " > ".

6) Транзитивность.

Отношение R транзитивно, если для любыx x, y, zÎ A из того, что (x, y)Î R и (y, z)Î R следует (x, z)Î R.

Свойства транзитивного отношения:

а) RoR Í R;

б) для любого хÎ A из yÎ G_R(x) следует, что G_R(y) Í G_R(x).

Нетранзитивным является отношение " ¹ ". Пусть x = 2, y = 3, z = 2, тогда справедливо x ¹ y и y ¹ z, но x = z, т.е. (x, z)Ï R.

Отношение R₁ называется транзитивным относительно отношения R₂, если:

а) из (x, y)Î R₁ и (y, z)Î R₂ следует, что (x, z)Î R₁;

б) из (x, y)Î R₂ и (y, z)Î R₁ следует, что (x, z)Î R₁.

7) Негатранзитивность.

Отношение R называется негатранзитивным, если`R транзитивно.

Примеры.

Отношения R₁–" > " и R₂–" ¹ " негатранзитивны, так как отношения`R₁ – " £ ", `R₂ – " =" транзитивны. Возможно одновременное выполнение свойств транзитивности и негатранзитивности. Например, отношение R₁одновременно транзитивно и негатранзитивно, а R₂, как известно, транзитивным не является.

8) Полнота.

Отношение R полно, если для любых x, yÎ А либо (x, y)Î R, либо (y, x)Î R, либо оба отношения выполняются одновременно.

Свойства полных отношений:

а) G_R(x) È H_R(x) = А для любого хÎ A;

б) полное отношение рефлексивно.

9) Слабая полнота.

Отношение R называется слабо полным, если для любых х ¹ y из А или (x, y)Î R, или (y, x)Î R.

Пример слабо полного отношения. Пусть А – множество предприятий, " неблагополучных" в смысле своего бюджета. Отношение R " быть должным" является слабо полным, так как каждое из этих предприятий или кому-либо должно, или ему кто-то должен, но быть должным самому себе нельэя и (x, x)Ï R.

10) Ацикличность.

Бинарное отношение R ациклично, если RⁿÇ R^–1= Æ для любого nÎ N. Иными словами, если из любой конечной цепочки отношений х₁Rx₂, x₂Rx₃,..., x_n_-1Rx_n следует, что x₁¹ х_n, то отношение R ациклично.

1. Отношение R слабо полно тогда и только тогда, когда R^dантисимметрично.

ДОКАЗАТЕЛЬСТВО. Пусть R слабо полно и x ¹ y. Рассмотрим три случая.

1) (x, y)Î R.Тогда, по определению обратного отношения (y, x)Î R^-1, а по определению двойственного отношения – (y, x)Ï R^d.

2) (y, x)Î R, тогда (x, y)Î R^–1 и, следовательно, (x, y)Ï `R^–1 = R^d.

3) (x, y)Î R и одновременно (y, x)Î R. Отсюда, (y, х)Ï R^d и (x, y)Ï R^d.

Так как R – слабо полное отношение, то для любых x ¹ y выполняется либо случай а), либо б), либо в). Ни в одном из этих случаев включения (x, y)Î R^d и (y, x)Î R^d не могут выполняться одновременно. Следовательно, отношение R^d антисимметрично.

Докажем, что из антисимметричности R^d следует слабая полнота отношения R. Рассмотрим эквивалентное определение антисимметричности. Если x ¹ y, то либо (x, y)Î R^d и (y, x)Ï R^d, либо (x, y)Ï R^d и (y, x)Î R^d, либо (x, y)Ï R^d и (y, x)Ï R^d. В первом случае получим, что (x, y)Î R, во втором – (y, x)Î R, в третьем – (x, y)Î R и (y, x)Î R. Это утверждение означает, что отношение R слабо полно.

2. Отношение R асимметрично тогда и только тогда, когда R^d полно.

ДОКАЗАТЕЛЬСТВО. Пусть R – асимметрично. Тогда по определению, R Ç R^–1 = Æ. Рассмотрим два случая.

1) (x, y)Î R. Тогда (х, y)Ï R^–1, значит, (x, y)Î R^d.

2) (x, y)Ï R. Тогда (x, y)Î `R и (y, x) Î `R^–1 = R^d.

В любом случае либо (x, y)Î R^d, либо (y, x)Î R^d, а это означает, что R^d – полно.

Докажем обратное следствие. Пусть R^d полно. Снова рассмотрим два случая:

а) (x, y)Î R^d, тогда (y, x)Ï R;

б) (y, x)Î R^d, тогда (x, y)Ï R.

Так как R^d полно, то либо случай а), либо случай б) всегда будет иметь место, а отсюда следует невозможность одновременного выполнения yRx и xRy. Это означает, что R асимметрично.

КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

1. Доказать, что если отношение R транзитивно, то R^–1 также является транзитивным.

2. Доказать, что из асимметричности отношения R следует асимметричность R^–1.

3. Доказать, что из антисимметричности отношения R следует антисимметричность R^–1.

4. Доказать, что из рефлексивности отношения R следует рефлексивность R^–1.

5. Доказать, что для симметричности отношения R необходимо и достаточно, чтобы R^d было симметрично.

6. Отношение R симметрично тогда и только тогда, когда R = R^-1.

7. Доказать, что если отношения R₁ и R₂ рефлексивны, то рефлексивны отношения R₁È R₂, R₁Ç R₂, R₁^–1.

8. Доказать, что если отношения R₁ и R₂ антирефлексивны, то антирефлексивны и отношения R₁È R₂, R₁Ç R₂, R₁^–1. Показать, что композиция R₁o R₂ антирефлексивных отношений может не быть антирефлексивной.

9. Доказать, что если отношения R₁ и R₂ симметричны, то симметричныны отношения R₁È R₂, R₁Ç R₂, R₁^–1, R₁o R₁^–1.

10. Доказать, что если отношения R₁ и R₂ антисимметричны, то антисимметричны также R₁Ç R₂ и R₁^–1.

11. Пусть отношения R₁, R₂ – симметричны. Доказать, что для того чтобы R₁o R₂ было симметрично необходимо и достаточно, чтобы выполнялось равенство R₁o R₂ = R₂o R₁.

12. Пусть отношения R₁и R₂ антисимметричны. Объединение R₁È R₂ антисимметрично тогда и только тогда, когда R₁Ç R₂^-1Í D.

13. Доказать, что если отношение R асимметрично, то R Ç R₁асимметрично для любого отношения R₁.

14. Доказать, что объединение R₁È R₂ асимметричных отношений R₁и R₂асимметрично тогда и только тогда, когда R₁Ç R₂^-1== Æ.

15. Доказать, что если отношение транзитивно, то его симметричная и асимметричная части тоже транзитивны.

16. Пусть отношения R₁, R₂ транзитивны и R₁ транзитивно относительно R₂. Доказать, что тогда R₁È R₂ также является транзитивным.

17*. Доказать, что если отношения R₁, R₂ рефлексивны, то справедливо включение R₁È R₂ Í R₁oR₂.

18. Доказать, что отношение R асимметрично тогда и только тогда, когда R = ( R^d)^a.

19. Доказать, что для того чтобы отношение R было полным необходимо и достаточно, чтобы выполнялось тождество

R^a= R^d.

20. Доказать, что если отношения R₁, R₂ рефлексивны, то их композиция тоже рефлексивна.

21*. Доказать, что отношения R È (`R Ç R^d ) = R È (`R )^s полны.

22. Доказать, что если отношение R полно, то`R Ì R^–1 и R^–1 ==`R È (R Ç R^–1).

23. Доказать, что если отношение R асимметрично, то R^–1Ì `R и`R = R^–1È (`RÇ R^d).

24. Доказать, что композиция полных отношений R₁ и R₂ является полным отношением.

25*. Отношение Р негатранзитивно тогда и только тогда, когда xPy Þ " zÎ А, xPz или zPy.

26. Доказать, что если R рефлексивно, то R^d антирефлексивно, если R антирефлексивно, то R^d рефлексивно.

27. Доказать, что полное отношение рефлексивно.

28. Доказать, что асимметричное отношение антирефлексивно.

29*. Доказать, что отношение R негатранзитивно тогда и только тогда, когда R^d транзитивно.

30. Пусть отношение R симметрично, транзитивно и для любого x существует такой y, что (x, y)Î R. Доказать, что оно рефлексивно.

31. Доказать, что ацикличное отношение асимметрично.

32. Доказать, что если отношение антирефлексивно и транзитивно, то оно ациклично.

33. Доказать, что асимметричное и негатранзитивное отношение транзитивно.

34. Доказать, что если отношение антирефлексивно, транзитивно и слабо полно, то оно негатранзитивно.

35. Доказать, что дополнение и двойственное отношение к антисимметричному и рефлексивному отношению R являются слабо полными.

36. Доказать, что любое отношение R симметричное и антисимметричное одновременно, является транзитивным.

37. Доказать, что для того чтобы отношение R было асимметричным необходимо, чтобы R^d и`R были полными.

38. Построить бинарное отношение:

а) рефлексивное, симметричное, не транзитивное;

б) рефлексивное, антисимметричное, не транзитивное;

в) рефлексивное, не симметричное, транзитивное;

г) не рефлексивное, антисимметричное, транзитивное;

д) симметричное, транзитивное, но не рефлексивное.

Примеры решения

Задача 17.

Пусть (x, y)Î R₁È R₂, тогда (x, y)Î R₁ или (x, y)Î R₂. В первом случае из рефлексивности R₂ следует (y, y)Î R₂ и, следовательно,

(x, y)Î R₁o R₂. Аналогично для второго случая получим (x, x)Î R₁ и (x, y)Î R₁o R₂, что и требовалось доказать.

Задача 21.

Докажем равенство множеств, воспользовавшись свойствами операций над множествами и отношениями.

RÈ (`R Ç R^d) = R È (`R Ç ) = R È (`RÇ (`R )^-1) = R È (`R )^s.

Покажем теперь, что отношение R È (`R )^s полно. Для любых x, yÎ A возможен один из трех случаев: 1) (x, y)Î R; 2) (y, x)Î R; 3) (x, y)Ï R и (y, x)Ï R. В первых двух случаях принадлежность (x, y) к рассматриваемому отношению очевидна. Рассмотрим третий случай. Так как (x, y)Î `R и (x, y)Î ^-1, то (x, y)Î (`R )^s. Следовательно, рассматриваемое отношение полно.

Задача 25.

Докажем необходимость. Предположим противное, что отношение Р негатранзитивно, но

xPy и $ z: x`P z и z`P y. (1)

Так как Р негатранзитивно, то из (1) следует одновременное выполнение xРy и x y, а этого быть не может, поэтому из негатранзитивности следует

xPy Þ " zÎ А, xPz или zPy. (2)

Докажем обратное следствие. Предположим противное, т.е. что (2) выполнено, но Р не является негатранзитивным. Последнее означает, что

$ x, y, zÎ A: x`Pz, z`Py, но (x, y) Ï `P,

т.е. (x, y)Î P. Таким образом, получаем, что xPy выполняется, а xPz и zPy не выполняется, и, значит, (4) неверно, что противоречит предположению. Полученное противоречие доказывает требуемое следствие.

Задача 29.

Пусть отношение R негатранзитивно, т.е. если (x, y)Ï R и (y, z)Ï R, то (x, z)Ï R. Пусть для u, v, w выполнены условия (u, v)Î R^d и (v, w)Î R^d. Тогда, по определению двойственного отношения, (v, u)Ï R и (w, v)Ï R. Так как R негатранзитивно, то (w, u)Ï R, что означает (u, w)Î R^d. Следовательно, R^d транзитивно.

Обратное следствие доказывается аналогично.

⇐ Предыдущая 1 2 345 6 7 8 Следующая ⇒