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

 

Рефлексивне, симетричне та транзитивне відношення на множині А називається відношенням еквівалентності на А.

Прикладом відношення еквівалентності на множині А ={ a, b, c, d } є відношення R = i_A È{< a, d >,< d, a >,< c, b >,< b, c >}. Відношення R ={< x, y >| x та y – особи одного року народження} на множині людей є відношенням еквівалентності, оскільки R рефлексивне (адже твердження «х та х – особи одного року народження» істинне для будь-якого х з множини людей, отже, R містить усі діагональні пари), симетричне (якщо < x, y >Î R, то це означає, що х та у – особи одного року народження, але тоді у та х – особи одного року народження, звідки < y, x >Î R), транзитивне (якщо < x, y >Î R та < y, z >Î R, тобто х та у – особи одного року народження й у та z – особи одного року народження, то й х та z – особи одного року народження, отже, < x, z >Î R). Відношення і_А (тобто відношення тотожності на А) на довільній множині А є відношенням еквівалентності, оскільки і_А Í і_А (і_А рефлексивне), < x, y >Î і_А Þ x = y Þ < y, x >Î і_А (і_А симетричне), < x, y >Î і_А, < y, z >Î і_А Þ x = y = z Þ < x, z >Î і_А (і_А транзитивне). Відношення R ={<1,1>,<2,1>,<1,2>} на множині {1,2} не є відношенням еквівалентності, оскільки воно не рефлексивне (<2,2>Ï R) (а також не транзитивне). Відношення {< x, y >| x не вищий на зріст за y } на множині людей не є відношенням еквівалентності, тому що воно не симетричне.

Теорема 7. Бінарне відношення R на множині А є відношенням еквівалентності тоді й тільки тоді, коли існує розбиття Р множини А таке, що R ={< x, y >| x, y Î C для деякої множини С з Р }.

Доведення. Нехай Р – розбиття множини А. Покажемо, що відношення R ={< x, y >| x, y Î C для деякої С з Р } є відношенням еквівалентності на А. Нехай х – довільний елемент множини А. Оскільки Р – розбиття А, то знайдеться така множина С з розбиття Р, що х Î С, але тоді, за визначенням відношення R, < x, x >Î R, отже, i_A Í R, тобто R рефлексивне. Нехай < x, y >Î R. Це означає, що x, y Î C для деякої С з Р, але тоді у, х Î C для деякої С з Р, тобто < y, x >Î R, отже, R симетричне. Нехай < x, y >Î R, < y, z >Î R. Це означає, що x, y Î C для деякої С з Р й у, z Î C ₁ для деякої С ₁ з Р, але оскільки Р – розбиття, то кожен елемент множини А належить лише одній множині з розбиття, тому y Î C, y Î C ₁ Þ C = C ₁, а тоді x Î C, z Î C, звідки < x, z >Î R, тобто R транзитивне. Отже, R – відношення еквівалентності на А.

Нехай тепер R – відношення еквівалентності на А. Покажемо, що існує таке розбиття Р множини А, що < x, y >Î R Û x, y Î C для деякої множини С з Р. Нехай х Î А. Розглянемо множину К (х)={ u | u Î A, < x, u >Î R }. Назвемо К (х) класом елементу х. Оскільки < x, x >Î R для кожного х з А, то х Î К (х), отже, К (х)¹Æ для кожного х з А. Таким чином, множина усіх класів елементів множини А утворює покриття множини А. Покажемо, що для будь-яких х та у з множини А або К (х)= К (у), або К (х)Ç К (у)=Æ. Для довільного елемента у множини А можуть бути два випадки: у Î К (х) або у Ï К (х). Покажемо, що у випадку у Î К (х) К (х)= К (у). Нехай а Î К (х). Тоді < x, а >Î R, але з визначення класу елемента х випливає, що < x, y >Î R. Оскільки R симетричне, то < у, х >Î R. З транзитивності R маємо < у, а >Î R, отже, а Î К (у), тобто К (х)Í К (у). Аналогічно доводиться, що К (у)Í К (х). Таким чином, якщо у Î К (х), то К (х)= К (у). Розглянемо випадок у Ï К (х). Припустимо, що К (х)Ç К (у)¹Æ. Тоді існує с Î К (х)Ç К (у), звідки с Î К (х) та с Î К (у), отже, < x, c >Î R та < y, c >Î R. Оскільки R симетричне та транзитивне, то < x, y >Î R, тобто у Î К (х), отже, маємо суперечність (ми розглядаємо випадок у Ï К (х)). Таким чином, якщо у Ï К (х), то К (х)Ç К (у)=Æ. Ми довели, що покриття множини А, котре утворюється усіма класами елементів цієї множини, складається з множин, кожні дві з яких або не перетинаються, або збігаються. Сукупність усіх попарно різних множин даного покриття утворює деяке розбиття Р множини А. За побудовою Р < x, y >Î R Û x, y Î C для деякої множини С з Р.

