WikiSort.ru - Не сортированное

ПОИСК ПО САЙТУ | о проекте

Бина́рное (двухместное) отноше́ние — отношение между двумя множествами $A$ и $B$ , то есть всякое подмножество декартова произведения этих множеств: $R\subseteq A\times B$ ^[1]. Бинарное отношение на множестве $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(xSz\land zRy)\}$ и обозначается, как $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)$ ,
полнота (или связность^[2]): $\forall x,y\in M(xRy\lor yRx)$ ,
связность (или слабая связность^[2]): $\forall x,y\in M(x\neq y\Rightarrow xRy\lor yRx)$ ,
коннексность (англ. connex): $\forall x,y\in M(xRy\lor yRx\lor x=y)$ ,
трихотомия: $\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$ .
Связанное отношение — бинарное отношение $R$ , определённое на некотором множестве, отличающееся тем, что для любых двух различных элементов $x$ и $y$ из этого множества, одно из них находится в отношении $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$ называется отношение $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$ .

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

Примечания

↑ Кострикин А. И. Введение в алгебру. Основы алгебры.. — М.: Физматлит, 1994. — С. 47-48. — 320 с. — ISBN 5-02-014644-7.
1 2 Дубов Ю. А., Травкин СИ., Якимец В. Н. Многокритериальные модели формирования и выбора вариантов систем. — М.: Наука, 1986. (с. 48)

Литература

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

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

Учебник: Математика без формул (Ю.В. Пухначев, Ю.П. Попов, 1995)

Ссылки

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .

Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии

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

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