Материал: discrete_mathematics

7. Довести, що для транзитивного відношення R виконується R(k) R для всіх k ≥ 1.

Доведення здійснимо методом математичної індукції. Для k = 1 твердження справджується, оскільки за означенням R(1) = R. Припустимо, що для транзитивного відношення R виконується R(k) R для всіх k ≤ n. Застосувавши до припущення ін-

для відношення R виконується R°R R. Отже, R(n + 1) R. 8. Довести, що R+ = R(1) R(2) … R(k) … .

Якщо (a, b) R+, то за означенням транзитивного замикання

існує послідовність елементів a1, a2, ..., ak така, що a1 = a, ak = b і a1Ra2, a2Ra3, ..., ak – 1Rak. Звідси робимо висновок, що a1R(k – 1)ak,

тобто aR(k – 1)b для деякого k (k ≥ 2). Отже,

для якогось k, k = 1, 2, .... З означення відношення R(k) і властивостей операції композиції випливає, що існує набір елементів z1, z2, ..., zk + 1, для яких виконуються співвідношення z1 = a, zk + 1 = b і ziRzi + 1 для i = 1, 2, ..., k. Отже, (a, b) R+. ◄

Деякі відношення посідають особливе місце в математиці. Розглянемо ці відношення окремо в наступних параграфах.

Завдання для самостійної роботи

1. Нехай на множині всіх людей P означено відношення:

(в) Pr1R = M iM R ° R–1; (г) Pr2R = M iM R–1 ° R.

122

3.Довести, що для довільних відношень R1 і R2 виконується R1 ° R2 = тоді й тільки тоді, коли Pr2R1 ∩ Pr1R2 = .

4.Визначити, для яких відношень R на множині M виконується рівність:

(а) R°iM = iM; (б) R°iM = R; (в) R –1°R = iM; (г) R°iM°R = iM;

(д) iM°R°iM = iM; (е) R°R = iM.

5. На множині M = {1, 2, 3, 4} задано відношення:

R1 = {(1, 1), (1, 3), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2), (4, 4)}; R2 = {(1, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 3), (4, 1), (4, 4)}; R3 = {(1, 3), (1, 4), (2, 1), (1, 2), (3, 1), (3, 3), (4, 1)};

R4 ={(1, 1), (1, 2), (1, 4), (2, 2), (2, 4), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)}; R5 = {(1, 2), (1, 3), (2, 3), (2, 4), (4, 1), (4, 3)}.

Визначити, які з цих відношень:

(а) рефлексивні; (б) антирефлексивні; (в) симетричні; (г) антисиметричні; (д) транзитивні.

Побудувати графіки, графи й матриці заданих відношень.

6.Проінтерпретуйте властивості відношень за допомогою їх матриць, графіків і діаграм.

7.Довести, що коли R1 R2, тоді для довільного відношення Q виконується:

8. Довести, що відношення R на множині M є рефлексивним

9.Навести приклад двох антирефлексивних відношень R1 і R2 на множині M = {1, 2, 3}, композиція R1°R2 яких буде рефлексивним відношенням.

10.Довести, що відношення R є симетричним тоді й тільки тоді, коли:

11. Довести, що композиція R1 ° R2 симетричних відношень R1 і R2 є симетричним відношенням тоді й тільки тоді, коли

R2 ° R1 R1 ° R2.

12.Довести, що відношення R на множині M антисиметричне тоді й тільки тоді, коли R ∩ R –1 iM.

13.Довести, що об'єднання R1 R2 антисиметричних відношень R1 і R2 на множині M є антисиметричним відношенням то-

ді й лише тоді, коли R1 ∩ R2–1 iM.

123

14.Довести, що рефлексивне відношення R є транзитивним тоді й тільки тоді, коли R°R = R.

15.Довести, що перетин транзитивних відношень є транзитивним відношенням.

16.Довести, що для довільних толерантних відношень R1 і R2 відношення

R1 R2, R1 ∩ R2, R1–1, R1°R2 R2°R1 і R1°R2 ∩ R2°R1

будуть також толерантними.

17.Побудувати толерантні відношення R1 і R2 на множині M = {1, 2, 3}, композиція R1 ° R2 яких не є толерантним відношенням.

18.Довести, що для довільного транзитивного відношення R і для будь-якого k = 0, 1, 2, … відношення R(k) є транзитивним.

19.Довести, що коли R – рефлексивне і транзитивне відношення, тоді R(k) = R для всіх натуральних k.

20.Довести, що для довільного відношення R на скінченній множині M (| M | = n) має місце рівність R+ = R(1) R(2) … R(n).

21.Довести, що відношення R транзитивне тоді й тільки тоді, коли R+ = R.

22.Нехай C – матриця відношення R, заданого на скінченній множині M ( | M | = n). Побудувати матрицю C(k) відношення R(k), k = 0, 1, 2, … .

2.7.Відношення еквівалентності

Відношення R на множині M називають відношенням екві валентності (або просто еквівалентністю), якщо воно рефлек-

сивне, симетричне й транзитивне.

Зважаючи на важливість відношення еквівалентності, дамо розгорнуте означення цього поняття. Відношення R на множині

M є відношенням еквівалентності, або еквівалентністю, якщо воно має такі властивості:

