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

Відношення 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 є класами еквівалентності для цього відношення.

Фактор-множина

Виходячи із сказаного кожен клас еквівалентності X_j є підмножиною множини X, що складається з елементів, еквівалентних деякому фіксованому елементу цієї множини. Тому можна розглянути і множину всіх класів еквівалентності, яку звичайно називають фактор-множиною за даним відношенням еквівалентності R і позначають наступним чином Х / R. Якщо через K (x) позначити клас еквівалентності елемента x, то K (x) є елементом фактор-множини та x Î K (x).

Можна дати просту інтерпретацію фактор-множини на прикладах відношень еквівалентності, наведених раніше (1, 2, 3, 4, 5):

1)°фактор- множина - це множина Z_m цілих чисел, порівняних за модулем m;

2)°фактор- множина - це множина напрямлених прямих на площині;

3)°фактор- множина - це множина місяців року. Вона може мати менше 12 місяців, бо в аудиторії може не виявитися студентів, які народилися в одному з місяців, скажімо в лютому.