Відношення еквівалентності. 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, Ç }; (в) {ADB, 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) тоді і тільки тоді, коли ADBÍCDD, 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. Довести, що будь-яка непорожня цілком упорядкована множина має найменший елемент.