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

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