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

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

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

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

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

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

Пусть 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)\}

      ... показать

      Источники: