Composition of Relations

Topics: Discrete Mathematics - Relation

---

(definition)

Let $R\subseteq X\times Y$ and $S\subseteq Y\times Z$ be two relations.

The composition of $R$ and $S$, denoted $R\circ S$, is the relation:

$$R\circ S=\{(x,z)\in X\times Z\mid \exists y\in Y:(x,y)\in R\wedge (y,z)\in S\}$$

In other words, $R\circ S\subseteq X\times Z$ is defined by the rule that says that $(x,z)\in R$ if and only if there is an element $y\in Y$ such that $(x,y)\in R$ and $(y,z)\in S$.

Associativity §

(theorem)

Let $A,B,C,D$ be sets. Let $R_1\subseteq A\times B$, $R_2\subseteq B\times C$ and $R_3\subseteq C\times D$ (see Cartesian Product).

Then, it’s true that:

$$R_1\circ (R_2\circ R_3)=(R_1\circ R_2)\circ R_3$$