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

Нехай 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у.