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 ${\mathrm{\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 \text{and}(b,c)\in \sigma \text{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}\ne {\rho}^{n}\circ {\rho}^{m}$ for all integers, since ${\rho}^{1}\circ \rho \ne \rho \circ {\rho}^{1}$ in general.

6.
Nevertheless, we may define $\mathrm{\Delta}:=\{(a,a)\mid a\in A\}$. This is called the identity^{} or diagonal relation on $A$. It has the property that $\mathrm{\Delta}\circ \rho =\rho \circ \mathrm{\Delta}=\rho $. For this, we may define, for every relation $\rho $ on $A$, ${\rho}^{0}:=\mathrm{\Delta}$.

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 $\mathrm{\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 $\mathrm{\Delta}\subseteq \rho $;

•
$\rho $ is symmetric^{} if $\rho ={\rho}^{1}$;

•
$\rho $ is antisymmetric if $\rho \cap {\rho}^{1}\subseteq \mathrm{\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 \}\mathit{\hspace{1em}}\text{and}\mathit{\hspace{1em}}\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

•
$\mathrm{dom}(\rho ):=\{a\mid (a,b)\in \rho \text{for some}b\in B\}$, and

•
$\mathrm{ran}(\rho ):=\{b\mid (a,b)\in \rho \text{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 ${\mathrm{\Delta}}_{a}\circ \rho $, where ${\mathrm{\Delta}}_{a}=\{(a,a)\}$. Similarly, $\rho \circ {\mathrm{\Delta}}_{b}=\rho (\cdot ,b)\times \{b\}$.

2.
$\mathrm{dom}(\rho )$ is the disjoint union^{} of $A$sections of $\rho $ and $\mathrm{ran}(\rho )$ is the disjoint union of $B$sections of $\rho $.

3.
$\mathrm{dom}({\rho}^{1})=\mathrm{ran}(\rho )$ and $\mathrm{ran}({\rho}^{1})=\mathrm{dom}(\rho )$.

4.
$\rho \circ {\rho}^{1}=\mathrm{dom}(\rho )\times \mathrm{dom}(\rho )$ and ${\rho}^{1}\circ \rho =\mathrm{ran}(\rho )\times \mathrm{ran}(\rho )$.

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

6.
The composition of binary relations can be generalized: let $R$ be a subset of ${A}_{1}\times \mathrm{\cdots}\times {A}_{n}$ and $S$ be a subset of ${B}_{1}\times \mathrm{\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 \mathrm{\cdots}\times {A}_{n1}\times {B}_{2}\times \mathrm{\cdots}{B}_{m}$, to be the set
$$\{({a}_{1},\mathrm{\dots},{a}_{n1},{b}_{2},\mathrm{\dots},{b}_{m})\mid \exists c\in C\text{with}({a}_{1},\mathrm{\dots},{a}_{n1},c)\in R\text{and}(c,{b}_{2},\mathrm{\dots},{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\text{and}c\in S\}$. The case where $m=2$ and $n=1$ is similar^{}. If $m=n=1$, then $R\circ S=\{\text{true}\}$ if $R\cap S\ne \mathrm{\varnothing}$. Otherwise, it is set to $\{\text{false}\}$.
Title  operations on relations 
Canonical name  OperationsOnRelations 
Date of creation  20130322 16:26:40 
Last modified on  20130322 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 