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

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

В математике бинарным отношением между любыми двумя множествами X и Y (или просто на X, если Y = X) называется всякое подмножество \omega декартова произведения этих множеств: \omega \subset X \times Y. [1]

Связанные определения[править | править вики-текст]

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

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

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

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

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

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

См. также[править | править вики-текст]

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

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

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

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