Розглянемо приклади побудови розбиття множини за визначеним на ній відношенням еквівалентності. Нехай на множині А ={ a, b, c, d, e } задано відношення еквівалентності R = i_A È{< a, c >,< c, a >,< d, e >,< e, d >}. Визначимо для кожного елемента х множини А клас К (х) цього елемента. Маємо: К (а)={ a, c }, K (b)={ b }, K (c)={ c, a }, K (d)={ d, e }, K (e)={ e, d }. Виберемо з побудованої сукупності класів ті, які є попарно різними. Маємо:

Р ={{ a, c }, { b }, { d, e }}. Це й є шукане розбиття.

Нехай на множині N задано відношення R таке, що xRy Û х та у – числа однакової парності (тобто х та у обидва парні або х та у обидва непарні). R є відношенням еквівалентності, оскільки для кожного х Î N х та х – числа однакової парності, отже, і_А Í R, тобто R рефлексивне. Якщо х та у – числа однакової парності, то у та х теж числа однакової парності, тобто R симетричне. Якщо х та у – числа однакової парності й у та z – числа однакової парності, то, зрозуміло, х та z також є числа однакової парності, тобто R транзитивне. Таким чином, R є відношенням еквівалентності на N, отже, визначає на N деяке розбиття Р. Кожен елемент множини N належить лише одному класу розбиття. Позначимо Р ₀ – клас розбиття, який містить число 0. Цьому класу будуть також належати ті числа з N, котрі мають ту ж саму парність, що й число 0, тобто усі додатні парні числа. Таким чином, Р ₀={2 k | k Î N }. Число 1 не входить у Р ₀, отже, у Р існує клас розбиття (позначимо його Р ₁), що містить число 1. Цей клас містить також усі числа, що мають ту саму парність, що й число 1, тобто усі додатні непарні числа. Отже, Р ₁={2 k +1| k Î N }. Таким чином, Р ={ P ₁, P ₂} – шукане розбиття, оскільки P ₁È P ₂= N, P ₁Ç P ₂=Æ й < х, у >Î R Û x, y належать одному й тому самому класу розбиття (тобто або х, у Î P ₁, або х, у Î Р ₂).

 

Фактор-множина

 

Нехай R – відношення еквівалентності на А. Тоді, як відомо, існує розбиття множини А, яке визначається відношенням R. Позначимо це розбиття через А / R й називатимемо його фактор-множиною множини А по відношенню R, а множини, що складають дане розбиття – класами еквівалентності. Клас розбиття будемо іноді позначати через [ x ], де х – деякий елемент даного класу розбиття. Наприклад, якщо А / R ={{ a, c }, { b }, { d, e }}, то клас розбиття { a, c } можна позначити [ а ] або [ с ], а клас розбиття { d, e } – [ d ] або [ е ]. Якщо множина класів еквівалентності (тобто А / R) скінченна, то кількість класів еквівалентності називається індексом множини А, а множина А з відношенням еквівалентності R називається множиною скінченного індексу.

Наприклад, множина N з відношенням еквівалентності R, заданим умовою xRy Û х та у – числа однакової парності, є множиною індексу 2. Якщо на N задано відношення тотожності і _N, то N / і _N = {{ n }| n Î N }, тобто N / і _N не є скінченною множиною, отже, N з відношенням і _N не є множиною скінченного індексу.

 

Замикання відношень

 

Рефлексивним замиканням бінарного відношення R, заданого на множині А (позначається R_r), називається відношення R_r = i_A È R.

Симетричним замиканням бінарного відношення R, заданого на множині А (позначається R_s), називається відношення R_s = R È R ^-1.

Нехай, наприклад, на множині А ={1,2,3,4} задано відношення R ={<2,3>,<3,3>, <2,1>,<1,3>}. Рефлексивним замиканням R є відношення R_r ={<1,1>,<2,2>,<3,3>, <4,4>,<2,3>,<2,1>,<1,3>}, симетричним замиканням R є відношення R_s ={<2,3>, <3,3>,<2,1>,<1,3>,<3,2>,<1,2>, <3,1>}.

Транзитивним замиканням бінарного відношення R, заданого на множині А (позначається R_t або TC (R)), називається відношення R_t = R È R ²È…È Rⁿ È…, де Rⁿ = R, якщо n =1, Rⁿ = R^n-1 * R, якщо n >1.

