Composition of Relations

If $A$ and $B$ are sets, then a relation on $(A,B)$ is merely a subset of $A \times B$.

Suppose that $A$, $B$, and $C$ are three sets. Let $R \subset A \times B$ and $S \subset B \times C$ be binary relations on $(A,B)$ and $(B,C)$ respectively. Then $S \circ R \subset X \times Z$ a relation on $(X,Z)$ defined by

$S \circ R = \{(a,c) : (\exists b \in B)((a,b) \in R \text{ and } (b,c) \in S)\}$

Note that that $A$ and $B$ are functions, then $B \circ A$ defined above correspond to the usual function composition.

One example I find helpful is the notion of "multi-valued functions". Define a multi-valued function $f$ to be one which just satisfies $(\forall x)(\exists y)f(x) = y$ and not necessarily $(\forall x)(\forall y, y')f(x) = y$ and $f(x) = y'$ implies $y = y'$. Just as in the case of normal functions we can associate $f$ with its graph $G(f)$. Then the composition of relations $G(f) \circ G(g)$ corresponds to the multi-valued function $h$ where $h(x) = y$ if there is some intermediate $z$ with $g(x) = z$ and $f(z) = y$.

Consider three sets $X,Y,Z$ with relations $R \subset X \times Y$ and $S \subset Y \times Z$. We want to construct a new relation, $S \circ R$, between $X$ and $Z$. For motivation, let's take an example where $X$ is the set of lines in the plane, $Y$ the set of points, and $Z$ the set of closed circles with their interiors. Then we can set $(l,p) \in R$ or $l R p$ if $p$ is a point on $l$ and $(p,c) \in S$ if $p$ is in c. What's the natural candidate for $S \circ R$? Surely we want to say $(l,c)\in S \circ R$ if $l$ intersects $c$-that is, if $l$ contains $p$ in $c$.

The example says it all: we define the composition of morphisms by $(x,z) \in S \circ R$ if $\exists y: (x,y) \in R, (y,z) \in S$. In particular this is how we set up the category $Rel$ of relations. Note that with this definition in hand we can reformulate some of the central definitions of relation theory. For instance, a relation is transitive just if it's equal to its composition with itself.

Here's a simpler formulation, since I see by your comment this was confusing. Let's try composing the relation $<$ with itself of the natural numbers 1,2,3,... Call the new relation $<^2$. We say for two numbers $m,n$ that $m <^2 n$ if there's some third number $p$ with $m < p$ and $p < n$. So, what do we have? $<^2$ is just the relation between numbers at least two apart. So $1 <^2 3$ and $100 <^2 110,$ but we don't have $3 <^2 4$. For some relations, composition doesn't change anything: for instance, if two lines are both parallel to a third, then the two lines are parallel to each other.

We can also compose two different relations. Think about the two relations: (1) a line is perpendicular to another line and (2) a line intersects a circle. The composition of these relations is: a line is perpendicular to some line intersecting a circle.