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

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

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 – множина людей.

ІI. Для заданого відображення множини А={a,b,c,d} у множину В={1,2, 3,4,5} побудувати канонічний розклад.

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

3) F={<a,3>,<b,5>,<c,4>,<d,1>}, 4) F={<a,1>,<b,2>,<c,3>,<d,4>},

5) F={<a,1>,<b,1>,<c,2>,<d,3>}, 6) F={<a,3>,<b,5>,<c,5>,<d,5>}.

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

ІV. Описати фактор-множини, що визначаються відношеннями еквіва-лентності із завдань ІІ та ІІІ до розділу «Відношення еквівалентності».

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

Рефлексивним замиканням бінарного відношення 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).

Теорема 11. Нехай 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у.