You are here
Homeoperations on relations
Primary tabs
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 $(n1)$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. 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}}\neq\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:=\{(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. 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 antisymmetric if $\rho\cap\rho^{{1}}\subseteq\Delta$;

$\rho$ is transitive if $\rho\circ\rho\subseteq\rho$;

$\rho$ is a preorder if it is reflexive and transitive

$\rho$ is a partial order if it is a preorder and is antisymmetric

$\rho$ is an equivalence if it is a preorder and is symmetric
Of these, only reflexivity is preserved by $\circ$ and both symmetry and antisymmetry 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. $\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. $\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_{{n1}}\times B_{2}\times\cdots B_{m}$, to be the set
$\{(a_{1},\ldots,a_{{n1}},b_{2},\ldots,b_{m})\mid\exists c\in C\mbox{ with }(a% _{1},\ldots,a_{{n1}},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 }\}$.
Mathematics Subject Classification
08A02 no label found03E20 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections