Відношення еквівалентності. 1. Для фіксованого натурального числа k на множині N визначимо відношення R: (m,n)ÎR тоді і тільки тоді

1. Для фіксованого натурального числа k на множині N визначимо відношення R: (m, n)Î R тоді і тільки тоді, коли
m - n ділиться на k. Довести, що відношення R є відношенням еквівалентності на N.

2. На множині N ´ N визначимо відношення R і Q:

(а) ((a, b),(c, d))Î R Û a + d = b + c;

(б) ((a, b),(c, d))Î Q Û a×d = b × c.

Довести, що відношення R і Q є відношеннями еквівалентності на множині N ´ N.

3. Нехай M = N ´ N. Означимо на множині M відношення R таким чином: (a, b) R (c, d) тоді і тільки тоді, коли

(а) ab = cd; б) a + b = c + d.

Довести, що R є еквівалентністю на M. Виписати всі елементи класів еквівалентності [(1,1)], [(2,2)], [(4,3)], [(1,23)] і [(6,8)] за відношенням R.

4. На множині дійсних чисел означимо відношення H: xHy тоді і тільки тоді, коли (x - y) - раціональне число. Довести, що відношення H є відношенням еквівалентності.

5. На множині N натуральних чисел означимо відношення R: mRn тоді і тільки тоді, коли m / n = 2 ^k для деякого цілого k.

(а) Довести, що R є відношенням еквівалентності на N.

(б) Скільки різних класів еквівалентності є серед [1] _R, [2] _R, [3] _R і [4] _R?

(в) Скільки різних класів еквівалентності є серед [6] _R, [7] _R, [12] _R, [24] _R, [28] _R, [42] _R і [48] _R?

6. Нехай у множині M зафіксовано деяку підмножину K Í M. Означимо відношення R на b(M): ARB тоді і тільки тоді, коли A Ç K = B Ç K, A, B Îb(M).

(а) Довести, що R є відношенням еквівалентності на b(M).

(б) Для M = {1,2,3} і K = {1,2} знайти класи еквівалентності за відношенням R.

(в) Для M = {1,2,3,4,5} і K = {1,2,3} визначити [ A ] _R, де A = {2,3,4}.

(г) Для M = {1,2,3,4,5} і K = {1,2,3} визначити кількість класів еквівалентності та кількість підмножин множини M у кожному класі еквівалентності за відношенням R.

(д) Визначити кількість класів еквівалентності та кількість підмножин множини M у кожному класі еквівалентності за відношенням R, якщо | M |= n і | K |= m.

7. Нехай M множина всіх прямих на площині. Чи будуть еквівалентностями на M такі відношення:

(а) паралельність прямих; (б) перпендикулярність прямих?

8. Довести, що відношення рівності i_M на будь-якій множині M є відношенням еквівалентності.

9. Довести, що для довільного відношення еквівалентності R на множині M виконується i_M Í R. Таким чином, i_M є найменшим відношенням еквівалентності на множині M.

10. Довести, що відношення рівнопотужності множин є еквівалентністю.

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

13. Довести, що R є відношенням еквівалентності тоді і тільки тоді, коли R^{- 1} є відношенням еквівалентності.

14. Довести, що перетин будь-якої сукупності відношень еквівалентності на множині M є еквівалентністю на M.

15. Навести приклад двох еквівалентностей R ₁ і R ₂ на множині M ={1,2,3,4}таких, що R ₁È R ₂ не є еквівалентністю на множині M.

16. Довести, що об’єднання R ₁È R ₂ двох еквівалентностей R ₁ і R ₂ є еквівалентністю тоді і тільки тоді, коли R ₁È R ₂= R ₁° R ₂.

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

18. Навести приклад двох еквівалентностей R ₁ і R ₂ на множині M ={1,2,3,4}таких, що R ₁° R ₂ не є еквівалентністю на M.

19. Довести, що композиція R ₁° R ₂ двох еквівалентностей R ₁ і R ₂ є еквівалентністю, якщо R ₁° R ₂ = R ₁È R ₂.

20. Довести, що композиція R ₁° R ₂ двох еквівалентностей R ₁ і R ₂ є еквівалентністю тоді і тільки тоді, коли