Для обчислення транзитивного замикання деякого відношення зручно використовувати таку властивість. Нехай R – бінарне відношення на множині А. Якщо для деякого n (n ³1) R È…È Rⁿ = R È…È Rⁿ È Rⁿ⁺¹, то R_t = R È…È Rⁿ. Для обгрунтування цього твердження достатньо показати, що для усіх k > n +1 R È…È Rⁿ = R È…È R^k за умови R È…È Rⁿ = R È…È Rⁿ È Rⁿ⁺¹. Очевидно, що R È…È Rⁿ Í R È…È R^k. Покажемо, що R È…È R^k Í R È…È Rⁿ. Дійсно, < x, y >Î R È…È R^k Þ існує число і (1£ і £ k) таке, що < x, y >Î Rⁱ. Якщо і £ n +1, то < x, y >Î R È…È Rⁿ. Нехай і > n +1, тоді маємо: < x, y >Î Rⁱ Þ < x, y >Î Rⁿ * R^i-n Þ < x, y >Î Rⁿ⁺¹ * R^i-n-1 Þ існує z Î А такий, що < x, z >Î Rⁿ⁺¹ та < z, y >Î R^{i-n -1} Þ < x, z >Î R È…È Rⁿ, < z, y >Î R^{i-n -1} Þ існує число j < n +1 таке, що < x, z >Î R^j Þ < x, y >Î R^{j+i-n -1}. Якщо j + i - n -1£ n +1, то включення доведено, інакше покладемо і ₁= j + i - n -1. Очевидно, що і ₁< і. Таким чином, можна побудувати скінченну послідовність чисел і, і₁,…, і_l, де і_l – перше з чисел у послідовності, для якого i_l < n +1, < x, y >Î R^m, m Î{ і, і₁,…, і_l }. Отже, < x, y >Î R È…È Rⁿ.

Обчислимо транзитивне замикання R_t відношення R ={<2,3>,<3,3>, <2,1>,<1,3>,<3,4>}, заданого на множині А ={1,2,3,4}. Маємо: R ²={<2,3>,<2,4>, <3,3>,<3,4>,<1,3>,<1,4>}. R È R ²={<2,3>,<3,3>,<2,1>,<1,3>,<3,4>,<2,4>, <1,4>} ¹ R, отже, обчислюємо R ³= R ²* R. Маємо: R³={<2,3>,<2,4>,<3,3>,<3,4>,<1,3>, <1,4>}. Оскільки

R È R ²È R ³={<2,3>,<3,3>,<2,1>,<1,3>,<3,4>,<2,4>,<1,4>}= R È R ²,

то R_t = R È R ².

З визначення транзитивного замикання відношення випливає, що для будь-якого бінарного відношення R на А xR_ty Û існує така скінченна послідовність x ₁,…, x_n елементів множини А, що x ₁= x, x_n = y, x_iRx_i+1, i Î{1,…, n -1}.

Рефлексивно-симетрично-транзитивним замиканням відношення R, заданого на множині А, назвемо відношення R_rst =ТС(і_А È R È R ^-1).

Теорема 8. Нехай R – деяке бінарне відношення на множині А, R_е – будь-яке відношення еквівалентності на А таке, що R Í R_е, R_rst – рефлексивно-симетрично-транзитивне замикання відношення R. Тоді R_rst Í R_е.

Доведення. Нехай < x, y >Î R_rst. Тоді < x, y >Î R або < x, y >Ï R. Якщо < x, y >Î R, то, оскільки R Í R_е, < x, y >Î R_е. Якщо < x, y >Ï R, то для деякого і ³1 < x, y >Î(і_А È R È R ^-1) ⁱ. Нехай i =1. Тоді < x, y >Î і_А або < x, y >Î R ^-1. Якщо < x, y >Î і_А, то < x, y >Î R_е, оскільки R_е рефлексивне. Якщо < x, y >Î R ^-1, то маємо: < x, y >Î R ^-1 Þ < y, x >Î R Þ < y, x >Î R_е Þ < x, y >Î R_е. Нехай і >1 й < x, y >Î(і_А È R È R ^-1) ⁱ. Це означає, що існують такі елементи х ₁,…, х_{і +1} множини А, що х ₁= х, у = х_{і +1}, х ₁(і_А È R È R ^-1) х ₂,…, х_і (і_А È R È R ^-1) х_{і +1}, але тоді х ₁ R_eх ₂,…, х_іR_eх_{і +1}. Оскільки R_e транзитивне, то х ₁ R_eх_{і +1}, отже, хR_eу.

 

Задачі та вправи

 

