Рефлексивне, симетричне та транзитивне відношення на множині А називається відношенням еквівалентності на А.
Прикладом відношення еквівалентності на множині А={a,b,c,d} є відношення R=iAÈ{<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, отже, iAÍR, тобто R рефлексивне. Нехай <x,y>ÎR. Це означає, що x,yÎC для деякої С з Р, але тоді у,хÎC для деякої С з Р, тобто <y,x>ÎR, отже, R симетричне. Нехай <x,y>ÎR, <y,z>ÎR. Це означає, що x,yÎC для деякої С з Р й у,zÎC1 для деякої С1 з Р, але оскільки Р – розбиття, то кожен елемент множини А належить лише одній множині з розбиття, тому yÎC, yÎC1 Þ C=C1, а тоді 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=iAÈ{<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 – клас розбиття, який містить число 0. Цьому класу будуть також належати ті числа з N, котрі мають ту ж саму парність, що й число 0, тобто усі додатні парні числа. Таким чином, Р0={2k| kÎN}. Число 1 не входить у Р0, отже, у Р існує клас розбиття (позначимо його Р1), що містить число 1. Цей клас містить також усі числа, що мають ту саму парність, що й число 1, тобто усі додатні непарні числа. Отже, Р1={2k+1| kÎN}. Таким чином, Р={P1,P2} – шукане розбиття, оскільки P1ÈP2=N, P1ÇP2=Æ й <х,у>ÎR Û x,y належать одному й тому самому класу розбиття (тобто або х,уÎP1, або х,уÎР2).