(а) R ₁° R ₂ = R ₂° R ₁; (в) R ₂° R ₁ Í R ₁° R ₂;

(б) R ₁° R ₂ - симетричне відношення; (г) R ₁° R ₂ = R ₁° R ₂ È R ₂° R ₁.

21. Довести, що коли R ₁ і R ₂ - еквівалентності, то відношення (R ₁È R ₂)^* також буде еквівалентністю.

22. Довести, що коли R ₁ і R ₂ - еквівалентності, то відношення (R ₁° R ₂È R ₂° R ₁)^* також буде еквівалентністю.

23. Довести, що коли R ₁ і R ₂ - еквівалентності, то (R ₁È R ₂)^* = (R ₁° R ₂È R ₂° R ₁)^*.

24. Довести, що коли R ₁ і R ₂ - еквівалентності і R ₁° R ₂ = R ₂° R ₁, то R ₁° R ₂ = (R ₁È R ₂)^*.

25. Нехай R ₁ і R ₂ - еквівалентності і R ₁° R ₂= R ₂° R ₁. Довести, що R ₁° R ₂ є найменшим відношенням еквівалентності, яке містить R ₁È R ₂.

26. Нехай R ₁ і R ₂ - еквівалентності. Довести, що найменшим відношенням еквівалентності, яке містить R ₁È R ₂, є (R ₁È R ₂)^*.

27. Нехай R ₁ і R ₂ - еквівалентності. Довести, що найменшим відношенням еквівалентності, яке містить R ₁È R ₂, є (R ₁° R ₂È R ₂° R ₁)^*.

28. Довести, що для довільної сукупності відношень еквівалентності { R_i }, i Î I існує еквівалентність Q така, що R_i Í Q і для будь-якого відношення еквівалентності R з включення R_i Í R випливає Q Í R (тобто Q є найменшим відношенням еквівалентності, яке містить R_i)

29. Побудувати найменше відношення еквівалентності Q на множині M = {1,2,3,4}, яке включає задане відношення R.

(а) R = {(2,4),(3,1)};

(б) R = {(1,1),(1,2),(2,3),(3,3)};

(в) R = {(1,2),(2,2),(1,3),(2,3),(4,2)}.

30. Довести, що для довільної сукупності еквівалентностей { R_i }, i Î I найменшою еквівалентністю Q, яка містить R_i, є відношення ( R_i)^*.

31. Нехай задано довільне відношення R на множині M. Сформулювати алгоритм, який за допомогою основних операцій над відношеннями дозволяє побудувати найменше відношення еквівалентності Q на множині M таке, що R Í Q.

Застосувавши цей алгоритм до заданого відношення R на множині M ={1,2,3,4,5}, знайти відповідне відношення еквівалентності Q.

(а) R = {(1,1),(1,2),(4,2),(5,4)};

(б) R = {(2,4),(3,3),(3,2),(4,1),(4,2),(5,1),(5,5)};

(в) R = {(2,2),(3,3)}.

Для кожного з відношень Q побудувати фактор-множину M/Q.

32. Довести, що для довільного відношення R на множині M найменше відношення еквівалентності Q, яке містить R, дорівнює (R È i_M È R^{- 1})^*.

33. Знайти відношення R на множині M = {1,2,3,4}, яке містить мінімально можливу кількість елементів і таке, що найменшим відношенням еквівалентності Q, що включає R, є повне відношення на M, тобто Q = M ´ M.

34. Побудувати на множині M = { a ₁, a ₂,..., a_n } відношення R з мінімально можливою кількістю елементів таке, що найменше відношення еквівалентності Q, що містить R, збігається з повним відношенням на M, тобто Q = M ´ M.

35. Визначити мінімально можливу кількість елементів у відношенні R на множині M = { a ₁, a ₂,..., a_n }, для якого найменшим відношенням еквівалентності M, що містить R, є повне відношення на M, тобто Q = M ´ M.

Дати геометричну (графову) інтерпретацію відповіді.

36. Довести, що транзитивне замикання R ^* толерантного відношення R є відношенням еквівалентності.

37. Довести, що транзитивне замикання R ^* відношення еквівалентності R збігається з R, тобто R ^* = R.

38. Навести приклад відношення R на множині M = {1,2,3,4}, для якого виконується R ^* = R і яке не є еквівалентністю.