І. Чи існують на множині {1,2,3,4} такі два різні відношення R та S, що: 1) R_r = S_r; 2) R_s = S_s; 3) R_t = S_t? Відповіді обгрунтувати.

ІІ. Побудувати декартів добуток множин

1) {1,2,Æ} та {2,4}, 2) { а, с, е }, { с, а },

3) {1},{2,3} та {1,2}, 4) { а,{ х }, х } та { і, с },

5) { х,Î, с } та { Х,Í, М }, 6) {3,+,5} та {2,´,4},

7) {12,34} та { ас, іе }, 8) {Ç,È} та {{ Х },{ А }},

9) { a, b, c }, Æ та {1,2}, 10) {2,3},{3,4} та {2,3},

11) {1,2}, {Æ} та {{Æ}}, 12) { x,{ x }}, {¹} та {{}}.

IІІ. Чи існують такі множини А, В, С, що А ´(В ´ С)≠(А ´ В)´ С?

ІV. Довести, що коли множини А, В, С, D непорожні, то:

1) А Í В й С Í D Û А ´ С Í В ´ D, 2) А = В й С = D Û А ´ С = В ´ D.

V. Довести, що:

1) (А Ç В)´(С Ç D)=(А ´ С)Ç(В ´ D),

2) (А ´ В)È(С ´ D)Í(А È С)´(В È D),

3) А ´(В È С)=(А ´ В)È(А ´ С),

4) (А È В)´(С È D)=(А ´ С)È(В ´ С)È(А ´ D)È(В ´ D),

5) (А \ В)´ С =(А ´ С)\(В ´ С),

6) А ´(В \ С)=(А ´ В)\(А ´ С),

7) А ´ В =(А ´ D)Ç(С ´ В), де А Í С, В Í D,

8) U ²\(А ´ В)=[(U \ A)´ U ]È[ U ´(U \ B)],

9) A ≠Æ, B ≠Æ, (A ´ B)È(B ´ A)= C ´ D Þ A = B = C = D.

VI. Навести приклад таких множин A, B, C, D, для яких (A È B)´(C È D)¹ ¹(A ´ C)È(B ´ D).

VII. Чи існують такі множини А, В, С, що А ´ В = А ´ В ´ С?

VIIІ. Побудувати приклади унарних, бінарних та тернарних відношень, заданих на множині {1,2,3,4,5,6}.

IX. Побудувати приклади унарних, бінарних та тернарних відношень, заданих на множині:

1) N, 2) Z, 3) Q,

4) R, 5) людей, 6) тварин,

7) птахів, 8) квітів, 9) країн світу,

10) учнів школи, 11) днів тижня, 12) видів спорту.

X. Нехай А ={1,2,3,4,5,6,7,8,9,10}, R Í А ². Записати відношення R у явному вигляді:

1) R ={< x, y >| x, y Î A, x – дільник y, х £5},

2) R ={< x, y >| x, y Î A, x < y, х £2},

3) R ={< x, y >| x, y Î A, x £ y +1, y >7},

4) R ={< x, y >| x, y Î A, x – y ділитьcя на 3},

5) R ={< x, y >| x, y Î A, x + y ділитьcя на 5},

6) R ={< x, y >| x, y Î A, x > y, x + y <6},

7) R ={< x, y >| x, y Î A, x парне, y непарне},

8) R={< x, y >| x, y Î A, x просте, y складене},

9) R={< x, y >| x, y Î A, x кратне 5, y <5},

10) R={< x, y >| x, y Î A, x, y не мають спільних дільників, відмінних від 1}.

XI. Нехай Х =P({а,б,в}). Знайти усі елементи відношень Í, Ì, Ê, É, Ë на Х.

XIІ. Нехай R, Q, Т Í A ², A ={1,2,3,4,5,6,7}, R ={<2,1>,<2,2>,<3,5>,<6,3>}, Q ={<1,3>,<1,5>,<4,3>,<5,7>,<2,4>}, T ={<4,5>,<1,6>,<5,5>,<4,1>, <5,7>}. Обчислити вирази:

1) (R * Q)Ç(Q * R), 2) (T È Q)¢* R ^-1, 3) (T \ Q ¢)* Q ^-1,

4) (Q Ç T ¢)\ R ¢, 5) T ^-1Ç((Q * R)* T), 6) (Q È(R ¢\ T)¢)* T,

7) (Q ¢\ R ¢)* Q, 8) (T ^-1È R)Ç Q ^-1, 9) T È(Q ¢* R),

10) (Q È R)¢* R, 11) (R ¢\ T ¢)¢Ç R ¢, 12) (Q È T)^-1*(T ¢\ R),

