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

ВідношенняR називається відношенням еквівалентності, якщо воно має такі властивості:

а) рефлективності: (x, х) Î R при будь-якому х Î Х;

б) симетричності: з (x₁, х₂) Î R випливає (x₂, х₁) Î R;

в) транзитивності: якщо (x₁, х₂) Î R і (x₂, х₃) Î R, то (x₁, х₃) Î R;

Замість того, щоб писати (x₁, х₂) Î R, часто пишуть x₁ ~ x₂ або x₁ º x₂(mod R) (читається так: x₁ конгруентно x₂ за модулем R) чи, простіше, (x₁ ~ x₂ або x₁ º x₂, якщо немає необхідності ще раз вказувати, що мова йде про одне й те саме відношення R).

Приклади: 1)°Визначимо на множині цілих чисел Z відношення еквівалентності так, що рºq, тоді і тільки тоді, коли p - q ділиться без остачі на деяке наперед задане натуральне число m >1, скажімо m=5. У теорії чисел таке відношення записується у вигляді р º q(mod т).

2)°Нехай Х - множина прямих на площині. Визначимо відношення еквівалентності для прямих x₁ іx_2, покладаючи x₁ º x₂, коли ці прямі паралельні.

3) Нехай Х – множина всіх студентів, які присутні на лекції з дискретної математики. Два студенти еквівалентні, якщо вони народилися в тому самому місяці року.

Для x Î X позначимо через K(x)підмножину, що складається з елементів, еквівалентних x, тобто K(x) = {y | y Î X; y ~ x}. Таку підмножину будемо називати класом еквівалентності. Зрозуміло, що клас еквівалентності є множиною всіх елементів, еквівалентних довільному елементу з цього класу. Справедлива наступна теорема:

Теорема 1. Два класи еквівалентності або не перетинаються або співпадають.

Доведення. Припустимо, що перетин множин K(x)і K(х')непорожній, і візьмемо z Î K(x) Ç K(х'). Клас еквівалентності K(x) утворений з елементів, еквівалентних одному зі своїх елементів x. Оскільки x і z еквівалентні, то за властивістю транзитивності отримуємо, що K(x) утворений також з елементів, еквівалентних z. Аналогічно K(х') утворений з елементів, еквівалентних z. Таким чином, K(х) і K(х') співпадають.

Відношення еквівалентності на множині Х породжує деяке розбиття множини Х, тобто деяку сім’ю непорожніх підмножин множини X (класів еквівалентності), які попарно не перетинаються,а їхоб’єднання рівне X. Будь-які два елементи з одного класу зв’язані відношенням еквівалентності, тобто еквівалентні;з різних класів - не еквівалентні.

Навпаки, будь-яке розбиття множини X: Х = , де X_j непорожні і попарно не перетинаються, визначає деяке відношення еквівалентності, а саме x º х', якщо існує такий індекс j Î J, що x,х' Î X_j. У цьому випадку підмножини X_j є класами еквівалентності для цього відношення.