Отношение эквивалентности, связь с разбиениями

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

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

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

  1. Рефлексивность: a \sim a, \forall a \in A;
  2. Симметричность: a \sim b, то b \sim a, \forall a,b \in A;
  3. Транзитивность: a \sim b и b \sim c, то a \sim c, \forall a,b,c \in A.
  4. Если 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\Rightarrowx \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.

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

Источники:

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

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *