В математике бинарным отношением называется подмножество декартова произведения двух множеств. В частности, бинарным отношением на множестве называется непустое^{[источник не указан 215 дней]} множество упорядоченных пар элементов этого множества.

Связанные определения

• называют бинарным отношением на множестве , если . При этом вместо записи часто используют запись
• Если то говорят, что определено на паре множеств и .
• Множество всех первых элементов пар из называется областью определения отношения и обозначается как .

• Множество всех вторых элементов пар из называется областью значения отношения и обозначается как .

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

Свойства отношений

Бинарные отношения могут обладать различными свойствами, такими как

• Рефлексивность: .
• Антирефлексивность (иррефлексивность): .
• Симметричность: .
• Антисимметричность: .
• Транзитивность: .
• Асимметричность: . Асимметричность эквивалентна одновременной антирефлексивности и антисимметричности отношения.

Виды отношений

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

Виды двухместных отношений

• Обратное отношение^{[уточнить]} (отношение, обратное к R) — это двухместное отношение, состоящее из пар элементов (у, х), полученных перестановкой пар элементов (х, у) данного отношения R. Обозначается: R⁻¹. Для данного отношения и обратного ему верно равенство: (R⁻¹)⁻¹ = R.
• Взаимо-обратные отношения (взаимообратные отношения) — отношения, являющиеся обратными друг по отношению к другу. Область значений одного из них служит областью определения другого, а область определения первого — областью значений другого.
• Рефлексивное отношение — двухместное отношение R, определённое на некотором множестве и отличаю­щееся тем, что для любого х этого множества элемент х на­ходится в отношении R к самому себе, то есть для любого элемента х этого множества имеет место xRx. Примеры рефлексивных отношений: равенство, одновременность, сходство.
• Антирефлексивное отношение (Иррефлексивное отношение, отметим, что также как антисимметричность не совпадает с несимметричностью иррефлексивность не совпадает с нерефлексивностью.) — двухместное отношение R, определённое на некотором множестве и отличаю­щееся тем, что для любого элемента х этого множества неверно, что оно находится в отношении R к самому себе (неверно, что xRx), то есть возможен случай, что элемент множества не находится в отно­шении R к самому себе. Примеры нерефлексвных отношений: «заботиться о», «развлекать», «нервировать».
• Транзитивное отношение — двухместное отношение R, оп­ределенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz следует xRz (xRy&yRzxRz). Примеры транзитивных отношений: «больше», «меньше», «равно», «подобно», «выше», «севернее».
• Нетранзитивное отношение^{[уточнить]} — двухместное отношение R, оп­ределенное на некотором множестве и отличающееся тем, что для любых х, у, z этого множества из xRy и yRz не следует xRz ((xRy&yRzxRz)). Пример нетранзитивного отношения: «x отец y»
• Симметричное отношение — двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых элементов х и у этого множества из того, что х находится к у в отношении R (xRy), следует, что и у находится в том же отношении к х (уRx). Примером симметричных отношений могут быть равенство (=), отношение эквивалентности, подобия, одновременности, некоторые отношения родства (например, отношение братства).
• Антисимметричное отношение — двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых х и у из xRy и xR⁻¹y следует х = у (то есть R и R⁻¹ выполняются одновременно лишь для равных между собой членов).
• Асимметричное отношение^{[уточнить]} — двухместное отношение R, определённое на некотором множестве и отличающееся тем, что для любых х и у из xRy следует yRx. Пример: отношение «больше» (>) и «меньше» (<).
• Отношение эквивалентности (отношение тождества^{[уточнить]}, отношение типа равенства) — двухместное отношение R между предметами х и у в предметной области D, удовлетворяющее следующим аксиомам (условиям):
  1. аксиоме рефлексивности (см. выше): xRx (предмет находится в отношении R к само­му себе);
  2. аксиоме симметрич­ности (см. выше): xRyyRx (если предмет х находится в отношении R к пред­мету у, то и у находится в отношении R к х);
  3. аксиоме транзитивности (см. выше): xRy&yRzxRz (если предмет х находится в отношении R к предмету у и у находится в отношении R к z, то х находится в отношении R к г).

  Таким образом, отношение типа равенства является одновременно рефлексивным, симметричным и транзитивным. Примеры: равенство, равномощность двух множеств, обмениваемость товаров на рынке^{[источник не указан 938 дней]}, подобие, одновременность. Пример отношения, которое удовлетворяет аксиоме (3), но не удовлетворяет аксиомам (1) и (2): «больше».

• Отношения порядка — отношения, обладающие только некоторыми из трёх свойств отношения эквивалентности. В частности, отношение рефлексивное и транзитивное, но несимметричное (например, «не больше») образует «нестрогий» порядок. Отношение транзитивное, но нерефлексивное и несимметричное (например, «меньше») — «строгий» порядок.
• Функция — двухместное отношение R, определенное на некотором мно­жестве, отличающееся тем, что каждому значению x отно­шения xRy соответствует лишь одно-единственное значение y. Пример: «y отец x». Свойство функциональности отно­шения R записывается в виде аксиомы: (xRy и xRz)→(y≡z). Поскольку каждому значению x в выражениях xRy и xRz соответствует одно и то же значение, то y и z совпадут, окажутся одними и теми же. Функциональное отношение однозначно, поскольку каждому значению x отношения xRy соответствует лишь одно-единственное значение y, но не наоборот.
• Биекция (одно-однозначное отношение) — двухместное отношение R, определенное на некотором мно­жестве, отличающееся тем, что в нём каждому значению х соответствует единственное значение у, и каждому значению у соответствует единственное значение х. Одно-однозначное отношение является частным случаем однозначного отношения.
• Связанное отношение — это двухместное отношение R, определённое на некотором множестве, отличающееся тем, что для любых двух различных элементов х и у из этого множества, одно из них находится в отношении R к другому (то есть выполнено одно из двух соотношений: xRy или yRx). Пример: отношение «меньше» (<).

Операции над отношениями

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

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

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

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

Если , то обратным отношением называется отношение , определённое на паре , и состоящее из тех пар , для которых . Например, .

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

Если , и , то произведение отношений не определено. Если же отношения рассматривать определённые на каком-то множестве , то такой ситуации не возникает.

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

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

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

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

Отметим, что аналоги последних двух тождеств для не имеют места.

Некоторые свойства отношения можно определить, используя операции над отношениями:

• Рефлексивность: ,
• Симметричность: ,
• Транзитивность: .

См. также

• Теория множеств
• Равенство (математика)
• Сравнение (программирование)

Литература

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