39. Нехай R ₁ - толерантне відношення, R ₂ - еквівалентність і R ₁Í R ₂. Довести, що R ₁^*Í R ₂.

40. Довести, що найменшим відношенням еквівалентності Q, яке містить толерантне відношення R, є R ^*.

41. Нехай R ₁ і R ₂ - відношення еквівалентності на множині M. Довести, що відношення R ₁° R ₂° R ₁ буде еквівалентністю тоді і тільки тоді, коли

(а) R ₂° R ₁° R ₂Í R ₁° R ₂° R ₁; (б) R ₁° R ₂° R ₁ = R ₁° R ₂È R ₂° R ₁.

41. Нехай R транзитивне й симетричне відношення на множині M і Pr₁ R ÈPr₂ R=M. Довести, що R є еквівалентністю на множині M.

43. Довести, що коли R рефлексивне й транзитивне відношення на множині M, тоді R Ç R^{- 1} є відношенням еквівалентності на множині M.

44. Нехай R є відношенням на M. Довести, що R є еквівалентністю тоді і тільки тоді, коли (R ° R^{- 1}) È i_M = R.

45. Довести, що рефлексивне відношення R на множині M є еквівалентністю тоді і тільки тоді, коли з того, що xRy і xRz завжди випливає yRz, x, y, z Î M.

46. Довести, що для довільного відношення еквівалентності R виконується:

(а) x Î[ x ] _R;

(б) (x, y)Î R Û [ x ] _R = [ y ] _R ;

(в) або[ x ] _R = [ y ] _R , або[ x ] _R Ç [ y ] _R =Æ.

47. Довести, що для довільного відношення еквівалентності R наведені твердження є рівносильними

(а) (x, y)Î R; (б) [ x ] _R Ç[ y ] _R ¹ Æ; (в) [ x ] _R =[ y ] _R.

48. Нехай f: A ® B - довільне відображення. Покладемо R ={(x, y) | f (x)= f (y)}. Довести, що R є еквівалентністю на множині A і для відображення f існує розклад f = e ° f ₁, де e - природне відображення множини A на A / R, а f ₁ - взаємно однозначна відповідність між A / R і f (A) (правило розкладу або факторизації відображення).

49. Нехай C - деяка відповідність між A і B. Означимо відношення R_C на множині A таким чином: для x, y ÎPr₁ C вважаємо (x, y)Î R_C тоді і тільки тоді, коли C (x)Ç C (y)¹Æ.

Довести, що

(а) відношення R_C симетричне;

(б) відношення R_C рефлексивне тоді і тільки тоді, коли відповідність C всюди визначена;

(в) коли для деякого x Î A виконується (x, x)Ï R_C, то (x, y)Ï R_C для всіх y Î A;

(г) коли відповідність C є відображенням, то відношення R_C транзитивне;

(д) коли відповідність C є відображенням, то R_C - еквівалентність на A.

50. Для відповідності C між A і B через Q_C позначимо відношення на множині A, яке означається таким чином: для x, y ÎPr₁ C вважаємо (x, y)Î Q_C тоді і тільки тоді, коли | C (x)Ç C (y)| = 1.

Довести, що для довільного антирефлексивного й симетричного відношення R на множині A існує така відповідність C між A і деякою множиною B, що R = Q_C.

51. Нехай R ₁ і R ₂ - еквівалентності на множині A. Довести, що

(а) R ₁° R ₁= A ² Û R ₁= A ²; (б) R ₁° R ₂= A ² Û R ₂° R ₁= A ².

52. Довести, що множини

(а) { A, }; (б) { A Ç B, A \ B, B \ A, Ç }; (в) { A D B, A Ç B, }

є розбиттями універсальної множини E для довільних множин A, B Í E.

53. Побудувати всі можливі розбиття множини

(а) A = { a, b, c }; (б) A = {Æ,{Æ}}.

Відношення порядку

 

1. Довести, що множина всіх підмножин (булеан) даної множини є частково впорядкованою за відношенням включення Í.

2. Довести, що i_A є частковий порядок на A.

3. Нехай a £ b Û a, b Î N і a ділить b. Довести, що £ - частковий порядок на N.

