Recall that an $n$ -ary relation ($n>0$ ) is a subset of a product of some $n$ sets. In this definition, any $n$ -ary relation for which $n>1$ is automatically an $(n-1)$ -ary relation, and consequently a binary relation. On the other hand, a unary, or $1$ -ary relation, being the subset $B$ of some set $A$ , can be viewed as a binary relation (either realized as $B\times B$ or $\Delta_B:=\lbrace (b,b)\mid b\in B\rbrace$ ) on $A$ . Hence, we shall concentrate our discussion on the most important kind of relations, the binary relations, in this entry.

Compositions, Inverses, and Complements

Let $\rho \subseteq A\times B$ and $\sigma \subseteq B\times C$ be two binary relations. We define the composition of $\rho$ and $\sigma$ , the inverse (or converse) and the complement of $\rho$ by

• $\rho\circ\sigma := \lbrace (a,c)\mid (a,b)\in \rho \mbox{ and }(b,c)\in \sigma \mbox{ for some } b\in B\rbrace$ ,
• $\rho^{-1}:=\lbrace (b,a)\mid (a,b)\in \rho\rbrace$ , and
• $\rho':=\lbrace (a,b)\mid (a,b)\notin \rho\rbrace$ .

Properties. Suppose $\rho,\sigma,\tau$ are binary relations of $A\times B,B\times C,C\times D$ respectively.

1. Associativity of relational compositions: $(\rho\circ\sigma)\circ \tau =\rho\circ (\sigma\circ\tau)$ .
2. $(\rho\circ\sigma)^{-1}=\sigma^{-1}\circ\rho^{-1}$ .
3. For the rest of the remarks, we assume $A=B$ . Define the power of $\rho$ recursively by $\rho^1=\rho$ , and $\rho^{n+1}=\rho\circ\rho^n$ . By 1 above, $\rho^{n+m}=\rho^n\circ\rho^m$ for $m,n\in \mathbb{N}$ .
4. $\rho^{-n}$ may be also be defined, in terms of $\rho^{-1}$ for $n>0$ .
5. However, $\rho^{n+m}\ne\rho^n\circ\rho^m$ for all integers, since $\rho^{-1}\circ\rho\neq \rho\circ\rho^{-1}$ in general.
6. Nevertheless, we may define $\Delta:=\lbrace (a,a)\mid a\in A\rbrace$ . This is called the identity or diagonal relation on $A$ . It has the property that $\Delta\circ \rho=\rho\circ\Delta=\rho$ . For this, we may define, for every relation $\rho$ on $A$ , $\rho^0:=\Delta$ .
7. Let $\mathcal{R}$ be the set of all binary relations on a set $A$ . Then $(\mathcal{R},\circ)$ is a monoid with $\Delta$ as the identity element.

Let $\rho$ be a binary relation on a set $A$ , below are some special relations definable from $\rho$ :

• $\rho$ is reflexive if $\Delta\subseteq\rho$ ;
• $\rho$ is symmetric if $\rho=\rho^{-1}$ ;
• $\rho$ is anti-symmetric if $\rho\cap\rho^{-1}\subseteq \Delta$ ;
• $\rho$ is transitive if $\rho\circ\rho \subseteq \rho$ ;
• $\rho$ is a pre-order if it is reflexive and transitive
• $\rho$ is a partial order if it is a pre-order and is anti-symmetric
• $\rho$ is an equivalence if it is a pre-order and is symmetric

Other Operations

Some operations on binary relations yield unary relations. The most common ones are the following:

Given a binary relation $\rho\in A\times B$ , and an elements $a\in A$ and $b\in B$ , define $$\rho(a,\cdot):=\lbrace y\mid (a,y)\in \rho\rbrace \quad\mbox{ and }\quad \rho(\cdot,b):=\lbrace x\mid (x,b)\in \rho\rbrace.$$

$\rho(a,\cdot)\subseteq B$ is called the section of $\rho$ in $B$ based at $a$ , and $\rho(\cdot,b)\subseteq A$ is the section of $\rho$ in $A$ (based) at $b$ . When the base points are not mentioned, we simply say a section of $\rho$ in $A$ or $B$ , or an $A$ -section or a $B$ -section of $\rho$ .

Finally, we define the domain and range of a binary relation $\rho\subseteq A\times B$ , to be

• $\operatorname{dom}(\rho):=\lbrace a\mid (a,b)\in \rho \mbox{ for some } b\in B\rbrace$ , and
• $\operatorname{ran}(\rho):=\lbrace b\mid (a,b)\in \rho \mbox{ for some } a\in A\rbrace.$

Remarks. Given a binary relation $\rho\subseteq A\times B$ .

1. $\rho(a,\cdot)$ , realized as a binary relation $\lbrace a\rbrace \times \rho(a,\cdot)$ can be viewed as the composition of $\Delta_a\circ \rho$ , where $\Delta_a=\lbrace (a,a)\rbrace$ . Similarly, $\rho\circ \Delta_b=\rho(\cdot,b) \times \lbrace b\rbrace$ .
2. $\operatorname{dom}(\rho)$ is the disjoint union of $A$ -sections of $\rho$ and $\operatorname{ran}(\rho)$ is the disjoint union of $B$ -sections of $\rho$ .
3. $\operatorname{dom}(\rho^{-1})=\operatorname{ran}(\rho)$ and $\operatorname{ran}(\rho^{-1})=\operatorname{dom}(\rho)$ .
4. $\rho\circ\rho^{-1}=\operatorname{dom}(\rho)\times \operatorname{dom}(\rho)$ and $\rho^{-1}\circ\rho=\operatorname{ran}(\rho)\times \operatorname{ran}(\rho)$ .
5. If $A=B$ , then $\operatorname{dom}(\rho)\times A=\rho\circ A^2$ and $\operatorname{ran}(\rho) = A^2\circ \rho$ .
6. The composition of binary relations can be generalized: let $R$ be a subset of $A_1\times \cdots \times A_n$ and $S$ be a subset of $B_1\times \cdots \times B_m$ , where $m,n$ are positive integers. Further, we assume that $A_n=B_1=C$ . Define $R\circ S$ , as a subset of $A_1\times \cdots \times A_{n-1} \times B_2 \times \cdots B_m$ , to be the set $$\lbrace (a_1, \ldots, a_{n-1}, b_2, \ldots, b_m) \mid \exists c\in C \mbox{ with }(a_1, \ldots, a_{n-1}, c)\in R\mbox{ and }(c, b_2, \ldots, b_m) \in S\rbrace.$$ If $m=n=2$ , then we have the familiar composition of binary relations. If $m=1$ and $n=2$ , then $R\circ S=\lbrace a \mid (a,c)\in R\mbox{ and }c \in S\rbrace$ . The case where $m=2$ and $n=1$ is similar. If $m=n=1$ , then $R\circ S = \lbrace \mbox{ true }\rbrace$ if $R\cap S\ne \varnothing$ . Otherwise, it is set to $\lbrace \mbox{ false }\rbrace$ .