Дискретна математика для програмістів

лекция

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

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

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

б) симетричності: з (x1, х2) R випливає (x2, х1) R;

в) транзитивності: якщо (x1, х2) R і (x2, х3) R, то (x1, х3) R;

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

Для 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:

Х =,

де Xj непорожні і попарно не перетинаються, визначає деяке відношення еквівалентності, а саме x х, якщо існує такий індекс j J, що x,х Xj. У цьому випадку підмножини Xj є класами еквівалентності для цього відношення.

Делись добром ;)