13) ((Q È T)^-1* T ¢)\ R, 14) (T * Q * R)¢, 15) (T * Q)* R ¢,

16) (Q ^-1)¢*(R Ç T ¢), 17) (T ^-1)¢*(Q * T), 18) (Q Ç R ¢)* T,

19) (R * R)ÇQ¢, 20) (Q ¢\ R)* T, 21) (Q È R)¢* T,

22) (R ¢\ Q)*(T * T), 23) (T * Q ^-1)\(R * R ^-1), 24) (Q * Q)*(T ^-1)¢,

25) R * R * R, 26) T * T * T, 27) Q * Q * Q,

28) R * Q * R, 29) T * Q * T, 30) Q * T * Q ¢.

XIII. Нехай на множині N задані бінарні відношення:

R ₁={< x, y >| x, y – парні числа},

R ₂={< x, y >| x парне, y непарне},

R ₃={< x, y >| x, y – непарні числа},

R ₄={< x, y >| x непарне, y парне}.

Обчислити: R_i ^-1, R_i * R_j, R_i ¢, R_i Ç R_j (i, j Î{1,2,3,4}).

XIV. Знайти R ^-1, R * R, R * R ^-1, R ^-1* R для відношень:

1) R Í N ², R ={< x, y >| x ділить y };

2) R Í N ², R ={< x, y >| y ділить x };

3) R Í R ², R ={< x, y >| x + y £0};

4) R Í R ², R ={< x, y >| 2 x ³3 y };

5) R Í[0,p]², R ={< x, y >| y ³cos x }.

XV. Нехай на множині людей задані відношення R ={< x, y >| x – брат y }, Q ={< x, y >| x – помічник y }. Опишіть відношення R È Q, R Ç Q, R \ Q.

XVI. Нехай відношення <, >, £, ³ визначені на множині N звичайним чином. Чи правильні рівності:

1) <*< = <, 2) £*£ = £, 3) £*< = <, 4) £*³ = N ²,

5) ³*£ = <, 6) ³*< = Æ, 7) <*> = N ², 8) >*£ = >?

XVII. Довести рівності 1-3, 5-9 теореми 5.

XVIII. Нехай R ₁, R ₂, Q – бінарні відношення, задані на множині А, R ₁Í R ₂. Довести, що:

1) Q * R ₁ Í Q * R ₂, 2) R ₁* Q Í R ₂* Q, 3) R ₁^-1 Í R ₂^-1.

XIX. Нехай R, R ₁, R ₂, R ₃ – бінарні відношення на множині А. Довести, що:

1) R ₁*(R ₂Ç R ₃)Í(R ₁* R ₂)Ç(R ₁* R ₃), 2) (R ₁Ç R ₂)* R ₃Í(R ₁* R ₃)Ç(R ₂* R ₃).

XX. Нехай R Í A ². Довести, що R = i_A Û R * R ₁= R ₁* R = R для довільного бінарного відношення R ₁ на множині А.

XXI. Для яких бінарних відношень R виконується R ^-1= R ¢?

XXIІ. Класифікувати відношення, задані на множині людей, тобто для кожного відношення визначити, є воно симетричним (антисиметричним, асиметрич-ним, рефлексивним, антирефлексивним, транзитивним) чи ні.

1) R ={< x, y >: x, y – підлітки, які мають спільні захоплення},

2) R ={< x, y >: x – сестра y },

3) R ={< x, y >: x, y – люди, які мають спільних знайомих},

4) R ={< x, y >: x, y – учні різних шкіл},

5) R ={< x, y >: x, y – уболівальники різних спортивних команд},

6) R ={< x, y >: x, y – діти, що мешкають в одному домі},

7) R ={< x, y >: x, y – люди, які працюють на одному підприємстві},

8) R ={< x, y >: x, y – люди, яким подобаються одні й ті ж страви},

9) R ={< x, y >: x – мати y },

10) R ={< x, y >: x, y – двоюрідні брати},

11) R ={< x, y >: x, y – клієнти одного банку}.

XXIІІ. Класифікувати відношення, задані на числових множинах.

1) R ={< x, y >: x - y – непарне число}, R Í Z ²,

2) R ={< x, y >: x + y £5}, R Í Z ²,

3) R ={< x, y >: x ²+ y ²=1}, R Í R ²,

4) R ={< x, y >: x - y >2}, R Í N ²,

5) R ={< x, y >: x, y – невід’ємні цілі числа, x - y >2}, R Í Z ²,

6) R ={< x, y >: x - y кратне 3}, R Í N ²,

7) R ={< x, y >: x, y – числа, які не мають спільних дільників (крім 1)}, R Í(N ⁺)²,

