Меню Главная Случайная статья Настройки Бинарное отношение Материал из https://ru.wikipedia.org Бинарное (двуместное) отношение (соответствие[1][2]) — отношение между двумя множествами ${\displaystyle A}$ и ${\displaystyle B}$, то есть всякое подмножество декартова произведения этих множеств: ${\displaystyle R\subseteq A\times B}$[3]. Бинарное отношение на множестве ${\displaystyle A}$ — любое подмножество ${\displaystyle R\subseteq A^{2}=A\times A}$, такие бинарные отношения наиболее часто используются в математике, в частности, таковы равенство, неравенство, эквивалентность, отношение порядка. Содержание 1 Связанные определения 2 Свойства отношений 3 Виды отношений 3.1 Виды бинарных отношений 4 Операции над отношениями 5 Примечания 6 Литература Связанные определения Множество всех первых компонент пар из ${\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\colon (xRx)}$, антирефлексивность (иррефлексивность): ${\displaystyle \forall x\in M\colon \neg (xRx)}$, корефлексивность: ${\displaystyle \forall x,y\in M\colon (xRy\Rightarrow x=y)}$, симметричность: ${\displaystyle \forall x,\;y\in M\colon (xRy\Rightarrow yRx)}$, антисимметричность: ${\displaystyle \forall x,\;y\in M\colon (xRy\wedge yRx\Rightarrow x=y)}$, асимметричность: ${\displaystyle \forall x,\;y\in M\colon (xRy\Rightarrow \neg (yRx))}$, свойство Мура — Смита[7]: ${\displaystyle \forall x,\,y\in M\,\exists z\in M\colon (xRz\wedge yRz)}$, транзитивность: ${\displaystyle \forall x,\;y,\;z\in M\colon (xRy\wedge yRz\Rightarrow xRz)}$, евклидовость: ${\displaystyle \forall x,y,z\in M\colon (xRy\wedge xRz\Rightarrow yRz)}$, полнота (или связность[8]): ${\displaystyle \forall x,y\in M\colon (xRy\lor yRx)}$, связность[англ.] (или слабая связность[8]): ${\displaystyle \forall x,y\in M\colon (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}$ и ${\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}$. Аналоги последних двух тождеств для пересечения отношений не имеют места. Примечания Цаленко М. Ш. Соответствие // Математическая энциклопедия. — 1985. — Т. 5 (Слу-Я). — С. 77. Соответствие  (неопр.). Большая российская энциклопедия. Дата обращения: 1 мая 2023. Архивировано 4 февраля 2023 года. Кострикин А. И. Введение в алгебру. Основы алгебры.. — М.: Физматлит, 1994. — С. 47-48. — 320 с. — ISBN 5-02-014644-7. 1 2 Пономарёв В. И. Направление, 1982. 1 2 Дубов Ю. А., Травкин СИ., Якимец В. Н. Многокритериальные модели формирования и выбора вариантов систем. — М.: Наука, 1986. (с. 48) Литература