# operations on relations

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}:=\{(b,b)\mid b\in B\}$) 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:=\{(a,c)\mid(a,b)\in\rho\mbox{ and }(b,c)\in\sigma\mbox{ for % some }b\in B\}$,

• $\rho^{-1}:=\{(b,a)\mid(a,b)\in\rho\}$, and

• $\rho^{\prime}:=\{(a,b)\mid(a,b)\notin\rho\}$.

$\rho\circ\sigma,\rho^{-1}$ and $\rho^{\prime}$ are binary relations of $A\times C,B\times A$ and $A\times B$ respectively.

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

1. 1.

Associativity of relational compositions: $(\rho\circ\sigma)\circ\tau=\rho\circ(\sigma\circ\tau)$.

2. 2.

$(\rho\circ\sigma)^{-1}=\sigma^{-1}\circ\rho^{-1}$.

3. 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. 4.

$\rho^{-n}$ may be also be defined, in terms of $\rho^{-1}$ for $n>0$.

5. 5.

However, $\rho^{n+m}\neq\rho^{n}\circ\rho^{m}$ for all integers, since $\rho^{-1}\circ\rho\neq\rho\circ\rho^{-1}$ in general.

6. 6.

Nevertheless, we may define $\Delta:=\{(a,a)\mid a\in A\}$. 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. 7.

Let $\mathcal{R}$ be the set of all binary relations on a set $A$. Then $(\mathcal{R},\circ)$ is a monoid (http://planetmath.org/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

Of these, only reflexivity is preserved by $\circ$ and both symmetry and anti-symmetry are preserved by the inverse operation.

## 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):=\{y\mid(a,y)\in\rho\}\quad\mbox{ and }\quad\rho(\cdot,b):=\{x% \mid(x,b)\in\rho\}.$

$\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):=\{a\mid(a,b)\in\rho\mbox{ for some }b\in B\}$, and

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

respectively. When $\rho$ is a function, the domain and range of $\rho$ coincide with the domain of range of $\rho$ as a function.

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

1. 1.

$\rho(a,\cdot)$, realized as a binary relation $\{a\}\times\rho(a,\cdot)$ can be viewed as the composition of $\Delta_{a}\circ\rho$, where $\Delta_{a}=\{(a,a)\}$. Similarly, $\rho\circ\Delta_{b}=\rho(\cdot,b)\times\{b\}$.

2. 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. 3.

$\operatorname{dom}(\rho^{-1})=\operatorname{ran}(\rho)$ and $\operatorname{ran}(\rho^{-1})=\operatorname{dom}(\rho)$.

4. 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. 5.

If $A=B$, then $\operatorname{dom}(\rho)\times A=\rho\circ A^{2}$ and $\operatorname{ran}(\rho)=A^{2}\circ\rho$.

6. 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

 $\{(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\}.$

If $m=n=2$, then we have the familiar composition of binary relations. If $m=1$ and $n=2$, then $R\circ S=\{a\mid(a,c)\in R\mbox{ and }c\in S\}$. The case where $m=2$ and $n=1$ is similar. If $m=n=1$, then $R\circ S=\{\mbox{ true }\}$ if $R\cap S\neq\varnothing$. Otherwise, it is set to $\{\mbox{ false }\}$.

 Title operations on relations Canonical name OperationsOnRelations Date of creation 2013-03-22 16:26:40 Last modified on 2013-03-22 16:26:40 Owner CWoo (3771) Last modified by CWoo (3771) Numerical id 14 Author CWoo (3771) Entry type Definition Classification msc 08A02 Classification msc 03E20 Synonym inverse relation Synonym relation composition Synonym converse of a relation Synonym diagonal relation Related topic GeneralAssociativity Related topic RelationAlgebra Defines power of a relation Defines relational composition Defines inverse of a relation Defines section Defines domain Defines range Defines identity relation