8) R ={< x, y >: x ´ y >3}, R Í N ²,

9) R ={< x, y >: x =3 y }, R Í(N ⁺)²,

10) R ={< x, y >: x = y ²}, R Í R ²,

11) R ={< x, y >: x, y – числа з однаковими чисельниками й різними знаменни-ками}, R Í Q ²,

12) R ={< x, y >: ½ x ½+ y =0}, R Í R ²,

13) R ={< x, y >: 5 x + y ділиться на 3}, R Í(N ⁺)²,

14) R ={< x, y >: ½ x - y ½<1}, R Í R ²,

15) R ={< x, y >: ½ x ½+ y ¹0}, R Í R ²,

16) R ={< x, y >: ½ x ½>½ y ½}, R Í R ²,

17) R ={< x, y >: x, y – цілі числа, 2 x + y – парне число}, R Í R ²,

18) R ={< x, y >: x, y – числа з однаковими цифрами у старшому розряді}, R Í(N ⁺)²,

19) R ={< x, y >: x = y ²-1}, R Í R ²,

20) R ={< x, y >: x + y +1 – парне число}, R Í(N ⁺)²,

21) R ={< x, y >: x, y – числа, які мають хоча б одну спільну цифру}, R Í(N ⁺)²,

22) R ={< x, y >: x / y ³3}, R Í(N ⁺)²,

23) R ={< x, y >: x, y – числа різної парності}, R Í(N ⁺)²,

24) R ={< x, y >: | х + y |>1}, R Í R ².

XXІV. Класифікувати відношення.

1) R ={<1, a >,< b,2>,<1, b >,<1,1>,< a,2>}, R задано на множині {1, a, b,2},

2) R ={<1,3>, <4,2>, <1,1>, <3,2>, <3,1>, <4,4>, <2,4>, <2,2>, <2,3>, <3,3>}, R задано на множині {1,2,3,4,5},

3) R ={< a, a >,< b, b >,< a, b >,< a, c >,< b, a >,< c, a >}, R задано на множині { a, b, c },

4) R ={< x, y >: x, y – книги, видані в одному році}, R задано на множині книг,

5) R ={<1,2>,<1,3>,<2,4>,<3,2>,<3,1>,<3,3>}, R задано на множині {1,2,3, 4}. Чи виконується для нього умова R = R ^-1?

6) R ={<1,2>,<2,5>,<3,3>,<4,1>,<5,3>,<3,2>}, R задано на множині {1,2,3,4,5}. Чи виконується для нього співвідношення R ²= R?

7) R ={< a, d >, < b, b >, < b, c >, < d, a >, < c, b >, < a, c >, < d, d >, < c, a >}, R задано на множині { a, b, c, d },

8) R ={< x, y >: x, y – книги різних авторів}, R задано на множині книг,

9) R ={< x, y >: x, y – трикутники на площині, які мають рівні периметри}, R задано на множині геометричних фігур,

10) R ={< x, y >: x, y – країни, розташовані на різних континентах}, R задано на множині країн світу,

11) R ={< x, y >: x, y – картини одного жанру}, R задано на множині картин,

12) R ={< x, y >: x, y – міста, між якими немає прямого автомобільного сполучення}, R задано на множині міст України,

13) R ={< x, y >: x, y – трамваї, що обслуговують один маршрут}, R задано на множині одиниць міського електротранспорту,

14) R ={< x, y >: слово x зустрічається в орфографічному словнику раніше слова y }, R задано на множині слів орфографічного словника,

15) R ={< x, y >: x, y – тварини одного виду}, R задано на множині тварин,

16) R ={< x, y >: x, y – слова в орфографічному словнику, між якими є принаймні два слова}, R задано на множині слів орфографічного словника,

17) R ={< x, y >: x, y – слова в орфографічному словнику, які знаходяться поруч}, R задано на множині слів орфографічного словника,

18) R ={< x, y >: x, y – слова у словнику, які починаються з однієї літери}, R задано на множині слів орфографічного словника,

19) R ={< x, y >: x, y – слова в орфографічному словнику, між якими є більше п’яти слів}, R задано на множині слів орфографічного словника,

20) R ={< x, y >: x, y – слова у словнику, що починаються різними літерами}, R задано на множині слів орфографічного словника,

21) R ={< x, y >: x, y – костюми різного кольору}, R заданo на множині костюмів, що належать одній особі,

22) R ={< x, y >: x, y – депутати від різних округів}, R задано на множині депутатів одного скликання,

23) R ={< x, y >: x, y – страви, що містять цукор}, R задано на множині страв,

