Отношение эквивалентности

Определение:

Бинарное отношение $R$ на множестве $X$ называется отношением эквивалентности (англ. equivalence binary relation), если оно обладает следующими свойствами: Рефлексивность: $\forall x \in X: xRx$. Симметричность: $\forall x, y \in X:$ если $xRy$, то $yRx$. Транзитивность: $\forall x, y, z \in X:$ если $xRy$ и $yRz$, то $xRz$.

Отношение эквивалентности обозначают символом $\thicksim$. Запись вида $a \thicksim b$ читают как "$a$ эквивалентно $b$"

Примеры отношений эквивалентности

• Отношение равенства($=$) является тривиальным примером отношения эквивалентности на любом множестве.
• Отношение равенства по модулю $k$: $a \equiv b \mod k$ на множестве целых чисел.
• Отношение параллельности прямых на плоскости.
• Отношение подобия фигур на плоскости.
• Отношение равносильности на множестве уравнений.
• Отношение связности вершин в графе.
• Отношение быть одного роста на множестве людей.

Следующие отношения не являются отношениями эквивалентности:

• Отношения порядка, так как они не являются симметричными.
• Отношение быть знакомым на множестве людей, так как оно не транзитивное.

Классы эквивалентности

Определение:

Система непустых подмножеств $\{M_1, M_2, \ldots, M_n, \ldots\}$ множества $M$ называется разбиением (англ. partition) данного множества, если: $M = M_1 \cup M_2 \cup \ldots \cup M_n \cup \ldots$ $M_i \cap M_j = \varnothing$ при $i \neq j$. Множества $M_1, M_2, \ldots, M_n, \ldots$ называются классами данного разбиения.

Примерами разбиений являются:

• Разбиение многоугольников на группы по числу вершин.
• Разбиение треугольников по свойствам углов (остроугольные, прямоугольные, тупоугольные).
• Разбиение учащихся школы по классам.

Теорема:

Если на множестве M задано отношение эквивалентности $\thicksim$, то оно порождает разбиение этого множества на классы эквивалентности такое, что: любые два элемента одного класса находятся в отношении $\thicksim$ любые два элемента разных классов не находятся в отношении $\thicksim$

Семейство всех классов эквивалентности множества образует множество, называемое фактор-множеством, или факторизацией множества $M$ по отношению $\thicksim$, и обозначаемое $M/^{\thicksim}$.

Примеры

• Равенство - классический пример отношения эквивалентности на любом множестве, в т. ч. вещественных чисел
• Равенство по модулю: $a \equiv b~(mod ~ m)$
• В Евклидовой геометрии:
  • отношение подобия$("\thicksim ")$
  • отношение параллельности$\colon ~ ("\parallel ")$
  • отношение конгруэнтности$\colon ~ ("\cong ")$
• Разбиение многоугольников по количеству вершин
• Оношение равносильности на множестве уравнений
• Отношение равномощности множеств
• Отношение принадлежать к одному виду на множестве животных
• Отношение жить в одном городе на множестве людей

См. также

• Определение отношения
• Рефлексивное отношение
• Симметричное отношение
• Транзитивное отношение
• Отношение порядка

Источники информации

• Wikipedia | Отношение эквивалентности
• Wikipedia | Equivalence relation
• Бинарные отношения. Отношение эквивалентности