Відношення еквівалентності. 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 = 2k для деякого цілого 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. Довести, що відношення рівності iM на будь-якій множині M є відношенням еквівалентності.
9. Довести, що для довільного відношення еквівалентності R на множині M виконується iMÍR. Таким чином, iM є найменшим відношенням еквівалентності на множині M.
10. Довести, що відношення рівнопотужності множин є еквівалентністю.
11. Довести, що еквівалентністю є відношення подібності на множині всіх трикутників.
13. Довести, що R є відношенням еквівалентності тоді і тільки тоді, коли R-1 є відношенням еквівалентності.
14. Довести, що перетин будь-якої сукупності відношень еквівалентності на множині M є еквівалентністю на M.
15. Навести приклад двох еквівалентностей R1 і R2 на множині M={1,2,3,4}таких, що R1ÈR2 не є еквівалентністю на множині M.
16. Довести, що об’єднання R1ÈR2 двох еквівалентностей R1 і R2 є еквівалентністю тоді і тільки тоді, коли R1ÈR2=R1°R2.
17. Довести, що для довільного відношення еквівалентності R виконується R°R=R.
18. Навести приклад двох еквівалентностей R1 і R2 на множині M={1,2,3,4}таких, що R1°R2 не є еквівалентністю на M.
19. Довести, що композиція R1°R2 двох еквівалентностей R1 і R2 є еквівалентністю, якщо R1°R2 = R1ÈR2.
20. Довести, що композиція R1°R2 двох еквівалентностей R1 і R2 є еквівалентністю тоді і тільки тоді, коли
(а) R1°R2 = R2°R1 ; (в) R2°R1 Í R1°R2 ;
(б) R1°R2 - симетричне відношення; (г) R1°R2 = R1°R2 È R2°R1.
21. Довести, що коли R1 і R2 - еквівалентності, то відношення (R1ÈR2)* також буде еквівалентністю.
22. Довести, що коли R1 і R2 - еквівалентності, то відношення (R1°R2ÈR2°R1)* також буде еквівалентністю.
23. Довести, що коли R1 і R2 - еквівалентності, то (R1ÈR2)* = (R1°R2ÈR2°R1)*.
24. Довести, що коли R1 і R2 - еквівалентності і R1°R2 = R2°R1, то R1°R2 = (R1ÈR2)*.
25. Нехай R1 і R2 - еквівалентності і R1°R2=R2°R1. Довести, що R1°R2 є найменшим відношенням еквівалентності, яке містить R1ÈR2.
26. Нехай R1 і R2 - еквівалентності. Довести, що найменшим відношенням еквівалентності, яке містить R1ÈR2, є (R1ÈR2)*.
27. Нехай R1 і R2 - еквівалентності. Довести, що найменшим відношенням еквівалентності, яке містить R1ÈR2, є (R1°R2ÈR2°R1)*.
28. Довести, що для довільної сукупності відношень еквівалентності {Ri}, iÎI існує еквівалентність Q така, що 
RiÍQ і для будь-якого відношення еквівалентності R з включення RiÍR випливає QÍR (тобто Q є найменшим відношенням еквівалентності, яке містить 
Ri)
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. Довести, що для довільної сукупності еквівалентностей {Ri}, iÎI найменшою еквівалентністю Q, яка містить 
Ri, є відношення ( 
Ri)*.
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ÈiMÈR-1)*.
33. Знайти відношення R на множині M = {1,2,3,4}, яке містить мінімально можливу кількість елементів і таке, що найменшим відношенням еквівалентності Q, що включає R, є повне відношення на M, тобто Q = M´M.
34. Побудувати на множині M = {a1,a2,...,an} відношення R з мінімально можливою кількістю елементів таке, що найменше відношення еквівалентності Q, що містить R, збігається з повним відношенням на M, тобто Q = M´M.
35. Визначити мінімально можливу кількість елементів у відношенні R на множині M = {a1,a2,...,an}, для якого найменшим відношенням еквівалентності 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. Нехай R1 - толерантне відношення, R2 - еквівалентність і R1ÍR2. Довести, що R1*ÍR2.
40. Довести, що найменшим відношенням еквівалентності Q, яке містить толерантне відношення R, є R*.
41. Нехай R1 і R2 - відношення еквівалентності на множині M. Довести, що відношення R1°R2°R1 буде еквівалентністю тоді і тільки тоді, коли
(а) R2°R1°R2ÍR1°R2°R1; (б) R1°R2°R1 = R1°R2ÈR2°R1.
41. Нехай R транзитивне й симетричне відношення на множині M і Pr1RÈPr2R=M. Довести, що R є еквівалентністю на множині M.
43. Довести, що коли R рефлексивне й транзитивне відношення на множині M, тоді RÇR-1 є відношенням еквівалентності на множині M.
44. Нехай R є відношенням на M. Довести, що R є еквівалентністю тоді і тільки тоді, коли (R°R-1) È iM = 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 ° f1, де e - природне відображення множини A на A/R, а f1 - взаємно однозначна відповідність між A/R і f(A) (правило розкладу або факторизації відображення).
49. Нехай C - деяка відповідність між A і B. Означимо відношення RC на множині A таким чином: для x,yÎPr1C вважаємо (x,y)ÎRC тоді і тільки тоді, коли C(x)ÇC(y)¹Æ.
Довести, що
(а) відношення RC симетричне;
(б) відношення RC рефлексивне тоді і тільки тоді, коли відповідність C всюди визначена;
(в) коли для деякого xÎA виконується (x,x)ÏRC, то (x,y)ÏRC для всіх yÎA;
(г) коли відповідність C є відображенням, то відношення RC транзитивне;
(д) коли відповідність C є відображенням, то RC - еквівалентність на A.
50. Для відповідності C між A і B через QC позначимо відношення на множині A, яке означається таким чином: для x,yÎPr1C вважаємо (x,y)ÎQC тоді і тільки тоді, коли |C(x)ÇC(y)| = 1.
Довести, що для довільного антирефлексивного й симетричного відношення R на множині A існує така відповідність C між A і деякою множиною B, що R = QC.
51. Нехай R1 і R2 - еквівалентності на множині A. Довести, що
(а) R1°R1=A2 Û R1=A2; (б) R1°R2=A2 Û R2°R1=A2.
52.Довести, що множини
(а) {A, 
}; (б) {AÇB, A\B, B\A, Ç 
}; (в) {ADB, AÇB, 
}
є розбиттями універсальної множини E для довільних множин A,BÍE.
53. Побудувати всі можливі розбиття множини
(а) A = {a,b,c}; (б) A = {Æ,{Æ}}.
Відношення порядку
1.Довести, що множина всіх підмножин (булеан) даної множини є частково впорядкованою за відношенням включення Í.
2. Довести, що iA є частковий порядок на A.
3.Нехай a£b Û a,bÎN і a ділить b. Довести, що £ - частковий порядок на N.
4. Означимо відношення R на множині цілих чисел Z таким чином: mRn тоді і тільки тоді, коли m-n є невід’ємним парним числом. Довести, що R - частковий порядок на Z. Чи є R лінійним порядком?
5. Означимо на множині R дійсних чисел відношення T: aTb тоді і тільки тоді, коли a/(a2+1) £ b/(b2+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 виконується x1£x2£...£xn£x1, то x1=x2=...=xn.
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 із заданим на ній відношенням £: (a1,b1)£(a2,b2) Û a1£Aa2 і b1£Bb2. Довести, що £ є частковим порядком на A´B;
12. Довести або спростувати таке твердження: якщо £ A лінійний порядок на множині A, а £ B - лінійний порядок на множині B, то відношення £ , означене в попередній задачі, є лінійним порядком на множині A´B.
13. Довести, що для ланцюгів A і B прямий добуток A´B є ланцюгом лише тоді, коли або½A½= 1, або½B½=1.
14. Задамо відношення Q на множині Rn кортежів дійсних чисел довжини n таким чином: (a1,a2,...,an)Q(b1,b2,...,bn) тоді і тільки тоді, коли a1£b1,a2£b2,...,an£bn. Довести, що Q є частковим порядком на Rn.
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. Для R1,R2ÎP покладемо R1£R2 тоді і тільки тоді, коли з (a,b)ÎR1 випливає (a,b)ÎR2 для a,bÎM.
Довести, що означене відношення £ є частковим порядком на P.
17. Означимо відношення R на множині N 2: (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 2 : (a,b)R(c,d) тоді і тільки тоді, коли числа a і b та c і d є попарно взаємно простими і виконується a×d£b×c. Довести, що відношення R є відношенням лінійного порядку на N 2.
20. Розташувати у лексикографічному порядку елементи множини:
(а) B3, де B={0,1}; (б) A3, де 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.Нехай {Ri}iÎI - система часткових порядків на множині A. Довести, що 
Ri - частковий порядок на множині A.
25. Нехай R - транзитивне відношення на множині M. Довести, що R є частковим порядком на M тоді і тільки тоді, коли RÇR-1 = iM.
26.Нехай R1 і R2 - часткові порядки на множині A. Чи буде частковим порядком R1ÈR2?
27.Нехай R1 і R2 - часткові порядки на множині A. Чи буде частковим порядком R1°R2?
28.Нехай R1 і R2 - лінійні порядки на множині A. Коли R1°R2 буде лінійним порядком на множині A?
29. Довести, що композиція R1°R2 відношень строгого порядку R1 і R2 буде строгим порядком, коли R1°R2 = R2°R1 і R1ÇR2-1 = Æ.
30. Нехай R - частковий (лінійний, повний) порядок на множині A, B - довільна підмножина множини A і R1 - довільна підмножина R. Чи буде відношенням часткового (лінійного, повного) порядку
(а) R на множині B; (б) R1 на множині A; (в) R1 на множині B?
31.Нехай R - частковий (лінійний, повний) порядок на множині A і BÍA (B¹Æ). Довести, що RÇB2 є частковий (лінійний, повний) порядок на множині B.
32. Нехай R - частковий порядок на множині A, який не є лінійним порядком, і B - непорожня підмножина множини A. Чи правильним є твердження, що відношення RÇB2 є частковим порядком на множині B, який не є лінійним?
33. Довести, що відношення часткового порядку R на множині M буде лінійним порядком тоді і тільки тоді, коли RÈR-1 = M2.
34. Довести, що об’єднання R1ÈR2 відношень часткового порядку R1 і R2 на множині M буде частковим порядком на множині M тоді і тільки тоді, коли R1°R2ÈR2°R1 Í R1ÈR2 і R1ÇR2-1 = iM.
35. Нехай R1 - відношення еквівалентність, R2 відношення строгого порядку. Довести, що відношення R1°R2°R1 буде строгим порядком тоді і тільки тоді, коли R2°R1°R2ÍR1°R2°R1 і R1ÇR2 = Æ.
36. Довести, що об’єднання R1ÈR2 відношень строгого порядку R1 і R2 буде строгим порядком тоді і тільки тоді, коли R1°R2ÈR2°R1ÍR1ÈR2.
37. Довести, що відношення R на множині A є одночасно відношенням еквівалентності та частковим порядком тоді і тільки тоді, коли R=iA.
38. Нехай £ - частковий порядок на множині A. Означимо відношення < на частково впорядкованій множині A: a<b тоді і тільки тоді, коли a£b і a¹b. Довести, що відношення < іррефлексивне та транзитивне.
39. Довести, що коли деяке відношення < на A іррефлексивне та транзитивне, тоді відношення x£y Û (x<y або x=y) є частковим порядком на A.
40. Довести, що для довільної частково впорядкованої множини M з k елементів існує таке відображення f : M®Nk, що для елементів ai,ajÎM зі співвідношення ai<aj випливає нерівність f(ai)<f(aj).
41. Довести, що транзитивне замикання R* відношення часткового порядку R збігається з R, тобто R* = R.
42.Довести, що транзитивне замикання R* рефлексивного відношення R на множині M буде відношенням часткового порядку на M тоді і тільки тоді, коли R* антисиметричне. Сформулюйте цю умову в термінах відношення R.
43. Нехай £ і < - це традиційні відношення порядку на множині натуральних чисел N. Довести, що
(а) < ° < ¹ <; (б) £ ° < = <; (в) £ ° ³ = N2.
44. На множині N2000 означено частковий порядок R за допомогою відношення «ділить», тобто mRn тоді і тільки тоді, коли m ділить n. Чи існують у множині N2000 найменший і найбільший елементи? Чи є в множині N2000 мінімальні й максимальні елементи, і якщо є, то визначити їхню кількість. Узагальнити відповідь на випадок множини Nk для довільного 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. Побудувати лінійний порядок на множині:
(а) N2; (б) NÈN2ÈN3È...ÈNnÈ...; (в) 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. Довести, що будь-яка непорожня цілком упорядкована множина має найменший елемент.