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

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

Бина́рное отноше́ние — двухместное отношение между любыми двумя множествами и , то есть всякое подмножество декартова произведения этих множеств: [1]. Бинарное отношение на множестве  — любое подмножество , такие бинарные отношения наиболее часто используются в математике, в частности, таковы равенство, неравенство, эквивалентность, отношение порядка.

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

  • Множество всех первых компонент пар из называется областью определения отношения и обозначается как .
  • Множество всех вторых компонент пар из называется областью значения отношения и обозначается как .
  • Инверсия (обратное отношение)  — это множество и обозначается, как .
  • Композиция (суперпозиция) бинарных отношений и  — это множество и обозначается, как .

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

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

  • рефлексивность: ,
  • антирефлексивность (иррефлексивность): ,
  • корефлексивность: ,
  • симметричность: ,
  • антисимметричность: ,
  • асимметричность: , эквивалентна одновременной антирефлексивности и антисимметричности отношения,
  • транзитивность: ,
  • евклидовость: ,
  • полнота (или связность[2]): ,
  • связность (или слабая связность[2]): ,
  • коннексность (англ. connex): ,
  • трихотомия: верно ровно одно из трех утверждений: , или .

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

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

  • Обратное отношение[уточнить] (отношение, обратное к ) — это двухместное отношение, состоящее из пар элементов , полученных перестановкой пар элементов данного отношения . Обозначается: . Для данного отношения и обратного ему верно равенство: .
  • Взаимо-обратные отношения (взаимообратные отношения) — отношения, являющиеся обратными друг по отношению к другу. Область значений одного из них служит областью определения другого, а область определения первого — областью значений другого.
  • Рефлексивное отношение — двухместное отношение , определённое на некотором множестве и отличаю­щееся тем, что для любого этого множества элемент на­ходится в отношении к самому себе, то есть для любого элемента этого множества имеет место . Примеры рефлексивных отношений: равенство, одновременность, сходство.
  • Антирефлексивное отношение (иррефлексивное отношение; так же, как антисимметричность не совпадает с несимметричностью, иррефлексивность не совпадает с нерефлексивностью) — бинарное отношение , определённое на некотором множестве и отличаю­щееся тем, что для любого элемента этого множества неверно, что оно находится в отношении к самому себе (неверно, что ), то есть возможен случай, что элемент множества не находится в отно­шении к самому себе.
  • Транзитивное отношение — двухместное отношение , оп­ределённое на некотором множестве и отличающееся тем, что для любых из и следует (). Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
  • Нетранзитивное отношение[уточнить] — двухместное отношение , оп­ределённое на некотором множестве и отличающееся тем, что для любых этого множества из и не следует (). Пример нетранзитивного отношения: «x отец y»
  • Симметричное отношение — бинарное отношение , определённое на некотором множестве и отличающееся тем, что для любых элементов и этого множества из того, что находится к в отношении , следует, что и находится в том же отношении к  — . Примером симметричных отношений могут быть равенство, отношение эквивалентности, подобие, одновременность.
  • Антисимметричное отношение — бинарное отношение , определённое на некотором множестве и отличающееся тем, что для любых и из и следует (то есть и выполняются одновременно лишь для равных между собой членов).
  • Асимметричное отношение — бинарное отношение , определённое на некотором множестве и отличающееся тем, что для любых и из следует . Пример: отношения «больше» (>) и «меньше» (<).
  • Отношение эквивалентности — бинарное отношение между объектами и , являющееся одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, подобие, одновременность.
  • Отношение порядка — отношение, обладающие только некоторыми из трёх свойств отношения эквивалентности: отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует нестрогий порядок, а отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») — строгий порядок.
  • Функция одного переменного — бинарное отношение , определённое на некотором мно­жестве, отличающееся тем, что каждому значению отно­шения соответствует лишь единственное значение . Свойство функциональности отно­шения записывается в виде аксиомы: .
  • Биекция (взаимно-однозначное отношение) — бинарное отношение , определённое на некотором мно­жестве, отличающееся тем, что в нём каждому значению соответствует единственное значение , и каждому значению соответствует единственное значение .
  • Связанное отношение — бинарное отношение , определённое на некотором множестве, отличающееся тем, что для любых двух различных элементов и из этого множества, одно из них находится в отношении к другому (то есть выполнено одно из двух соотношений: или ). Пример: отношение «меньше» (<).

Операции над отношениями[править | править вики-текст]

Так как отношения, заданные на фиксированной паре множеств и суть подмножества множества , то совокупность всех этих отношений образует булеву алгебру относительно операций объединения, пересечения и дополнения отношений. В частности, для произвольных , :

,
,
.

Часто вместо объединения, пересечения и дополнения отношений говорят об их дизъюнкции, конъюнкции и отрицании.

Например, , , то есть объединение отношения строгого порядка с отношением равенства совпадает с отношением нестрогого порядка, а их пересечение пусто.

Кроме перечисленных важное значение имеют ещё операции обращения и умножения отношений, определяемые следующим образом. Если , то обратным отношением называется отношение , определённое на паре , и состоящее из тех пар , для которых . Например, .

Пусть , . Композицией (или произведением) отношений и называется отношение такое, что:

.

Например, для отношения строгого порядка на множестве натуральных числе его умножение на себя определено следующим образом: .

Бинарные отношения и называются перестановочными, если . Для любого бинарного отношения , определённого на , имеет место , где символом обозначено равенство, определённое на . Однако равенство не всегда справедливо.

Имеют место следующие тождества:

  • ,
  • ,
  • ,
  • ,
  • ,
  • ,
  • .

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

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

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

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