Composition of Relations is Associative

Theorem

$\paren {\mathcal R_3 \circ \mathcal R_2} \circ \mathcal R_1 = \mathcal R_3 \circ \paren {\mathcal R_2 \circ \mathcal R_1}$

Proof

First, note that from the definition of composition of relations, the following must be the case before the above expression is even to be defined:

$\Dom {\mathcal R_2} = \Cdm {\mathcal R_1}$
$\Dom {\mathcal R_3} = \Cdm {\mathcal R_2}$

The two composite relations can be seen to have the same domain, thus:

 $\displaystyle \Dom {\paren {\mathcal R_3 \circ \mathcal R_2} \circ \mathcal R_1}$ $=$ $\displaystyle \Dom {\mathcal R_1}$ $\quad$ Domain of Composite Relation $\quad$

 $\displaystyle \Dom {\mathcal R_3 \circ \paren {\mathcal R_2 \circ \mathcal R_1} }$ $=$ $\displaystyle \Dom {\mathcal R_2 \circ \mathcal R_1}$ $\quad$ Domain of Composite Relation $\quad$ $\displaystyle$ $=$ $\displaystyle \Dom {\mathcal R_1}$ $\quad$ Domain of Composite Relation $\quad$

... and also the same codomain, thus:

 $\displaystyle \Cdm {\paren {\mathcal R_3 \circ \mathcal R_2} \circ \mathcal R_1}$ $=$ $\displaystyle \Cdm {\mathcal R_3 \circ \mathcal R_2}$ $\quad$ Codomain of Composite Relation $\quad$ $\displaystyle$ $=$ $\displaystyle \Cdm {\mathcal R_3}$ $\quad$ Codomain of Composite Relation $\quad$

 $\displaystyle \Cdm {\mathcal R_3 \circ \paren {\mathcal R_2 \circ \mathcal R_1} }$ $=$ $\displaystyle \Cdm {\mathcal R_3}$ $\quad$ Codomain of Composite Relation $\quad$

So they are equal if and only if they have the same value at each point in their common domain, which this shows:

 $\displaystyle \forall x \in \Dom {\mathcal R_1}: \ \$ $\displaystyle \paren {\paren {\mathcal R_3 \circ \mathcal R_2} \circ \mathcal R_1} \paren x$ $=$ $\displaystyle \paren {\mathcal R_3 \circ \mathcal R_2} \paren {\mathcal R_1 \paren x}$ $\quad$ Definition of Composition of Relations $\quad$ $\displaystyle$ $=$ $\displaystyle \mathcal R_3 \paren {\mathcal R_2 \paren {\mathcal R_1 \paren x} }$ $\quad$ Definition of Composition of Relations $\quad$ $\displaystyle$ $=$ $\displaystyle \mathcal R_3 \paren {\paren {\mathcal R_2 \circ \mathcal R_1} \paren x}$ $\quad$ Definition of Composition of Relations $\quad$ $\displaystyle$ $=$ $\displaystyle \paren {\mathcal R_3 \circ \paren {\mathcal R_2 \circ \mathcal R_1} } \paren x$ $\quad$ Definition of Composition of Relations $\quad$

$\blacksquare$