24) R ={< x, y >: x, y – музичні твори одного композитора}, R задано на множині музичних творів,

25) R ={< A, B >: A Ç B =Æ}, R задано на булеані деякої множини Х,

26) R ={< x, y >: x, y – множини, що мають принаймні два спільних елемента}, R задано на булеані деякої множини Х,

27) R ={< A, B >: A та B мають один спільний елемент}, R задано на булеані деякої множини Х,

28) R ={< x, y >: x, y – учні, які навчаються в одному класі, але вивчають різні іноземні мови}, R задано на множині учнів однієї школи,

29) R ={< x, y >: x, y – міста України, у яких є промислові підприємства одного й того ж профілю}, R задано на множині міст України,

30) R ={< x, y >: x, y – книги, видані одним видавництвом у різні роки}, R заданo на множині книг, надрукованих в Україні,

31) R ={< x, y >: x, y Î{1,3,4,6}, x + y <12}, R задано на множині {1,2,3,4,5,6,7},

32) R ={< x, y >: x - y £90°}, R задано на множині кутів,

33) R ={< x, y >: x + y >180°}, R задано на множині кутів,

34) R ={< x, y >: x + y =90°}, R задано на множині кутів,

35) R ={< x, y >: x, y – олівці різних кольорів}, R задано на множині олівців,

36) R ={< x, y >: x, y – маршрути транспорту, які мають спільну частину}, R задано на множині маршрутів міського громадського транспорту,

37) R ={< x, y >: x, y – чотирикутники на площині, які мають хоча б одну пару рівних сторін}, R задано на множині чотирикутників на площині,

38) R ={< x, y >: x, y – матриці одного порядку}, R задано на множині квадратних матриць над множиною чисел Х,

39) R ={< x, y >: x, y – столиці різних країн світу}, R задано на множині міст Землі,

40) R ={< x, y >: x, y – зірки одного сузір’я}, R задано на множині зірок Всесвіту,

41) R ={< x, y >: x, y – чоловічі імена}, R задано на множині імен людей,

42) R ={< x, y >: x, y – множини різної потужності}, R задане на булеані деякої множини,

43) R ={< x, y >: x не є власною підмножиною y }, R задане на булеані деякої множини.

XXV. Побудувати на деякій множині А бінарне відношення, яке є:

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

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

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

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

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

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

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

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

9) симетричним, не рефлексивним, не антирефлексивним,

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

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

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

13) симетричним, транзитивним, антисиметричним,

14) симетричним, рефлексивним, антисиметричним,

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

XXVI. Нехай R ₁, R ₂ – рефлексивні відношення на множині А. Довести, що: 1) рефлексивними на А є відношення R ₁È R ₂, R ₁Ç R ₂, R ₁^-1, R ₁* R ₂,

2) R ₁È R ₂ Í R ₁* R ₂.

XXVII. Нехай R ₁, R ₂ – антирефлексивні відношення на множині А. Довести, що антирефлексивними на А є відношення R ₁È R ₂, R ₁Ç R ₂, R ₁^-1. Чи є антирефлексивним на А відношення R ₁* R ₂?

XXVІIІ. Нехай R ₁, R ₂ – симетричні відношення на множині А. Довести: 1) симетричними на А є відношення R ₁È R ₂, R ₁Ç R ₂, R ₁^-1, R ₁* R ₁^-1;

2) відношення R ₁* R ₂ симетричне на А Û R ₁* R ₂= R ₂* R ₁.

XXIX. Нехай R ₁, R ₂ – антисиметричні відношення на множині А. Довести:

1) антисиметричними на А є відношення R ₁Ç R ₂ та R ₁^-1;

2) відношення R ₁È R ₂ антисиметричне на А Û R ₁Ç R ₂^-1 Í i_A.

XXX. Нехай R ₁, R ₂ – асиметричні відношення на множині А. Чи є асиметричними на А відношення: R ₁È R ₂, R ₁Ç R ₂, R ₁^-1, R ₁* R ₂?

XXXI. Нехай R ₁, R ₂ – транзитивні відношення на множині А. Чи є транзитивними на А відношення: R ₁È R ₂, R ₁Ç R ₂, R ₁^-1, R ₁* R ₂?

ХXXIІ. Нехай R – бінарне відношення на А. Довести, що:

1) якщо R асиметричне, то R антирефлексивне,

2) якщо R асиметричне, то R антисиметричне,

3) якщо R антирефлексивне та транзитивне, то R асиметричне,

4) якщо R симетричне, транзитивне й для кожного елемента х з А існує елемент у з А такий, що < x, y >Î R, то R рефлексивне,

5) якщо R симетричне та антисиметричне, то R транзитивне,

