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

Шаблон:Значения Бина́рное (двуме́стное) отноше́ние (соответствие) — отношение между двумя множествами $A$ и $B$, то есть всякое подмножество декартова произведения этих множеств: $R\subseteq A\times B$. Бинарное отношение на множестве $A$ — любое подмножество $R\subseteq A^2=A\times A$, такие бинарные отношения наиболее часто используются в математике, в частности, таковы равенство, неравенство, эквивалентность, отношение порядка.

Связанные определения

• Множество всех первых компонент пар из $R\subseteq A\times B$ называется областью определения отношения $R$ и обозначается как $\mathrm{D}\mathrm{o}\mathrm{m}R$.

$\mathrm{D}\mathrm{o}\mathrm{m}R=\{x\mid \mathrm{\exists }y((x,y)\in R)\}.$

• Множество всех вторых компонент пар из $R$ называется областью значений отношения $R$ и обозначается как $\mathrm{I}\mathrm{m}R$.

$\mathrm{I}\mathrm{m}R=\{y\mid \mathrm{\exists }x((x,y)\in R)\}.$

• Инверсия (обратное отношение) $R$ — это множество $\{(x,y)\mid (y,x)\in R\}$ и обозначается, как $R^{-1}$.
• Шаблон:Нп3 (суперпозиция) бинарных отношений $R$ и $S$ — это множество $\{(x,y)\mid \mathrm{\exists }z(xRz\wedge zSy)\}$ и обозначается, как $R\circ S$.

Свойства отношений

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

• рефлексивность: $\mathrm{\forall }x\in M:(xRx)$,
• антирефлексивность (иррефлексивность): $\mathrm{\forall }x\in M:\mathrm{\neg }(xRx)$,
• корефлексивность: $\mathrm{\forall }x,y\in M:(xRy\Rightarrow x=y)$,
• симметричность: $\mathrm{\forall }x,y\in M:(xRy\Rightarrow yRx)$,
• антисимметричность: $\mathrm{\forall }x,y\in M:(xRy\wedge yRx\Rightarrow x=y)$,
• асимметричность: $\mathrm{\forall }x,y\in M:(xRy\Rightarrow \mathrm{\neg }(yRx))$,
• транзитивность: $\mathrm{\forall }x,y,z\in M:(xRy\wedge yRz\Rightarrow xRz)$,
• евклидовость: $\mathrm{\forall }x,y,z\in M:(xRy\wedge xRz\Rightarrow yRz)$,
• полнота (или связность): $\mathrm{\forall }x,y\in M:(xRy\vee yRx)$,
• Шаблон:Нп3 (или слабая связность): $\mathrm{\forall }x,y\in M:(x\ne y\Rightarrow xRy\vee yRx)$,
• Шаблон:Нп3: $\mathrm{\forall }x,y\in M$ верно ровно одно из трех утверждений: $xRy$, $yRx$ или $x=y$.

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

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

Виды бинарных отношений

