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

Бина́рное отноше́ние, двуместный предикат на заданном множестве. Под бинарным отношением иногда понимают подмножество множества ${\displaystyle A\times A}$ упорядоченных пар ${\displaystyle (a,b)}$ элементов заданного множества ${\displaystyle A}$. Бинарное отношение – частный случай отношения. Пусть ${\displaystyle R\subseteq A\times A}$. Если ${\displaystyle (a,b)\in R}$, то говорят, что элемент ${\displaystyle a}$ находится в бинарном отношении ${\displaystyle R}$ к элементу ${\displaystyle b}$. Вместо ${\displaystyle (a,b)\in R}$ пишут также ${\displaystyle aRb}$.

Пустое подмножество ${\displaystyle \varnothing }$ в ${\displaystyle A\times A}$ и само множество ${\displaystyle A\times A}$ называется, соответственно, нуль-отношением и универсальным отношением в множестве ${\displaystyle A}$. Диагональ множества ${\displaystyle A\times A}$, т. е. множество ${\displaystyle \Delta =\{(a,a)/a\in A\}}$, есть отношение равенства, или единичное бинарное отношение в ${\displaystyle A}$.

Пусть ${\displaystyle R}$, ${\displaystyle R_{1}}$, ${\displaystyle R_{2}}$ – бинарные отношения в множестве ${\displaystyle A}$. Наряду с теоретико-множественными операциями объединения ${\displaystyle R_{1}\cup R_{2}}$, пересечения ${\displaystyle R_{1}\cap R_{2}}$ и дополнения ${\displaystyle R^{\prime }=(A\times A)\backslash R}$ для бинарного отношения рассматривают также операцию обращения

${\displaystyle R^{-1}=\{(a,b)\mid (b,a)\in R\}}$

и операцию умножения

${\displaystyle R_{1}\circ R_{2}=\left\{(a,b)\mid (\exists c\in A)\left(aR_{1}c{\text{ и }}cR_{2}b\right)\right\}}$.

Бинарное отношение ${\displaystyle R^{-1}}$ называется обратным для ${\displaystyle R}$. Умножение бинарных отношений ассоциативно, но, вообще говоря, не коммутативно.

Бинарное отношение ${\displaystyle R}$ в ${\displaystyle A}$ называется: а) рефлексивным, если ${\displaystyle \Delta \subseteq R}$; б) транзитивным, если ${\displaystyle R\circ R\subseteq R}$; в) симметричным, если ${\displaystyle R^{-1}\subseteq R}$; г) антисимметричным, если ${\displaystyle R\cap R^{-1}\subseteq \Delta }$. Если бинарное отношение ${\displaystyle R}$ обладает некоторым из свойств а), б), в), г), то обратное отношение ${\displaystyle R^{-1}}$ обладает этим же свойством. Бинарное отношение ${\displaystyle R\subseteq A\times A}$ называется функциональным, если ${\displaystyle R^{-1}{\circ }R\subseteq \Delta }$.

Наиболее важными типами бинарного отношения являются эквивалентности, порядки (линейные и частичные) и функциональные отношения.