# Composition of Relations is Associative

Jump to navigation Jump to search

## Theorem

$\paren {\RR_3 \circ \RR_2} \circ \RR_1 = \RR_3 \circ \paren {\RR_2 \circ \RR_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 {\RR_2} = \Cdm {\RR_1}$
$\Dom {\RR_3} = \Cdm {\RR_2}$

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

 $\displaystyle \Dom {\paren {\RR_3 \circ \RR_2} \circ \RR_1}$ $=$ $\displaystyle \Dom {\RR_1}$ Domain of Composite Relation

 $\displaystyle \Dom {\RR_3 \circ \paren {\RR_2 \circ \RR_1} }$ $=$ $\displaystyle \Dom {\RR_2 \circ \RR_1}$ Domain of Composite Relation $\displaystyle$ $=$ $\displaystyle \Dom {\RR_1}$ Domain of Composite Relation

... and also the same codomain, thus:

 $\displaystyle \Cdm {\paren {\RR_3 \circ \RR_2} \circ \RR_1}$ $=$ $\displaystyle \Cdm {\RR_3 \circ \RR_2}$ Codomain of Composite Relation $\displaystyle$ $=$ $\displaystyle \Cdm {\RR_3}$ Codomain of Composite Relation

 $\displaystyle \Cdm {\RR_3 \circ \paren {\RR_2 \circ \RR_1} }$ $=$ $\displaystyle \Cdm {\RR_3}$ Codomain of Composite Relation

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 {\RR_1}: \ \$ $\displaystyle \map {\paren {\paren {\RR_3 \circ \RR_2} \circ \RR_1} } x$ $=$ $\displaystyle \map {\paren {\RR_3 \circ \RR_2} } {\map {\RR_1} x}$ Definition of Composition of Relations $\displaystyle$ $=$ $\displaystyle \map {\RR_3} {\map {\RR_2} {\map {\RR_1} x} }$ Definition of Composition of Relations $\displaystyle$ $=$ $\displaystyle \map {\RR_3} {\map {\paren {\RR_2 \circ \RR_1} } x}$ Definition of Composition of Relations $\displaystyle$ $=$ $\displaystyle \map {\paren {\RR_3 \circ \paren {\RR_2 \circ \RR_1} } } x$ Definition of Composition of Relations

$\blacksquare$