4. Означимо відношення R на множині цілих чисел Z таким чином: mRn тоді і тільки тоді, коли m - n є невід’ємним парним числом. Довести, що R - частковий порядок на Z. Чи є R лінійним порядком?

5. Означимо на множині R дійсних чисел відношення T: aTb тоді і тільки тоді, коли a /(a ²+1) £ b /(b ²+1), a,b Î R. Довести, що

(а) T не є відношенням часткового порядку на всій множині R;

(б) T є відношенням часткового порядку на множині дійсних чисел з інтервалу [1;¥);

(в) T є відношенням часткового порядку на множині дійсних чисел з інтервалу (-¥;-1].

6. Побудувати всі відношення часткового порядку на множині

(а) M = { a, b }; (б) M = { a, b, c }; (в) M = { a, b, c, d }.

7. Нехай M - скінченна множина і частковим порядком R на множині b(M) є відношення включення Í. Визначити величину | R | для заданої множини M.

(а) M ={1,2}; (б) M ={1,2,3}; (в) M ={1,2,3,4}; (г) M ={1,2,..., n }.

8. Нехай M ={1,2,3,4}. На множині b(M) задамо відношення R таким чином: (A, B)Î R тоді і тільки тоді, коли жодна з множин A і B не є підмножиною іншої. З’ясувати, чи є відношення R частковим порядком. Визначити величину | R |.

9. Довести, що якщо для елементів частково впорядкованої множини M виконується x ₁£ x ₂£...£ x_n £ x ₁, то x ₁= x ₂=...= x_n.

10. Нехай M - довільна множина. Означимо відношення R на множині b (M)´ b (M): (A, B) R (C, D) тоді і тільки тоді, коли A D B Í C D D, A, B, C, D Î b (M). Чи є відношення R відношенням часткового порядку?

11. Нехай £ _A частковий порядок на множині A, £ _B - частковий порядок на множині B. Назвемо прямим добутком частково впорядкованих множин A і B множину A ´ B із заданим на ній відношенням £: (a ₁ ,b ₁)£(a ₂ ,b ₂) Û a ₁£ _Aa ₂ і b ₁£ _Bb ₂. Довести, що £ є частковим порядком на A ´ B;

12. Довести або спростувати таке твердження: якщо £ _A лінійний порядок на множині A, а £ _B - лінійний порядок на множині B, то відношення £, означене в попередній задачі, є лінійним порядком на множині A ´ B.

13. Довести, що для ланцюгів A і B прямий добуток A ´ B є ланцюгом лише тоді, коли або½ A ½= 1, або½ B ½=1.

14. Задамо відношення Q на множині Rⁿ кортежів дійсних чисел довжини n таким чином: (a ₁, a ₂,..., a_n) Q (b ₁, b ₂,..., b_n) тоді і тільки тоді, коли a ₁£ b ₁, a ₂£ b ₂,..., a_n £ b_n. Довести, що Q є частковим порядком на Rⁿ.

15. Нехай M - довільна множина. Означимо відношення R на множині b (M)´ b (M): (A, B) R (C, D) тоді і тільки тоді, коли A Í C і B Í D, A, B, C, D Î b (M). Визначити, чи є відношення R

(а) відношенням часткового порядку?

(б) відношенням лінійного порядку?

16. Нехай M - непорожня множина і P - множина всіх часткових порядків на M. Для R ₁, R ₂Î P покладемо R ₁£ R ₂ тоді і тільки тоді, коли з (a, b)Î R ₁ випливає (a, b)Î R ₂ для a, b Î M.

Довести, що означене відношення £ є частковим порядком на P.

17. Означимо відношення R на множині N ²: (a, b) R (c, d) тоді і тільки тоді, коли a £ c і b ³ d. Чи є відношення R відношенням часткового порядку?

18. На множині всіх підмножин (булеані) b (M) деякої множини M означимо відношення R: (A, B)Î R тоді і тільки тоді, коли існує бієкція між множинами A і B, A, B Î b (M). Чи буде відношення R відношенням часткового порядку на b (M)?

19. Означимо відношення R на множині N ² : (a, b) R (c, d) тоді і тільки тоді, коли числа a і b та c і d є попарно взаємно простими і виконується a×d £ b×c. Довести, що відношення R є відношенням лінійного порядку на N ².

