Operations on Relations – Foundations of Mathematics

Besides the ordinary set operations, there are special operations we can perform on relations.

Definition. The inverse of a relation $R$ from $A$ to $B$ is the relation from $B$ to $A$ defined by:

$R^{-1}=\left\{ (b,a)\middle| (a,b)\in R\right\}$

That is, $b \operatorname {R^{-1}} a$ iff $(b,a)\in R^{-1}$ iff $(a,b)\in R$ iff $a\operatorname{R} b$ .

E.g. $x\operatorname{LT^{-1}} y$ iff $y \operatorname{LT} x$ iff $y<x$ .

That is, the inverse of the less-than relation is the greater-than relation.

Note that the inverse and the complement are very different things, because the complement of less-than is greater-than-or-equal-to.

Exercise. What is the inverse of the identity relation?

Definition. If $R$ is a relation from $A$ to $B$ and $S$ is a relation from $B$ to $C$ , we define the {\em composite relation} $S\circ R$ from $A$ to $C$ by:

$S\circ R=\left\{ (a,c)\middle| \exists b\in B: (a,b)\in R\wedge (b,c)\in S\right\}$

Note that the source of $S\circ R$ is the source of $R$ and the target of $S\circ R$ is the target of $S$ .

We can think of $b$ as a stepping stone between $a$ and $c$ . $S\circ R$ consists of all the pairs $(a,c)$ such that there is such a stepping stone, as we pass from the source of $R$ to the target of $S$ .

Observe that unless the target of $T$ and the source of $V$ are the same, we can't even make sense of $V\circ T$ . So most composites aren't defined, and we must first check that two relations are compatible before we try to compose them. Even if $S\circ R$ is defined, $R\circ S$ usually isn't.

In lower mathematics courses, you probably only encountered relations on $\mathbb{R}$ , so that all sources and targets were the same---thus, all compositions were defined. The sole exception to this is in multivariable calculus. This is precisely why the multivariable Chain Rule is so much more complicated than its single-variable counterpart.

Exercise. Formulate the definition of $S\circ R$ in infix notation. That is, explain what $x \operatorname{S\circ R} y$ means.

Exercise. Consider the set $P$ of all people, and the relations $M$ and $F$ on $P$ given by: $x\operatorname{M} y$ iff $x$ is $y$ 's mother and $x\operatorname{F} y$ iff $x$ is $y$ 's father. Explain what the following relations mean: $F^c$ , $M\cap F$ , $M\circ M$ , $F\circ F$ , $F^{-1}$ , $M\circ F$ , $F\circ M$ , $M\circ F^{-1}$ , $F^{-1}\circ M$ .

Theorem. Let $R$ be a relation from $A$ to $B$ , $S$ a relation from $B$ to $C$ , and $T$ a relation from $C$ to $D$ . Then

$\left(R^{-1}\right)^{-1}=R$
$T\circ(S\circ R)=(T\circ S)\circ R$
$I_B\circ R=R$ and $R\circ I_A=R$
$\left(S\circ R\right)^{-1}=R^{-1}\circ S^{-1}$
$I_{\operatorname{Domain}(R)}\subseteq R^{-1}\circ R$ and $I_{\operatorname{Range}(R)}\subseteq R\circ R^{-1}$ .

Proof. We'll prove the last clause, and leave the others as exercises.

Since we need to prove $I_{\operatorname{Domain}(R)}\subseteq R^{-1}\circ R$ , let $x\in I_{\operatorname{Domain}(R)}$ . Then $x=(a,a)$ for some $a\in \operatorname{Domain}(R)$ . Since $a\in\operatorname{Domain}(R)$ , there is some $b\in B$ with $(a,b)\in R$ . So $(b,a)\in R^{-1}$ . So $x=(a,a)\in R^{-1}\circ R$ .

To show $I_{\operatorname{Range}(R)}\subseteq R\circ R^{-1}$ , let $x\in I_{\operatorname{Range}(R)}$ . Then $x=(b,b)$ for some $b\in \operatorname{Range}(R)$ . Since $b\in\operatorname{Range}(R)$ , there is some $a\in A$ with $(a,b)\in R$ . Then $(b,a)\in R^{-1}$ . So $x=(b,b)\in R\circ R^{-1}$ .