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 ${\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 $ℛ$ be the set of all binary relations on a set $A$. Then $(ℛ,\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 anti-symmetric if $\rho \cap {\rho }^{-1}\subseteq \mathrm{\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 \}\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_{n-1}\times B_2\times \mathrm{\cdots }{B}_m$, to be the set

   $$\{(a_1,\mathrm{\dots },a_{n-1},b_2,\mathrm{\dots },b_m)\mid \exists c\in C\text{ with }(a_1,\mathrm{\dots },a_{n-1},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	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