20. Розташувати у лексикографічному порядку елементи множини:

(а) B ³, де B ={0,1}; (б) A ³, де A ={ a, b, c }.

21. Довести, що лексикографічний порядок є лінійним порядком на множині A * всіх слів в алфавіті A.

22. Підмножина B лінійно впорядкованої множини A з відношенням порядку £ називається щільною в A, якщо для будь-яких a, b Î A існує елемент c Î B такий, що a £ c £ b або b £ c £ a.

Чи є щільними у множині дійсних чисел R

(а) множина натуральних чисел N;

(б) множина цілих чисел Z;

(в) множина раціональних чисел Q;

(г) множина алгебраїчних чисел?

23. Довести, що R - частковий порядок тоді і тільки тоді, коли R^{- 1} частковий порядок.

24. Нехай { R_i } _{i Î I} - система часткових порядків на множині A. Довести, що R_i - частковий порядок на множині A.

25. Нехай R - транзитивне відношення на множині M. Довести, що R є частковим порядком на M тоді і тільки тоді, коли R Ç R^{- 1} = i_M.

26. Нехай R ₁ і R ₂ - часткові порядки на множині A. Чи буде частковим порядком R ₁È R ₂?

27. Нехай R ₁ і R ₂ - часткові порядки на множині A. Чи буде частковим порядком R ₁° R ₂?

28. Нехай R ₁ і R ₂ - лінійні порядки на множині A. Коли R ₁° R ₂ буде лінійним порядком на множині A?

29. Довести, що композиція R ₁° R ₂ відношень строгого порядку R ₁ і R ₂ буде строгим порядком, коли R ₁° R ₂ = R ₂° R ₁ і R ₁Ç R ₂ ^{- 1} = Æ.

30. Нехай R - частковий (лінійний, повний) порядок на множині A, B - довільна підмножина множини A і R ₁ - довільна підмножина R. Чи буде відношенням часткового (лінійного, повного) порядку

(а) R на множині B; (б) R ₁ на множині A; (в) R ₁ на множині B?

31. Нехай R - частковий (лінійний, повний) порядок на множині A і B Í A (B ¹Æ). Довести, що R Ç B ² є частковий (лінійний, повний) порядок на множині B.

32. Нехай R - частковий порядок на множині A, який не є лінійним порядком, і B - непорожня підмножина множини A. Чи правильним є твердження, що відношення R Ç B ² є частковим порядком на множині B, який не є лінійним?

33. Довести, що відношення часткового порядку R на множині M буде лінійним порядком тоді і тільки тоді, коли R È R ^-1 = M ².

34. Довести, що об’єднання R ₁È R ₂ відношень часткового порядку R ₁ і R ₂ на множині M буде частковим порядком на множині M тоді і тільки тоді, коли R ₁° R ₂È R ₂° R ₁ Í R ₁È R ₂ і R ₁Ç R ₂^-1 = i_M.

35. Нехай R ₁ - відношення еквівалентність, R ₂ відношення строгого порядку. Довести, що відношення R ₁° R ₂° R ₁ буде строгим порядком тоді і тільки тоді, коли R ₂° R ₁° R ₂Í R ₁° R ₂° R ₁ і R ₁Ç R ₂ = Æ.

36. Довести, що об’єднання R ₁È R ₂ відношень строгого порядку R ₁ і R ₂ буде строгим порядком тоді і тільки тоді, коли R ₁° R ₂È R ₂° R ₁Í R ₁È R ₂.

37. Довести, що відношення R на множині A є одночасно відношенням еквівалентності та частковим порядком тоді і тільки тоді, коли R = i_A.

38. Нехай £ - частковий порядок на множині A. Означимо відношення < на частково впорядкованій множині A: a < b тоді і тільки тоді, коли a £ b і a ¹ b. Довести, що відношення < іррефлексивне та транзитивне.

39. Довести, що коли деяке відношення < на A іррефлексивне та транзитивне, тоді відношення x £ y Û (x < y або x = y) є частковим порядком на A.

40. Довести, що для довільної частково впорядкованої множини M з k елементів існує таке відображення f: M ® N_k, що для елементів a_i, a_j Î M зі співвідношення a_i < a_j випливає нерівність f (a_i)< f (a_j).

