Відношення еквівалентності, зв’язок з розбиттями, ПріМат

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

Бінарне відношення називається відношенням еквівалентності, якщо відповідає умовам:

1. Рефлексивність: , ;
2. Симетричність: , то , ;
3. Транзитивність: і , то , .

Якщо пов'язаний з , будемо писати і говорити, що еквівалентний .

Визначення

Нехай відношення еквівалентності, тоді підмножина називається класом еквівалентності.

Будь-яке відношення еквівалентності на множині утворює розбиття множини на класи еквівалентності. Назад, будь-яке розбиття безлічі задає на ньому відношення еквівалентності.

Доведення

Справді, нехай група елементів з еквівалентних фіксованому елементу . В силу рефлексивності. Покажемо, що для будь-яких і : або не мають спільних елементів. Доведемо методом «від неприємного». Нехай і, тобто. і , а з транзитивності , і . Тоді, те, тобто. . Отже, дві групи, мають хоча б загальний елемент, повністю збігаються. Ми отримали розбиття на класи. Доведемо зворотне. Тепер нехай - деяке розбиття множини. Розглянемо ставлення , таке, що має місце тоді й тільки тоді, коли і належать одному й тому елементу даного розбиття:

Очевидно, що введене ставлення є рефлексивним і симетричним. Якщо будь-яких , і має місце і , те , і з визначення відносини належать одному й тому елементу розбиття. Отже, і ставлення транзитивне. Таким чином, - еквівалентність на .

Відношення рівності на безлічі дійсних чисел є відношенням еквівалентності. : рефлексивно на множині; : і симетрично на множині; : і , то транзитивно на множині .

---