1)aRa для всіх a M (рефлексивність);

2)якщо aRb, то bRa для a, b M (симетричність);

3)якщо aRb і bRc, то aRc для a, b, c M (транзитивність).

124

Приклад 2.28.

1.Відношення рівності iM на будь-якій множині M є відношенням еквівалентності. Рівність – це мінімальне відношення еквівалентності, оскільки з видаленням принаймні одного еле-

мента з iM відношення припиняє бути рефлексивним, отже, і відношенням еквівалентності.

2.Відношення подібності на множині всіх трикутників є еквівалентністю.

3.Важливу роль відіграє в математиці відношення мають однакову остачу при діленні на k, або конгруентні за модулем k,

яке є відношенням еквівалентності на множині N натуральних

чисел для будь-якого фіксованого k N. Відношення конгруент ності за модулем k часто позначають

a ≡ b (mod k)

a та b конгруентні за модулем k.

Цьому відношенню належать, наприклад, пари натуральних чи-

сел (17, 22), (1221, 6), (42, 57) для k = 5, тобто 17 ≡ 22 (mod 5), 1221 ≡ 6 (mod 5), 42 ≡ 57 (mod 5).

4 . На множині M = N N означимо відношення R: ((a, b), (c, d)) R a + d = b + c.

Довести, що R – відношення еквівалентності на множині M. Рефлексивність R випливає із того, що a + b = b + a; симетри-

чність – із того, що коли a + d = b + c, то c + b = d + a. Для обґрунтування транзитивності розглянемо пари ((a, b), (c, d)) R і ((c, d), (e, f)) R. Тоді, додавши почленно рівності a + d = b + c і c + f = d + e, отримаємо a + f = b + e, тобто ((a, b), (e, f)) R.

5. Нехай M = N N. Означимо на множині M відношення R: (a, b) R (c, d) тоді й тільки тоді, коли ab = cd. Довести, що R є еквівалентністю на M. Виписати всі елементи класів еквівалент-

ності [(1, 1)], [(2, 2)], [(4, 3)], [(1, 23)] і [(6, 8)] за відношенням R.

Для доведення, що R є еквівалентністю на множині M, див. попередню задачу. Класу еквівалентності [(a, b)] належать усі такі пари (c, d) натуральних чисел, що cd = ab. Отже,

[(1, 1)] = {(1, 1)}, [(2, 2)] = {(1, 4), (4, 1), (2, 2)},

[(4, 3)] = {(1, 12), (12, 1), (2, 6), (6, 2), (3, 4), (4, 3)}, [(1, 23)] = {(1, 23), (23, 1)},

[(6, 8)] = {(1, 48), (48, 1), (2, 24), (24, 2), (3, 16), (16, 3), (4, 12), (12, 4), (6, 8), (8, 6)}.

125

6. Довести, що об'єднання R1 R2 двох еквівалентностей R1 і R2 є еквівалентністю тоді й тільки тоді, коли R1 R2 = R1 ° R2.

Нехай відношення R1, R2 і R1 R2 є еквівалентностями. Доведемо рівність R1 R2 = R1°R2. Розглянемо елемент (a, b) R1 R2, тоді (a, b) R1 або (a, b) R2. Із рефлексивності

R1 і R2 маємо (b, b) R2 та (a, a) R1, отже, в обох ситуаціях отримаємо (a, b) R1°R2. Для доведення оберненого включен-

ня розглянемо довільний елемент (a, b) R1°R2. Тоді існує елемент c такий, що (a, c) R1 і (c, b) R2. Використавши властивості операції об'єднання, матимемо (a, c) R1 R2 і (c, b) R1 R2. За умовою відношення R1 R2 транзитивне, тому (a, b) R1 R2. Необхідність доведено.

Припустимо, що для еквівалентностей R1 і R2 виконується рівність R1 R2 = R1°R2. Рефлексивність і симетричність об'єднання R1 R2 неважко вивести з рефлексивності й симетричності R1 і R2.

Для доведення транзитивності відношення R1 R2 розгляне-

мо пари (a, b) R1 R2 і (b, c) R1 R2. Останні умови рівносильні такій сукупності співвідношень:

Для 1) або 4) із транзитивності R1 і R2 отримаємо, відповідно

(a, c) R1 або (a, c) R2, звідки матимемо (a, c) R1 R2.

Увипадку2) маємо(a, c) R1°R2, тому(a, c) R1 R2 (заумовою). Нарешті, для 3) послідовно отримаємо: (b, a) R2 і (c, b) R1

(симетричність R1 іR2) (c, a) R1°R2

(c, a) R1 R2 (a, c) R1 R2

(оскільки R1 R2 – симетричне відношення).

7. Довести, що для довільного відношення еквівалентності R виконується рівність R ° R = R.

Нехай (a, b) R°R, тоді існує c такий, що (a, c) R і (c, b) R. Оскільки R транзитивне, то (a, b) R. З іншого боку, якщо (a, b) R, то із рефлексивності R маємо (b, b) R, отже, (a, b) R°R.

8. Довести, що композиція R1 ° R2 двох еквівалентностей R1 і R2 є еквівалентністю, якщо R1 ° R2 = R1 R2.

126