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

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

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

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

${\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)\}.}$^[4]

• Инверсия (обратное отношение) ${\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}$.^[5][6]

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

Бинарное отношение ${\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)}$,
• полнота (или связность^[7]): ${\displaystyle \forall x,y\in M:(xRy\lor yRx)}$,
• связность^[англ.] (или слабая связность^[7]): ${\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}$.

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

Примечания

1. Цаленко М. Ш. Соответствие // Математическая энциклопедия. — 1985. — Т. 5 (Слу-Я). — С. 77.
2. Соответствие  (неопр.). Большая российская энциклопедия. Дата обращения: 1 мая 2023. Архивировано 4 февраля 2023 года.
3. Кострикин А. И. Введение в алгебру. Основы алгебры.. — М.: Физматлит, 1994. — С. 47-48. — 320 с. — ISBN 5-02-014644-7.
4. Куликов Л.Я. Глава вторая. Множества и отношения // Алгебра и теория чисел: Учеб. пособие для педагогических институтов. — М.: Высшая школа, 1979. — С. 50. — 559 с.
5. Ерусалимский Я.М. 4. Композиция бинарных отношений. Булево произведение матриц // Дискретная математика: теория, задачи, приложения. — 3-е издание. — М.: Вузовская книга, 2000. — С. 112. — 280 с. — ISBN 5-89522-034-7.
6. Новиков Ф.А. 1.5.4. Композиция отношений // Дискретная математика для программистов. — СПб.: Питер, 2000. — С. 34. — 304 с. — ISBN 5-272-00183-4.
7. Дубов Ю. А., Травкин СИ., Якимец В. Н. Многокритериальные модели формирования и выбора вариантов систем. — М.: Наука, 1986. (с. 48)

Литература

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

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

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