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

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

Бинарное отношение называется отношением эквивалентности, если отвечает условиям:

Рефлексивность: $a \sim a$ , $\forall a \in A$ ;
Симметричность: $a \sim b$ , то $b \sim a$ , $\forall a,b \in A$ ;
Транзитивность: $a \sim b$ и $b \sim c$ , то $a \sim c$ , $\forall a,b,c \in A$ .

Если $a$ связан с $b$ , будем писать $a \sim b$ и говорить, что $a$ эквивалентен $b$ .

Определение

Пусть $\rho$ — отношение эквивалентности, тогда подмножество $\overline{X}=\{y\in A\vert y\sim_{\rho}x\}$ называется классом эквивалентности.

Теорема

Любое отношения эквивалентности на множестве $A$ образует разбиение множества $A$ на классы эквивалентности. Обратно, любое разбиение множества $A$ задает на нем отношение эквивалентности.

Доказательство

Действительно, пусть $K_a$ — группа элементов из $A$ эквивалентных фиксированному элементу $a$ . В силу рефлексивности $a \in K_a$ .
Покажем, что для любых $K_a$ и $K_b$ : $K_a = K_b$ или не имеют общих элементов.
Докажем методом «от противного».
Пусть $\exists c: c\in K_a$ и $c\in K_b$ , т.е. $c \sim a$ и $c \sim b$ , а в силу транзитивности $a \sim b$ , и $b \sim a$ . Тогда $\forall x \in K_a$ , то $x \sim a$ $\Rightarrow$ $x \sim b$ , т.е. $x \in K_b$ . Таким образом, две группы, имеющие хотя бы $1$ общий элемент, полностью совпадают.
Мы получили разбиение на классы.
Докажем обратное.
Теперь пусть $(B_i)_{i\in I}$ — некоторое разбиение множества $A$ . Рассмотрим отношение $\rho$ , такое, что $x \sim_{\rho} y$ имеет место тогда и только тогда, когда $x$ и $y$ принадлежат одному и тому же элементу $B_i$ данного разбиения:

$x \sim_{\rho} y \Leftrightarrow (\exists i \in I)(x \in B_i) \land (y \in B_i).$

Очевидно, что введенное отношение рефлексивно и симметрично. Если для любых $x$ , $y$ и $z$ имеет место $x \sim_{\rho} y$ и $y \sim_{\rho} z$ , то $x$ , $y$ и $z$ в силу определения отношения $\rho$ принадлежат одному и тому же элементу $B_i$ разбиения. Следовательно, $x \sim_{\rho} z$ и отношение $\rho$ транзитивно. Таким образом, $\rho$ — эквивалентность на $A$ .

Пример

Отношение равенства $=_\rho$ на множестве действительных чисел является отношением эквивалентности.
$\forall a \in R$ : $a=a$ $\Rightarrow$ $=_\rho$ рефлексивно на множестве $R$ ;
$\forall a,b \in A$ : $a=b$ и $b=a$ $\Rightarrow$ $=_\rho$ симметрично на множестве $R$ ;
$\forall a,b,c \in A$ : $a=b$ и $b=c$ , то $a=c$ $\Rightarrow$ $=_\rho$ транзитивно на множестве $R$ .

Тест поможет определить как хорошо вы усвоили материал.

Источники:

Конспект лекций С.В.Федоровского
Воеводин В.В. Линейная алгебра. М.: Наука, 1994,стр 15-17
Отношения эквивалентности на множестве

Метка: связь с разбиениями.