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

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

Прикладом відношення еквівалентності на множині А={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, тобто усі додатні парні числа. Таким чином, Р₀={2k| kÎN}. Число 1 не входить у Р₀, отже, у Р існує клас розбиття (позначимо його Р₁), що містить число 1. Цей клас містить також усі числа, що мають ту саму парність, що й число 1, тобто усі додатні непарні числа. Отже, Р₁={2k+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>| 2x³3y};

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

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=3y}, 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>: 5x+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 – цілі числа, 2x+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={3k| 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.