• Обратное отношениеШаблон:Уточнить (отношение, обратное к $R$) — это двуместное отношение, состоящее из пар элементов $(y,x)$, полученных перестановкой пар элементов $(x,y)$ данного отношения $R$. Обозначается: $R^{-1}$. Для данного отношения и обратного ему верно равенство: $(R^{-1}{)}^{-1}=R$.
• Взаимо-обратные отношения (взаимообратные отношения) — отношения, являющиеся обратными друг по отношению к другу. Область значений одного из них служит областью определения другого, а область определения первого — областью значений другого.
• Рефлексивное отношение — двуместное отношение $R$, определённое на некотором множестве и отличающееся тем, что для любого $x$ этого множества элемент $x$ находится в отношении $R$ к самому себе, то есть для любого элемента $x$ этого множества имеет место $xRx$. Примеры рефлексивных отношений: равенство, одновременность, сходство.
• Антирефлексивное отношение (иррефлексивное отношение; так же, как антисимметричность не совпадает с несимметричностью, иррефлексивность не совпадает с нерефлексивностью) — бинарное отношение $R$, определённое на некотором множестве и отличающееся тем, что для любого элемента $x$ этого множества неверно, что оно находится в отношении $R$ к самому себе (неверно, что $xRx$).
• Транзитивное отношение — двуместное отношение $R$, определённое на некотором множестве и отличающееся тем, что для любых $x,y,z$ из $xRy$ и $yRz$ следует $xRz$ ($xRy\wedge yRz\to xRz$). Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
• Нетранзитивное отношениеШаблон:Уточнить — двуместное отношение $R$, определённое на некотором множестве и отличающееся тем, что для любых $x,y,z$ этого множества из $xRy$ и $yRz$ не следует $xRz$ ($\mathrm{\neg }(xRy\wedge yRz\to xRz)$). Пример нетранзитивного отношения: «x отец y»
• Симметричное отношение — бинарное отношение $R$, определённое на некотором множестве и отличающееся тем, что для любых элементов $x$ и $y$ этого множества из того, что $x$ находится к $y$ в отношении $R$, следует, что и $y$ находится в том же отношении к $x$ — $xRy\to yRx$. Примером симметричных отношений могут быть равенство, отношение эквивалентности, подобие, одновременность.
• Антисимметричное отношение — бинарное отношение $R$, определённое на некотором множестве и отличающееся тем, что для любых $x$ и $y$ из $xRy$ и $yRx$ следует $x=y$ (то есть $R$ и $R^{-1}$ выполняются одновременно лишь для равных между собой членов).
• Асимметричное отношение — бинарное отношение $R$, определённое на некотором множестве и отличающееся тем, что для любых $x$ и $y$ из $xRy$ следует $\mathrm{\neg }yRx$. Пример: отношения «больше» (>) и «меньше» (<).
• Отношение эквивалентности — бинарное отношение $R$ между объектами $x$ и $y$, являющееся одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, подобие, одновременность.
• Отношение порядка — отношение, обладающие только некоторыми из трёх свойств отношения эквивалентности: отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует нестрогий порядок, а отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») — строгий порядок.
• Отношение толерантности — бинарное отношение, удовлетворяющее свойствам рефлексивности и симметричности, но не обязательно являющееся транзитивным. Таким образом, отношение эквивалентности является частным случаем толерантности.
• Функция одного переменного — бинарное отношение $R$, определённое на некотором множестве, отличающееся тем, что каждому значению $x$ отношения $xRy$ соответствует лишь единственное значение $y$. Свойство функциональности отношения $R$ записывается в виде аксиомы: $(xRy\wedge xRz)\to (y\equiv z)$.
• Биекция (взаимно-однозначное отношение) — бинарное отношение $R$, определённое на некотором множестве, отличающееся тем, что в нём каждому значению $x$ соответствует единственное значение $y$, и каждому значению $y$ соответствует единственное значение $x$.

Операции над отношениями

Так как отношения, заданные на фиксированной паре множеств $A$ и $B$ суть подмножества множества $A\times B$, то совокупность всех этих отношений образует булеву алгебру относительно операций объединения, пересечения и дополнения отношений. В частности, для произвольных $a\in A$, $b\in B$:

$a(R\cup S)b\iff aRb\vee aSb$,

$a(R\cap S)b\iff aRb\wedge aSb$,

$a\bar{R}b\iff \mathrm{\neg }aRb$.

Часто вместо объединения, пересечения и дополнения отношений говорят об их дизъюнкции, конъюнкции и отрицании.

Например, $(=)\cup (<)=(⩽)$, $(=)\cap (<)=\varnothing$, то есть объединение отношения строгого порядка с отношением равенства совпадает с отношением нестрогого порядка, а их пересечение пусто.

Кроме перечисленных важное значение имеют ещё операции обращения и умножения отношений, определяемые следующим образом. Если $R\subseteq A\times B$, то обратным отношением называется отношение $R^{-1}$, определённое на паре $B$, $A$ и состоящее из тех пар $(b,a)$, для которых $aRb$. Например, $(<{)}^{-1}=(>)$.

Пусть $R\subseteq A\times B$, $S\subseteq B\times C$. Композицией (или произведением) отношений $R$ и $S$ называется отношение $R\circ S\subseteq A\times C$ такое, что:

$a(R\circ S)c\iff \mathrm{\exists }b\in B:a(R)b\wedge b(S)c$.

Например, для отношения строгого порядка на множестве натуральных числе его умножение на себя определено следующим образом: $a(<)(<)b\iff a+1<b$.

Бинарные отношения $R$ и $S$ называются перестановочными, если $RS=SR$. Для любого бинарного отношения $R$, определённого на $A$, имеет место $R{𝖨𝖽}_A={𝖨𝖽}_{A}R$, где символом ${𝖨𝖽}_A$ обозначено равенство, определённое на $A$. Однако равенство $R{R}^{-1}=𝖨𝖽$ не всегда справедливо.

Имеют место следующие тождества:

• $R(ST)=(RS)T$,
• $(RS{)}^{-1}=S^{-1}{R}^{-1}$,
• $\overline{R^{-1}}={\bar{R}}^{-1}$,
• $(R\cup S{)}^{-1}=R^{-1}\cup S^{-1}$,
• $(R\cap S{)}^{-1}=R^{-1}\cap S^{-1}$,
• $R(S\cup T)=RS\cup RT$,
• $(R\cup S)T=RT\cup ST$.

Аналоги последних двух тождеств для пересечения отношений не имеют места.

Литература

• Шаблон:Книга

• Шаблон:Книга

• Шаблон:Книга