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

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

Прикладом відношення еквівалентності на множині А={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} на множині людей не є відношенням еквівалентності, тому що воно не симетричне.

Теорема 9. Бінарне відношення 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₁, або х,уР₂).