Composition of Relations Associative

Theorem

The composition of relations is an associative binary operation:

$\left({\mathcal R_3 \circ \mathcal R_2}\right) \circ \mathcal R_1 = \mathcal R_3 \circ \left({\mathcal R_2 \circ \mathcal R_1}\right)$

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:

• $\operatorname{Dom} \left({\mathcal R_2}\right) = \operatorname{Cdm} \left({\mathcal R_1}\right)$
• $\operatorname{Dom} \left({\mathcal R_3}\right) = \operatorname{Cdm} \left({\mathcal R_2}\right)$

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

	\(\displaystyle \)	\(\displaystyle \operatorname{Dom} \left({\left({\mathcal R_3 \circ \mathcal R_2}\right) \circ \mathcal R_1}\right)\)	\(=\)	\(\displaystyle \operatorname{Dom} \left({\mathcal R_2 \circ \mathcal R_1}\right)\)	\(\displaystyle \)	Domain of Composite Relation
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \operatorname{Dom} \left({\mathcal R_1}\right)\)	\(\displaystyle \)	Domain of Composite Relation

	\(\displaystyle \)	\(\displaystyle \operatorname{Dom} \left({\mathcal R_3 \circ \left({\mathcal R_2 \circ \mathcal R_1}\right)}\right)\)	\(=\)	\(\displaystyle \operatorname{Dom} \left({\mathcal R_2 \circ \mathcal R_1}\right)\)	\(\displaystyle \)	Domain of Composite Relation
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \operatorname{Dom} \left({\mathcal R_1}\right)\)	\(\displaystyle \)	Domain of Composite Relation

... and also the same codomain, thus:

	\(\displaystyle \)	\(\displaystyle \operatorname{Cdm} \left({\left({\mathcal R_3 \circ \mathcal R_2}\right) \circ \mathcal R_1}\right)\)	\(=\)	\(\displaystyle \operatorname{Cdm} \left({\mathcal R_3 \circ \mathcal R_2}\right)\)	\(\displaystyle \)	Codomain of Composite Relation
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \operatorname{Cdm} \left({\mathcal R_3}\right)\)	\(\displaystyle \)	Codomain of Composite Relation

	\(\displaystyle \)	\(\displaystyle \operatorname{Cdm} \left({\mathcal R_3 \circ \left({\mathcal R_2 \circ \mathcal R_1}\right)}\right)\)	\(=\)	\(\displaystyle \operatorname{Cdm} \left({\mathcal R_3 \circ \mathcal R_2}\right)\)	\(\displaystyle \)	Codomain of Composite Relation
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \operatorname{Cdm} \left({\mathcal R_3}\right)\)	\(\displaystyle \)	Codomain of Composite Relation

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

	\(\displaystyle \forall x \in \operatorname{Dom} \left({\mathcal R_1}\right):\)	\(\displaystyle \left({\left({\mathcal R_3 \circ \mathcal R_2}\right) \circ \mathcal R_1}\right) \left({x}\right)\)	\(=\)	\(\displaystyle \left({\mathcal R_3 \circ \mathcal R_2}\right) \left ({\mathcal R_1 \left({x}\right)}\right)\)	\(\displaystyle \)	Definition of composite relation
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \mathcal R_3 \left ({\mathcal R_2 \left ({\mathcal R_1 \left({x}\right)}\right)}\right)\)	\(\displaystyle \)	Definition of composite relation
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \mathcal R_3 \left ({\left({\mathcal R_2 \circ \mathcal R_1}\right) \left({x}\right)}\right)\)	\(\displaystyle \)	Definition of composite relation
	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \left({\mathcal R_3 \circ \left({\mathcal R_2 \circ \mathcal R_1}\right)}\right) \left({x}\right)\)	\(\displaystyle \)	Definition of composite relation

$\blacksquare$

Sources

• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 10$: Inverses and Composites
• Seth Warner: Modern Algebra (1965): $\S 5$: Exercise $5.8 \ \text{(b)}$
• George McCarty: Topology: An Introduction with Application to Topological Groups (1967): $\text{I}$: Problem $\text{AA}$