в). Відношення R називається симетричним, якщо для всіх a,bM таких, що aRb маємо bRa.

г). Відношення R називається антисиметричним, якщо для всіх a,bM таких, що aRb і bRa маємо a = b.

Наприклад, відношення R3,R4,R5,R6,R8 - симетричні, а відношення R1,R2,R7 - антисиметричні.

Неважко переконатись, що відношення R симетричне тоді і тільки тоді, коли R=R-1.

д). Відношення R називається транзитивним, якщо зі співвідношень aRb і bRc випливає aRc.

Наприклад, відношення R1,R2,R4,R5,R7,R8,R9 - транзитивні, а відношення R3,R6 - не транзитивні.

Неважко переконатись, що відношення R транзитивне тоді і тільки тоді, коли RRR.

Зауважимо, якщо відношення R має будь-яку з перерахованих вище властивостей, то обернене відношення R-1 також має ту саму властивість. Таким чином, операція обернення зберігає всі п'ять властивостей відношень.

Для довільного відношення R означимо нову операцію. Відношення R* називається транзитивним замиканням відношення R на M, якщо aR*b, a,bM, тоді і тільки тоді, коли у множині M існує послідовність елементів a1,a2,...,an така, що a1 = a, an = b і a1Ra2, a2Ra3,...,an-1Ran.

Наприклад, нехай M - це множина точок на площині і aRb, a,bM, якщо точки a і b з'єднані відрізком. Тоді cR*d, c,dM, якщо існує ламана лінія, яка з'єднує точки c і d.

Можна довести, що відношення R транзитивне тоді і тільки тоді, коли R*=R.

Деякі відношення займають особливе місце в математиці. Розглянемо ці відношення окремо.

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

Відношення R на множині M називається відношенням еквівалентності (або просто еквівалентністю), якщо воно рефлексивне, симетричне і транзитивне.

Враховуючи важливість відношення еквівалентності, дамо розгорнуте означення цього поняття. Таким чином, відношення R на множині M є відношенням еквівалентності або евівалентністю, якщо

1. aRa для всіх aM (рефлексивність);

2. Якщо aRb, то bRa для a,bM (симетричність);

3. Якщо aRb і bRc, то aRc для a,b,cM (транзитивність).

Приклад 1.15. 1. Відношення рівності iM на будь-якій множині M є відношенням еквівалентності. Рівність - це мінімальне відношення еквівалентності, бо при видаленні бодай одного елемента з iM відношення перестає бути рефлексивним, а отже, і відношенням еквівалентності.

2. Відношення рівнопотужності множин є еквівалентністю.

3. Важливу роль відіграє в математиці відношення "мають однакову остачу при діленні на k" або "конгруентні за модулем k", яке є відношенням еквівалентності на множині N натуральних чисел для будь-якого фіксованого kN. Відношення конгруентності за модулем 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 | iI} називається розбиттям множини A, якщо Bi=A і BiBj = для ij. Множини Bi, iI є підмножинами множини A і називаються класами, суміжними класами, блоками або елементами розбиття. Очевидно, що кожний елемент aA належить одній і тільки одній множині Bi, iI.

Припустимо, що на множині M задано відношення еквівалентності R. Виконаємо таку побудову. Виберемо деякий елемент aM і утворимо підмножину SaR = { x | xM і aRx}, яка складається з усіх елементів множини M еквівалентних елементу a. Відтак, візьмемо другий елемент bM такий, що bSaR і утворимо множину SbR = { x | xM і bRx } з елементів еквівалентних b і т.д. Таким чином одержимо сукупність множин (можливо, нескінченну) {SaR,SbR,...}. Побудована сукупність множин { SiR | iI} називається фактор-множиною множини M за еквівалентністю R і позначається M/R.

Приклад 1.16. 1. Фактор-множина за відношенням рівності E для будь-якої множини M має вигляд M/E = { {a} | aM}.

2. Фактор-множина для відношення "конгруентні за модулем 3" на множині N натуральних чисел складається з трьох класів { 3k | kN }, { 3k-1 | kN } і { 3k-2 | kN}.

Доведемо, що фактор-множина M/R є розбиттям множини M. Оскільки за побудовою кожний елемент множини M належить принаймні одній з множин SiR, iI, то SiR = M. Відтак припустимо, що для деяких SaRSbR існує елемент cSaRSbR. Тоді з cSaR випливає aRc, а з cSbR випливає bRc. Iз симетричності і транзитивності відношення R виводимо aRb і bRa. Iз співвідношення aRb і правила побудови множини SaR маємо SaRSbR, а з bRa і правила побудови множини SbR одержуємо протилежне включення SbRSaR. Отже, SaR=SbR, і з одержаної суперечності випливає справедливість сформульованого твердження.

Очевидно, що будь-які два елементи з одного класу SiR еквівалентні між собою, в той час як будь-які два елементи з різних класів фактор-множини M/R нееквівалентні. Класи SiR називають класами еквівалентності за відношенням R. Клас еквівалентності, який містить елемент aM часто позначають через [a]R.

Потужність фактор-множини |M/R| називається індексом розбиття або індексом відношення еквівалентності R.

З іншого боку, припустімо, що для множини M задано деяке розбиття {Si | iI }. Побудуємо відношення T на множині M за таким правилом: aTb для a,bM тоді і тільки тоді, коли a і b належать тій самій множині Si розбиття. Неважко переконатись, що відношення T є рефлексивним, симетричним і транзитивним, тобто є відношенням еквівалентності на множині M.

Отже, справедлива така теорема.

Теорема 1.10. Iснує взаємно однозначна відповідність між усіма можливими еквівалентностями на множині M і всіма розбиттями множини M. Тобто, кожному відношенню еквівалентності на множині M відповідає єдине розбиття даної множини на класи і, навпаки, кожне розбиття множини M однозначно задає деяке відношення еквівалентності на M.

Нехай R