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

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

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

Теорема 7. Бінарне відношення 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, тобто усі додатні парні числа. Таким чином, Р ₀={2 k | k Î N }. Число 1 не входить у Р ₀, отже, у Р існує клас розбиття (позначимо його Р ₁), що містить число 1. Цей клас містить також усі числа, що мають ту саму парність, що й число 1, тобто усі додатні непарні числа. Отже, Р ₁={2 k +1| k Î N }. Таким чином, Р ={ P ₁, P ₂} – шукане розбиття, оскільки P ₁È P ₂= N, P ₁Ç P ₂=Æ й < х, у >Î R Û x, y належать одному й тому самому класу розбиття (тобто або х, у Î P ₁, або х, у Î Р ₂).