Operations on Relations

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