6) якщо R рефлексивне та антисиметричне, то R Ç R ^-1= і_А.

XXXIIІ. Які з відношень завдань XXVIІ-XXІX є відношеннями еквівалентності? Для кожного відношення еквівалентності визначити, яке розбиття воно породжує.

XXXІV. Чи є відношеннями еквівалентності відношення:

1) R_m Í N ², m >1, R_m ={< a, b >| (a - b) ділиться на m },

2) Т Í(N ´ N)², < a, b > Т < c, d > Û a + d = b + c,

3) S Í(N ´ N)², < a, b > S < c, d > Û (ad = bc, b ¹0, d ¹0) або (a = c, b = d =0),

4) W Í R ², aWb Û (a - b) – раціональне число.

XXXV. Побудувати відношення еквівалентності на множині:

1) {Æ, a, s, r, t },

2) книг університетської бібліотеки,

3) слів, що знаходяться на одній сторінці деякої книги,

4) мешканців одного будинку,

5) раціональних чисел,

6) житлових будинків Києва,

7) слів орфографічного словника,

8) вищих навчальних закладів Києва,

9) читачів однієї бібліотеки,

10) квадратних матриць порядку n над деякою множиною Р,

11) точок площини,

12) N ²,

13) паралелограмів на плошині,

14) парних цілих чисел,

15) непарних натуральних чисел,

16) літер українського алфавіту.

XXXVI. Нехай R ₁, R ₂ – відношення еквівалентності на А. Довести, що:

1) R ₁Ç R ₂ – відношення еквівалентності на А,

2) R ₁^-1 – відношення еквівалентності на А,

3) R ₁* R ₂ є відношенням еквівалентності на А Û R ₁* R ₂= R ₂* R ₁,

4) R ₁È R ₂ є відношенням еквівалентності на А Û R ₁È R ₂= R ₁* R ₂,

5) (R ₁)¢ не є відношенням еквівалентності.

XXXVII Нехай R ₁, R ₂ – відношення еквівалентності на А. Довести, що

1) R ₁* R ₁= A ² Û R ₁= A ², 2) R ₁* R ₂= A ² Û R ₂* R ₁= A ².

XXXVIII. Довести, що R є відношенням еквівалентності на А Û (R * R ^-1)È i_A = R.

XXXIX. Нехай R є транзитивне та симетричне відношення на деякій множині А й D(R)ÈR(R)= А. Довести, що R – відношення еквівалентності на А.

XL. Нехай R – рефлексивне та транзитивне відношення на деякій множині А. Довести, що R Ç R ^-1 є відношення еквівалентності.

XLІ. На даній множині А задати принаймні два відношення еквівалентності й побудувати відповідні фактор-множини.

1) А ={ a, b, c, d }, 2) A ={!,~,$,%,*,&}, 3) A ={1,2,3, a, b, c, d },

4) A = N, 5) A = Z, 6) A = Q,

7) A = R, 8) A =({1,2,3})², 9) A = N ²,

10) A = N È N ², 11) A ={3 k | k Î Z }, 12) A ={< x, y >| x Î N, y Î Z },

13) A – множина людей.

XLІІІ. Скільки можна побудувати двоелементних фактор-множин для множини, що має n елементів?

XLIV. Описати фактор-множини, що визначаються відношеннями еквівалентності із завдань XXXІX та XL.

XLV. Для заданого на множині A ={ a, b, c, d, e } відношення R побудувати рефлексивне, симетричне, транзитивне замикання, а також R_rst та A / R_rst.

1) R ={< a, b >,< c, c >,< d, a >,< d, d >}, 2) R ={< b, c >,< c, b >,< a, a >,< b, b >},

3) R ={< d, c >,< a, a >,< c, c >,< d, d >}, 4) R ={< a, c >,< b, a >,< b, b >,< a, b >},

5) R ={< c, b >,< c, d >,< c, a >,< c, c >}, 6) R ={< a, d >,< a, a >,< d, b >,< d, c >},

7) R ={< c, d >,< c, b >,< b, a >,< d, b >}, 8) R ={< a, c >,< b, d >,< d, a >,< c, b >},

9) R ={< d, d >,< a, d >,< d, c >,< b, a >}, 10) R ={< b, c >,< d, c >,< c, c >,< c, a >}.

XLVI. Довести, що відношення R È R ²È…È Rⁿ симетричне для будь-якого n ³1, якщо R симетричне.

XLVІІ. Нехай R – бінарне відношення на множині А. Довести, що:

1) якщо R рефлексивне, то R = R_r;

2) якщо R симетричне, то R = R_s;

3) якщо R транзитивне, то R = R_t.