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

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

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

Свойства отношений 
Бинарное отношение  на некотором множестве  может обладать различными свойствами, например:
 рефлексивность: ,
 антирефлексивность (иррефлексивность): ,
 корефлексивность: ,
 симметричность: ,
 антисимметричность: ,
 асимметричность: ,
 транзитивность: ,
 евклидовость: ,
 полнота (или связность): ,
  (или слабая связность): ,
 :  верно ровно одно из трех утверждений: ,  или .

Виды отношений 
 Рефлексивное транзитивное отношение называется отношением квазипорядка.
 Рефлексивное симметричное транзитивное отношение называется отношением эквивалентности.
 Рефлексивное антисимметричное транзитивное отношение называется отношением (частичного) порядка.
 Антирефлексивное антисимметричное транзитивное отношение называется отношением строгого порядка.
 Полное антисимметричное (для любых  выполняется  или ) транзитивное отношение называется отношением линейного порядка.
 Антирефлексивное антисимметричное отношение называется отношением доминирования.

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

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

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

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

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

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

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

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

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

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

Примечания

Литература 
 

 

 

Математические отношения