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

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