Какие бинарные отношения обладают свойством эквивалентности

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

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

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].

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

Определение

Пусть [latex]rho[/latex] — отношение эквивалентности, тогда подмножество [latex]overline{X}={yin Avert ysim_{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: cin K_a[/latex] и [latex]cin 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)_{iin 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$ называют множество $Atimes B,$состоящее из всех упорядоченных пар, где $ ain A, bin B. $

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

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

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

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

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

• на множестве целых чисел $Z$ отношения «делится», «делит», «равно», «больше», «меньше», «взаимно просты»;
• на множестве прямых пространства отношения «параллельны», «взаимно перпендикулярны», «скрещиваются», «пересекаются», «совпадают»;
• на множестве окружностей плоскости «пересекаются», «касаются», «концентричны».

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

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

Композиция (суперпозиция) бинарных отношений $R$ и $S$ — это множество ${langle x,yrangle |exists zlangle xSzwedge zRyrangle}$ и обозначается, как $Rcirc S$.

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

• Рефлексивность: $forall xin M(xRx)$
• Антирефлексивность (иррефлексивность): $forall xin Mneg (xRx)$
• Корефлексивность: $forall x,yin M(xRyRightarrow x=y)$
• Симметричность: $forall x,yin M(xRyRightarrow yRx)$
• Антисимметричность: $forall x,yin M(xRywedge yRxRightarrow x=y)$
• Асимметричность: $forall x,yin M(xRyRightarrowneg (yRx))$. Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.
• Транзитивность: $forall x,y,zin M(xRywedge yRzRightarrow xRz)$
• Связность: $forall x,yin M(xneq yRightarrow xRylor yRx)$
• Рефлексивное транзитивное отношение называется отношением квазипорядка
• Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности
• Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка
• Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка
• Полное антисимметричное (для любых $x, y$ выполняется $xRy$ или $yRx$) транзитивное отношение называется отношением линейного порядка

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

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

  Например, пересечением отношения «не меньше» и «не равно» является отношение «больше».
  $ xAyLeftrightarrow xgeq y, xByLeftrightarrow xneq y$, тогда $Acap BLeftrightarrow x>y $

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

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

• Включение. Обозначается $Asubseteq B$. Первое отношение включено во второе, если все те пары, для которых выполняется первое отношение, являются подмножеством пар, для которых выполняется второе отношение. Если $Asubseteq B$, то $Aneq B$. Если $Asubseteq B$, то, когда любые два элемента из множества, на котором выполняется отношение $A$, связаны этим отношением, они связаны отношением $B$.

Очевидно, для любого отношения $A varnothingsubseteq Asubseteq 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)}.$


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


Задача

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

Спойлер

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

• Рефлексивность
  $(forall xin A)langle x,xranglein R$ – это ложное высказывание.
  Можно привести контрпример: $x=3$, пара $langle 3,3rangle$ не принадлежит множеству $R$. Бинарное отношение не является рефлексивным.
• Антирефлексивность
  $(forall xin A)langle x,xranglenotin R$ – это ложное высказывание.
  Можно привести контрпример: $x=1$, пара $langle 1,1rangle$ принадлежит множеству $R$. Бинарное отношение не является антирефлексивным.
• Корефлексивность
  $(forall x,yin A)langle x,yranglenotin R$ – это ложное высказывание.
  Можно привести контрпример: $x=1,y=2$, пара $langle 1,2rangle$ принадлежит множеству $R$, но $xneq y$. Бинарное отношение не является антирефлексивным.
• Симметричность
  $ forall x,yin A (langle x,yranglein R): langle y,xranglein R$ – это ложное высказывание.
  Можно привести контрпример, $x=1,y=2$ пара $langle 1,2rangle$ принадлежит множеству $R$, а пара $langle 2,1rangle$ не принадлежит множеству $R$. Бинарное отношение не является симметричным.
• Антисимметричность
  $forall x,yin A(xRywedge yRxRightarrow x=y)$ – это истинное высказывание
  Контрпример подобрать невозможно. Бинарное отношение является антисимметричным.
• Асимметричность
  Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения и отношение не является антирефлексивным, отношение не является асимметричным.
• Транзитивность
  $forall x,y,zin A(xRywedge yRzRightarrow xRz)$– это ложное высказывание.
  Можно привести контр пример, $x=1,y=2,z=3$ пара $langle 1,2rangle$ принадлежит множеству R и пара $langle 2,3rangle$ принадлежит множеству $R$, а пара $langle 1,3rangle$ не принадлежит множеству $R$. Бинарное отношение не является транзитивным.
• Связность
  $forall x,yin A(xneq yRightarrow xRylor yRx)$ – это ложное высказывание.
  Можно привести контрпример, $x=3,y=4$, $3neq 4$ пара $langle 3,4rangle$ не принадлежит множеству $R$ и пара $langle 4,3rangle$ не принадлежит множеству $R$. Бинарное отношение не является связанным.

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

[свернуть]

Источники:

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

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

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

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

максимум из 15 баллов

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