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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Бинарное отношение в математике — двухместное отношение между любыми двумя множествами 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\and zRy)\} и обозначается, как R\circ S.

Свойства отношений[править | править вики-текст]

Бинарное отношение R на некотором множестве M может обладать различными свойствами, например:

Виды отношений[править | править вики-текст]

Виды бинарных отношений[править | править вики-текст]

  • Обратное отношение[уточнить] (отношение, обратное к R) — это двухместное отношение, состоящее из пар элементов (y, x), полученных перестановкой пар элементов (x, y) данного отношения R. Обозначается: R^{-1}. Для данного отношения и обратного ему верно равенство: (R^{-1})^{-1} = R.
  • Взаимо-обратные отношения (взаимообратные отношения) — отношения, являющиеся обратными друг по отношению к другу. Область значений одного из них служит областью определения другого, а область определения первого — областью значений другого.
  • Рефлексивное отношение — двухместное отношение R, определённое на некотором множестве и отличаю­щееся тем, что для любого x этого множества элемент x на­ходится в отношении R к самому себе, то есть для любого элемента x этого множества имеет место xRx. Примеры рефлексивных отношений: равенство, одновременность, сходство.
  • Антирефлексивное отношение (иррефлексивное отношение; так же, как антисимметричность не совпадает с несимметричностью, иррефлексивность не совпадает с нерефлексивностью) — бинарное отношение R, определённое на некотором множестве и отличаю­щееся тем, что для любого элемента x этого множества неверно, что оно находится в отношении R к самому себе (неверно, что xRx), то есть возможен случай, что элемент множества не находится в отно­шении R к самому себе.
  • Транзитивное отношение — двухместное отношение 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} = (\geqslant).

Пусть 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.

Например, для отношения строгого порядка на множестве натуральных числе его умножение на себя определено следующим образом: a({<})({<})b \Leftrightarrow a + 1 < b.

Бинарные отношенияR и S называются перестановочными, если RS = SR. Для любого бинарного отношения R, определённого на A, имеет место R\mathsf{Id}_A = \mathsf{Id}_AR, где символом \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.

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

Примечания[править | править вики-текст]

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

Литература[править | править вики-текст]