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

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

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

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

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

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

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

• Инверсия (обратное отношение) $R$ — это множество $\{(x,\;y)\mid (y,\;x)\in R\}$ и обозначается, как $R^{-1}$.
• Композиция (суперпозиция) бинарных отношений $R$ и $S$ — это множество $\{(x,\;y)\mid \exists z(xRz\land zSy)\}$ и обозначается, как $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,z\in M:(xRy\wedge xRz\Rightarrow yRz)$,
• полнота (или связность): $\forall x,y\in M:(xRy\lor yRx)$,
• связность (или слабая связность): $\forall x,y\in M:(x\neq y\Rightarrow xRy\lor yRx)$,
• трихотомия: $\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$ ($\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$ следует $\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\Leftrightarrow a\,R\,b\vee a\,S\,b$,

$a\,(R\cap S)\,b\Leftrightarrow a\,R\,b\wedge a\,S\,b$,

$a\,{\overline {R}}\,b\Leftrightarrow \neg a\,R\,b$.

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

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

Кроме перечисленных важное значение имеют ещё операции обращения и умножения отношений, определяемые следующим образом. Если $R\subseteq A\times B$, то обратным отношением называется отношение $R^{-1}$, определённое на паре $B$, $A$ и состоящее из тех пар $(b,a)$, для которых $a\,R\,b$. Например, $({<})^{-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\Leftrightarrow \exists b\in B:\,a\,(R)\,b\wedge b\,(S)\,c$.

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

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

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

• $R(ST)=(RS)T$,
• $(RS)^{-1}=S^{-1}R^{-1}$,
• ${\overline {R^{-1}}}={\overline {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$.

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

Литература

• Мальцев, А. И. Алгебраические системы. — М.: Наука, 1970. — 392 с. — 17 500 экз.

• Алескеров Ф.Т., Хабина Э.Л., Шварц Д.А. Бинарные отношения, графы и коллективные решения. — М.: Учебники Высшей школы экономики, 2006. — 300 с.

• Пухначев Ю. В., Попов Ю. П. Кн. 1: Множества, отображения, отношения, последовательности, ряды, функции, свойства функций, дифференциальное и интегральное исчисление, функции многих переменных // Математика без формул. — Изд. 6-е, испр. — М.: URSS, 2017. — 231 с. — ISBN 978-5-9710-3871-9.