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

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

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

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

  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. Отношения эквивалентности на множестве

Бинарные отношения

Пусть $A$ и $B$ два конечных множества. Декартовым произведением множеств $A$ и $B$ называют множество $A\times B,$состоящее из всех упорядоченных пар, где $ a\in A, b\in B. $

Бинарным отношением между элементами множества $A$ и $B$ называется любое подмножество $R$ множества $A\times B$, то есть $ R\subset A\times B.$

По определению, бинарным отношением называется множество пар. Если R — бинарное отношение (т.е. множество пар), то говорят, что параметры $x$ и $y$ связаны бинарным отношением $R$, если пара $\langle x,y \rangle $ является элементом R, т.е. $\langle x,y \rangle\in R. $

Высказывание: «предметы $x$ и $y$ связаны бинарным отношением $R$» записывают в виде $xRy.$Таким образом, $ xRy\leftrightarrow\langle x,y\rangle\in R.$

Если $R\subset A\times A $, то говорят, что бинарное отношение определено на множестве $A$.

Примеры бинарных отношений:

  • на множестве целых чисел $Z$ отношения «делится», «делит», «равно», «больше», «меньше», «взаимно просты»;
  • на множестве прямых пространства отношения «параллельны», «взаимно перпендикулярны», «скрещиваются», «пересекаются», «совпадают»;
  • на множестве окружностей плоскости «пересекаются», «касаются», «концентричны».
  • Областью определения бинарного отношения $R$ называется множество, состоящее из таких $x$, для которых $\langle x,y \rangle\in R $ хотя бы для одного $y$.
    Область определения бинарного отношения будем обозначать $ \Re R$.
    $\Re R=\{ x|\exists y(\langle x,y\rangle\in R)\}$
    Областью значений бинарного отношения $R$ называется множество, состоящее из таких $y$, для которых $\langle x,y \rangle\in R $ хотя бы для одного $x$.
    Область значений бинарного отношения будем обозначать $\Im R$
    $\Im R=\{ y|\exists x(\langle x,y\rangle\in R)\}$

    Инверсия (обратное отношение) $R$ — это множество $\{\langle x,y\rangle |\langle y,x\rangle\in R\}$ и обозначается, как ${R}^{-1}.$

    Композиция (суперпозиция) бинарных отношений $R$ и $S$ — это множество $\{\langle x,y\rangle |\exists z\langle xSz\wedge zRy\rangle\}$ и обозначается, как $R\circ S$.

    Свойства бинарных отношений

    Бинарное отношение $R$ на некотором множестве $M$ может обладать различными свойствами, например:

    • Рефлексивность: $\forall x\in M(xRx)$
    • Антирефлексивность (иррефлексивность): $\forall x\in M\neg (xRx)$
    • Корефлексивность: $\forall x,y\in M(xRy\Rightarrow x=y)$
    • Симметричность: $\forall x,y\in M(xRy\Rightarrow yRx)$
    • Антисимметричность: $\forall x,y\in M(xRy\wedge yRx\Rightarrow x=y)$
    • Асимметричность: $\forall x,y\in M(xRy\Rightarrow\neg (yRx))$. Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.
    • Транзитивность: $\forall x,y,z\in M(xRy\wedge yRz\Rightarrow xRz)$
    • Связность: $\forall x,y\in M(x\neq y\Rightarrow xRy\lor yRx)$

    Виды отношений

    • Рефлексивное транзитивное отношение называется отношением квазипорядка
    • Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности
    • Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка
    • Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка
    • Полное антисимметричное (для любых $x, y$ выполняется $xRy$ или $yRx$) транзитивное отношение называется отношением линейного порядка
    • Операции над отношениями

      Над бинарными отношениями можно производить некоторые операции, точно так же, как и над множествами. Не ограничивая общности, будем считать, что следующие операции выполняются на множестве $M$.

      • Пересечение. Пересечением двух бинарных отношений ($A$и $B$) является отношение, которое определяется пересечением соответствующих подмножеств. Очевидно, что отношение $A\cap B$ выполнимо только в том случае, когда некоторые $x$ и $y$ связаны как первым, так и вторым отношением ($xAy$ и $xBy$).

        Например, пересечением отношения «не меньше» и «не равно» является отношение «больше».
        $ xAy\Leftrightarrow x\geq y, xBy\Leftrightarrow x\neq y$, тогда $A\cap B\Leftrightarrow x>y $

      • Объединение. Объединением двух бинарных отношений ($A$ и $B$) является отношение, которое определяется объединением соответствующих подмножеств. Отношение $A\cup B$ выполнимо только в том случае, когда некоторые $x$ и $y$ связаны хотя бы одним из двух отношений хотя бы одно из отношений ($xAy$ или $xBy$).

        Например, объединением отношения «больше» и отношения «равно» является отношение «больше, либо равно».

      • Включение. Обозначается $A\subseteq B$. Первое отношение включено во второе, если все те пары, для которых выполняется первое отношение, являются подмножеством пар, для которых выполняется второе отношение. Если $A\subseteq B$, то $A\neq B$. Если $A\subseteq B$, то, когда любые два элемента из множества, на котором выполняется отношение $A$, связаны этим отношением, они связаны отношением $B$.
      • Очевидно, для любого отношения $A \varnothing\subseteq A\subseteq U$, где $\varnothing$ — пустое, а $U$- полное отношение.

      Графическое представление бинарных отношений

      Приведём в пример два графических представления бинарных отношений на множстве $X = \{a, b, c, d, e\}.$
      Первый способ тесно связан с аналитической геометрией. Пусть дана пара взаимно перпендикулярных осей ($Ox$ и $Oy$). На каждой оси нужно отметить точки которые являются элементами множества $X$.
      Будем считать, что $a, b, c, d, e$ — координаты точек на горизонтальной и вертикальной осях. Теперь отметим на плоскости точки с координатами $(x, y)$. На рисунке изображена совокупность точек, соответствующих следующему отношению: $R=\{(a, b), (a, c), (b, d), (c, e), (e,b), (e, e)\}.$
      Image1

      Следующий способ, который мы рассмотрим, заключается в использовании ориентированных графов. Элементы множества $X$ становятся вершинами графа, а элементы $\langle x,y\rangle $ отношения $R$ ребрами, которые соединяют первый член $x$ отношения со вторым членом $y$. Граф, соответствующий бинарному отношению $R$, изображен на рисунке.
      Image1

      Задача

      Бинарное отношение $R$ задано на множестве $A=\{1,2,3,4\}$, определить его свойства.
      $R=\{(1,1),(1,2),(2,3),(2,2),(2,4)\}$

      Спойлер

      Проверим все свойства отношения:

      • Рефлексивность
        $(\forall x\in A)\langle x,x\rangle\in R$ – это ложное высказывание.
        Можно привести контрпример: $x=3$, пара $\langle 3,3\rangle$ не принадлежит множеству $R$. Бинарное отношение не является рефлексивным.
      • Антирефлексивность
        $(\forall x\in A)\langle x,x\rangle\notin R$ – это ложное высказывание.
        Можно привести контрпример: $x=1$, пара $\langle 1,1\rangle$ принадлежит множеству $R$. Бинарное отношение не является антирефлексивным.
      • Корефлексивность
        $(\forall x,y\in A)\langle x,y\rangle\notin R$ – это ложное высказывание.
        Можно привести контрпример: $x=1,y=2$, пара $\langle 1,2\rangle$ принадлежит множеству $R$, но $x\neq y$. Бинарное отношение не является антирефлексивным.
      • Симметричность
        $ \forall x,y\in A (\langle x,y\rangle\in R): \langle y,x\rangle\in R$ – это ложное высказывание.
        Можно привести контрпример, $x=1,y=2$ пара $\langle 1,2\rangle$ принадлежит множеству $R$, а пара $\langle 2,1\rangle$ не принадлежит множеству $R$. Бинарное отношение не является симметричным.
      • Антисимметричность
        $\forall x,y\in A(xRy\wedge yRx\Rightarrow x=y)$ – это истинное высказывание
        Контрпример подобрать невозможно. Бинарное отношение является антисимметричным.
      • Асимметричность
        Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения и отношение не является антирефлексивным, отношение не является асимметричным.
      • Транзитивность
        $\forall x,y,z\in A(xRy\wedge yRz\Rightarrow xRz)$– это ложное высказывание.
        Можно привести контр пример, $x=1,y=2,z=3$ пара $\langle 1,2\rangle$ принадлежит множеству R и пара $\langle 2,3\rangle$ принадлежит множеству $R$, а пара $\langle 1,3\rangle$ не принадлежит множеству $R$. Бинарное отношение не является транзитивным.
      • Связность
        $\forall x,y\in A(x\neq y\Rightarrow xRy\lor yRx)$ – это ложное высказывание.
        Можно привести контрпример, $x=3,y=4$, $3\neq 4$ пара $\langle 3,4\rangle$ не принадлежит множеству $R$ и пара $\langle 4,3\rangle$ не принадлежит множеству $R$. Бинарное отношение не является связанным.

      Вывод: заданное бинарное отношение обладает только одним свойством антисимметричности.

      [свернуть]

      Источники:

      • Галушкина, Марьямов, «Задачи и упражнения по дискретной математике», 2007 г., стр.51
      • С.В.Федоровский.Конспект лекций по математической логике
      • Кострикин А.В. , «Введение в алгебру», 1977, стр.134
      • А.И. Мальцев, «Алгебраические системы», 1970, стр.16-19
      • Бинарные отношения

        Вопросы для закрепления пройденного материала

        Таблица лучших: Бинарные отношения

        максимум из 15 баллов
        Место Имя Записано Баллы Результат
        Таблица загружается
        Нет данных