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

Бина́рное (двухме́стное) отноше́ние (соответствие[1][2]) — отношение между двумя множествами $A$ и $B$ , то есть всякое подмножество декартова произведения этих множеств: $R\subseteq A\times B$ [3]. Бинарное отношение на множестве $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$ и $R$ — это множество $\{(x,\;y)\mid \exists z(xRz\land zSy)\}$ и обозначается, как $R\circ S$ .[4][5]

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

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

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

Примечания

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

Литература

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

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

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Цаленко М. Ш. Соответствие // Математическая энциклопедия. — 1985. — Т. 5 (Слу-Я). — С. 77.

[2] Соответствие (неопр.). Большая российская энциклопедия.

[3] Кострикин А. И. Введение в алгебру. Основы алгебры.. — М.: Физматлит, 1994. — С. 47-48. — 320 с. — ISBN 5-02-014644-7.

[4] Ерусалнмский Я.М. 4. Композиция бинарных отношений. Булево произведение матриц // Дискретная математика: теория, задачи, приложения. — 3-е издание. — М.: Вузовская книга, 2000. — С. 112. — 280 с. — ISBN 5-89522-034-7.

[5] Новиков Ф.А. 1.5.4. Композиция отношений // Дискретная математика для программистов. — СПб.: Питер, 2000. — С. 34. — 304 с. — ISBN 5-272-00183-4.

[autogenerated1-6] Дубов Ю. А., Травкин СИ., Якимец В. Н. Многокритериальные модели формирования и выбора вариантов систем. — М.: Наука, 1986. (с. 48)