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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle a\,(R\cup S)\,b\Leftrightarrow a\,R\,b\vee a\,S\,b}$ ,

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

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

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

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

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

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

${\displaystyle a\,(R\circ S)\,c\Leftrightarrow \exists b\in B:\,a\,(R)\,b\wedge b\,(S)\,c}$ .

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

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

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

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

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

Примечания

Литература

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

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

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