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

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

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

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

  1. Рефлексивность: [latex]a \sim a[/latex], [latex]\forall a \in A[/latex];
  2. Симметричность: [latex]a \sim b[/latex], то [latex]b \sim a[/latex], [latex]\forall a,b \in A[/latex];
  3. Транзитивность: [latex]a \sim b[/latex] и [latex]b \sim c[/latex], то [latex]a \sim c[/latex], [latex]\forall a,b,c \in A[/latex].
  4. Если [latex]a[/latex] связан с [latex]b[/latex], будем писать [latex]a \sim b[/latex] и говорить, что [latex]a[/latex] эквивалентен [latex]b[/latex].

Определение

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

Теорема

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

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

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

[latex]x \sim_{\rho} y \Leftrightarrow (\exists i \in I)(x \in B_i) \land (y \in B_i).[/latex]

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

Пример

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

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

Источники:

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

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

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