Binary relation

The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

2020 Mathematics Subject Classification: Primary: 03-XX [MSN][ZBL]

A two-place predicate on a given set. The term is sometimes used to denote a subset of the set $A\times A$ of ordered pairs $(a,b)$ of elements of a given set $A$. A binary relation is a special case of a relation. Let $R\subseteq A\times A$. If $(a,b)\in R$, then one says that the element $a$ is in binary relation $R$ to the element $b$. An alternative notation for $(a,b)\in R$ is $aRb$.

The empty subset $\emptyset$ in $A\times A$ and the set $A\times A$ itself are called, respectively, the nil relation and the universal relation in the set $A$. The diagonal of the set $A\times A$, i.e. the set $\Delta=\{(a,a)\colon a\in A\}$, is the equality relation or the identity binary relation in $A$.

Let $R,R_1,R_2$ be binary relations in a set $A$. In addition to the set-theoretic operations of union $R_1\cup R_2$, intersection $R_1\cap R_2$, and negation or complementation $R'=(A\times A)\setminus R$, one has the inversion (also inverse, converse or transpose)

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

as well as the operation of multiplication (or composition):

$$R_1\circ R_2=\{(a,c) \in A\times A\colon(\exists b\in A)(aR_1b\text{ and }bR_2c)\}.$$

Multiplication of binary relations is associative, but as a rule not commutative.

A binary relation $R$ in $A$ is said to be 1) reflexive if $\Delta\subseteq R$; 2) transitive if $R\circ R\subseteq R$; 3) symmetric if $R^{-1}\subseteq R$; and 4) anti-symmetric if $R\cap R^{-1}\subseteq\Delta$. If a binary relation has some of the properties 1), 2), 3) or 4), the inverse relation $R^{-1}$ has these properties as well. The binary relation $R\subseteq A\times A$ is said to be functional if $R^{-1}\circ R\subseteq\Delta$.

The most important types of binary relations are equivalences, order relations (total and partial), and functional relations.

More generally, a binary relation $R$ may be defined between two sets $A$ and $B$ as a two-place predicate or realised as a subset of the Cartesian product $A \times B$. As before we may speak of the union, intersection or negation of $R$ as a relation on $A \times B$. The transpose $R^t$ is now a relation on $B \times A$. Given relations $R_1$ on $A\times B$ and $R_2$ on $B\times C$, the composition $R_1 \circ R_2$ is a relation on $A \times C$:

$$R_1\circ R_2=\{(a,c) \in A \times C\colon(\exists b\in B)(aR_1b\text{ and }bR_2c)\}.$$

A relation $R$ on $A\times B$ is functional if for each $a \in A$ there is at most one $b \in B$ such that $a R b$. Such a relation defines a (partial) function from $A$ to $B$: cf. Functional relation.

References

 [a1] P. R. Halmos, Naive Set Theory, Springer (1960) ISBN 0-387-90092-6

The set $\mathcal{R}(A)$ of binary relations on $A$ form a monoid under composition of relations with the equality relation as identity element and the empty relation as a zero; indeed, it is a Baer semigroup.