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

У этого термина существуют и другие значения, см. Отношение.

В математике бинарным отношением называется подмножество декартова произведения двух множеств. В частности, бинарным отношением на множестве называется непустое^{[источник не указан 323 дня]} множество упорядоченных пар элементов этого множества.

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

• $R$ называют бинарным отношением на множестве $A$, если $R\subset A\times A$. При этом вместо записи $(x,\;y)\in R$ часто используют запись $xRy.$
• Если $R\subset A\times B,$ то говорят, что $R$ определено на паре множеств $A$ и $B$.
• Множество всех первых элементов пар из $R$ называется областью определения отношения $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(xSz\and zRy)\}$ и обозначается, как $R\circ S$.

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

Бинарные отношения могут обладать различными свойствами, такими как

• Рефлексивность: $\forall x\in M(xRx)$.
• Антирефлексивность (иррефлексивность): $\forall x\in M \neg(xRx)$.
• Симметричность: $\forall x,\;y\in M(xRy\Rightarrow yRx)$.
• Антисимметричность: $\forall x,\;y\in M(xRy\wedge yRx\Rightarrow x=y)$.
• Транзитивность: $\forall x,\;y,\;z\in M(xRy\wedge yRz\Rightarrow xRz)$.
• Асимметричность: $\forall x,\;y\in M(xRy\Rightarrow\neg(yRx))$. Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.

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

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

Виды двухместных отношений

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

  Таким образом, отношение типа равенства является одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, обмениваемость товаров на рынке^{[источник не указан 1046 дней]}, подобие, одновременность. Пример отношения, которое удовлетворяет аксиоме (3), но не удовлетворяет аксиомам (1) и (2): «больше».

• Отношения порядка — отношения, обладающие только некоторыми из трёх свойств отношения эквивалентности. В частности, отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует «нестрогий» порядок. Отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») — «строгий» порядок.
• Функция — двухместное отношение R, определенное на некотором мно­жестве, отличающееся тем, что каждому значению x отно­шения xRy соответствует лишь одно-единственное значение y. Пример: «y отец x». Свойство функциональности отно­шения R записывается в виде аксиомы: (xRy и xRz)→(y≡z). Поскольку каждому значению x в выражениях xRy и xRz соответствует одно и то же значение, то y и z совпадут, окажутся одними и теми же. Функциональное отношение однозначно, поскольку каждому значению x отношения xRy соответствует лишь одно-единственное значение y, но не наоборот.
• Биекция (одно-однозначное отношение) — двухместное отношение R, определенное на некотором мно­жестве, отличающееся тем, что в нём каждому значению х соответствует единственное значение у, и каждому значению у соответствует единственное значение х. Одно-однозначное отношение является частным случаем однозначного отношения.
• Связанное отношение — это двухместное отношение R, определённое на некотором множестве, отличающееся тем, что для любых двух различных элементов х и у из этого множества, одно из них находится в отношении R к другому (то есть выполнено одно из двух соотношений: xRy или yRx). Пример: отношение «меньше» (<).

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

Так как отношения, заданные на фиксированной паре множеств $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$ называется отношение $RS \subseteq A \times C$ такое, что

$a \, RS \, c \Leftrightarrow \exists b \in B \, a \, R \, b \wedge b \, S \, c.$

Если $R \subseteq A \times B$, $S \subseteq C \times D$ и $B \neq C$, то произведение отношений не определено. Если же отношения рассматривать определённые на каком-то множестве $A$, то такой ситуации не возникает.

Например, рассмотрим отношение строгого порядка $<$ определённого на множестве натуральных чисел. Несложно заметить, что

$a \,{<}{<} b \Leftrightarrow a + 1 < b.$

Бинарные отношения$R$ и $S$ называются перестановочными, если $RS = SR$. Несложно заметить, что для любого бинарного отношения $R$, определённого на $A$, $RI_A = I_AR$, где символом $I_A$ обозначено равенство, определённое на $A$. Однако равенство $RR^{-1} = I$ не всегда справедливо.

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

• $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$.

Отметим, что аналоги последних двух тождеств для $\cap$ не имеют места.

Некоторые свойства отношения $R \subseteq A \times A$ можно определить, используя операции над отношениями:

• Рефлексивность: $I \subseteq R$,
• Симметричность: $R^{-1} \subseteq R$,
• Транзитивность: $RR \subseteq R$.

См. также

• Теория множеств
• Равенство (математика)
• Сравнение (программирование)

Литература

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