Відношення еквівалентності
Відношення R на множині M називається відношенням еквівалентності (або просто еквівалентністю), якщо воно рефлексивне, симетричне і транзитивне.
Враховуючи важливість відношення еквівалентності, дамо розгорнуте означення цього поняття. Таким чином, відношення R на множині M є відношенням еквівалентності або евівалентністю, якщо
1. aRa для всіх a?M (рефлексивність);
2. Якщо aRb, то bRa для a,b?M (симетричність);
3. Якщо aRb і bRc, то aRc для a,b,c?M (транзитивність).
Приклад 1.15. 1. Відношення рівності iM на будь-якій множині M є відношенням еквівалентності. Рівність - це мінімальне відношення еквівалентності, бо при видаленні бодай одного елемента з iM відношення перестає бути рефлексивним, а отже, і відношенням еквівалентності.
2. Відношення рівнопотужності множин є еквівалентністю.
3. Важливу роль відіграє в математиці відношення "мають однакову остачу при діленні на k" або "конгруентні за модулем k", яке є відношенням еквівалентності на множині N натуральних чисел для будь-якого фіксованого k?N. Відношення конгруентності за модулем k часто позначають a ? b (mod k). Цьому відношенню належать, наприклад, пари натуральних чисел (17,22), (1221,6), (42,57) для k=5, тобто 17 ? 22(mod 5), 1221 ? 6 (mod 5), 42 ? 57 (mod 5).
4. Еквівалентністю є відношення подібності на множині всіх трикутників.
Сукупність множин { Bi | i?I} називається розбиттям множини A, якщо EMBED Equation.2 Bi=A і Bi?Bj = ? для i?j. Множини Bi, i?I є підмножинами множини A і називаються класами, суміжними класами, блоками або елементами розбиття. Очевидно, що кожний елемент a?A належить одній і тільки одній множині Bi, i?I.
Припустимо, що на множині M задано відношення еквівалентності R. Виконаємо таку побудову. Виберемо деякий елемент a?M і утворимо підмножину SaR = { x | x?M і aRx}, яка складається з усіх елементів множини M еквівалентних елементу a. Відтак, візьмемо другий елемент b?M такий, що b?SaR і утворимо множину SbR = { x | x?M і bRx } з елементів еквівалентних b і т.д. Таким чином одержимо сукупність множин (можливо, нескінченну) {SaR,SbR,...}. Побудована сукупність множин { SiR | i?I} називається фактор-множиною множини M за еквівалентністю R і позначається M/R.
Приклад 1.16. 1. Фактор-множина за відношенням рівності E для будь-якої множини M має вигляд M/E = { {a} | a?M}.
2. Фактор-множина для відношення "конгруентні за модулем 3" на множині N натуральних чисел складається з трьох класів { 3k | k?N }, { 3k-1 | k?N } і { 3k-2 | k?N}.
Доведемо, що фактор-множина M/R є розбиттям множини M. Оскільки за побудовою кожний елемент множини M належить принаймні одній з множин SiR, i?I, то EMBED Equation.2 SiR = M. Відтак припустимо, що для деяких SaR?SbR існує елемент c?SaR?SbR. Тоді з c?SaR випливає aRc, а з c?SbR випливає bRc. Iз симетричності і транзитивності відношення R виводимо aRb і bRa. Iз співвідношення aRb і правила побудови множини SaR маємо SaR?SbR, а з bRa і правила побудови множини SbR одержуємо протилежне включення SbR?SaR. Отже, SaR=SbR, і з одержаної суперечності випливає справедливість сформульованого твердження.
Очевидно, що будь-які два елементи з одного класу SiR еквівалентні між собою, в той час як будь-які два елементи з різних класів фактор-множини M/R нееквівалентні. Класи SiR називають класами еквівалентності за відношенням R. Клас еквівалентності, який містить елемент a?M часто позначають через [a]R.
Потужність фактор-множини |M/R| називається індексом розбиття або індексом відношення еквівалентності R.
З іншого боку, припустімо, що для множини M задано деяке розбиття {Si | i?I }. Побудуємо відношення T на множині M за таким правилом: aTb для a,b?M тоді і тільки тоді, коли a і b належать тій самій множині Si розбиття. Неважко переконатись, що відношення T є рефлексивним, симетричним і транзитивним, тобто є відношенням еквівалентності на множині M.
Отже, справедлива така теорема.
Теорема 1.10. Iснує взаємно однозначна відповідність між усіма можливими еквівалентностями на множині M і всіма розбиттями множини M. Тобто, кожному відношенню еквівалентності на множині M відповідає єдине розбиття даної множини на класи і, навпаки, кожне розбиття множини M однозначно задає деяке відношення еквівалентності на M.
Нехай R відношення еквівалентності на множині M. Відображення множини M на фактор-множину M/R, яке кожному елементу a?M ставить у відповідність клас еквівалентності SaR, якому належить елемент a, називається канонічним або природним відображенням множини M на фактор-множину M/R.