41. Довести, що транзитивне замикання R ^* відношення часткового порядку R збігається з R, тобто R ^* = R.

42. Довести, що транзитивне замикання R * рефлексивного відношення R на множині M буде відношенням часткового порядку на M тоді і тільки тоді, коли R * антисиметричне. Сформулюйте цю умову в термінах відношення R.

43. Нехай £ і < - це традиційні відношення порядку на множині натуральних чисел N. Довести, що

(а) < ° < ¹ <; (б) £ ° < = <; (в) £ ° ³ = N ².

44. На множині N ₂₀₀₀ означено частковий порядок R за допомогою відношення «ділить», тобто mRn тоді і тільки тоді, коли m ділить n. Чи існують у множині N ₂₀₀₀ найменший і найбільший елементи? Чи є в множині N ₂₀₀₀ мінімальні й максимальні елементи, і якщо є, то визначити їхню кількість. Узагальнити відповідь на випадок множини N_k для довільного k Î N.

45. Визначити для скількох відношень часткового порядку на множині M елемент a буде мінімальним.

(а) M ={ a, b }; (б) M ={ a, b, c }; (в) M ={ a, b, c, d }.

46. Довести, що будь-яка частково впорядкована множина містить не більше одного найбільшого (найменшого) елемента.

47. Довести, що найбільший (найменший) елемент частково впорядкованої множини є єдиним максимальним (мінімальним) елементом у цій множині.

48. Побудувати приклад частково впорядкованої множини, яка має

(а) точно один мінімальний елемент, але не має найменшого елемента;

(б) точно один максимальний елемент, але не має найбільшого елемента;

(в) один мінімальний і один максимальний елементи, але не має найменшого й найбільшого елементів;

(г) не має жодного мінімального і максимального елементів та не має найменшого й найбільшого елементів.

49. Довести, що будь-яка непорожня скінченна частково впорядкована множина A містить мінімальний і максимальний елементи.

50. Довести, що скінченна частково впорядкована множина має найменший (найбільший) елемент тоді і тільки тоді, коли вона містить рівно один мінімальний (максимальний) елемент. Чи справедливо це для нескінченних частково впорядкованих множин?

51. Нехай частково впорядкована множина A є скінченною. Довести, що для будь-якого елемента a Î A існують елементи b і c з A такі, що

(а) a £ b і b є максимальним елементом у множині A;

(б) c £ a і c є мінімальним елементом у множині A.

52. Скільки одиничок містить матриця C відношення лінійного порядку R на скінченній множині M з n елементів?

53. Нехай C - матриця відношення часткового порядку R на скінченній множині M з n елементів. Як за допомогою матриці C можна визначити існування в множині M

(а) мінімальних елементів; (в) найменшого елемента;

(б) максимальних елементів; (г) найбільшого елемента.

55. Побудувати лінійний порядок на множині:

(а) N ²; (б) N È N ²È N ³È...È Nⁿ È...; (в) C комплексних чисел.

56. Довести, що множина N натуральних чисел з традиційним відношенням порядку є цілком упорядкованою.

57. Довести, що

(а) множина N, де 0<2<4<...<1<3<5... є цілком упорядкованою;

(б) множина N, де...4<3<2<1 не є цілком упорядкованою.

(в) множина Z, де 1<2<3<...<0<-1<-2<-3<... є цілком упорядкованою.

58. Довести, що множина Z цілих чисел з традиційним відношенням порядку не є цілком упорядкованою.

59. Довести, що будь-яка скінченна лінійно впорядкована множина є цілком упорядкованою.

60. Чи будуть цілком упорядкованими такі множини:

(а) множина Q раціональних чисел з традиційним відношенням порядку;

(б) множина R дійсних чисел з традиційним відношенням порядку;

(в) множина чисел виду 1-1/ n, де n Î N з традиційним відношенням порядку.

61. Довести, що будь-яка підмножина цілком упорядкованої множини є цілком упорядкованою.

62. Знайти всі множини M, для яких існує повний порядок R на M такий, що R ^-1 також є повним порядком на M.

63. Довести, що будь-яка непорожня цілком упорядкована множина має найменший елемент.