Composition of Relations is Associative

From ProofWiki
Jump to navigation Jump to search

Theorem

The composition of relations is an associative binary operation:

$\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}\) Domain of Composite Relation


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


... 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}\) Codomain of Composite Relation
\(\displaystyle \) \(=\) \(\displaystyle \Cdm {\mathcal R_3}\) Codomain of Composite Relation


\(\displaystyle \Cdm {\mathcal R_3 \circ \paren {\mathcal R_2 \circ \mathcal R_1} }\) \(=\) \(\displaystyle \Cdm {\mathcal R_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 {\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}\) Definition of Composition of Relations
\(\displaystyle \) \(=\) \(\displaystyle \mathcal R_3 \paren {\mathcal R_2 \paren {\mathcal R_1 \paren x} }\) Definition of Composition of Relations
\(\displaystyle \) \(=\) \(\displaystyle \mathcal R_3 \paren {\paren {\mathcal R_2 \circ \mathcal R_1} \paren x}\) Definition of Composition of Relations
\(\displaystyle \) \(=\) \(\displaystyle \paren {\mathcal R_3 \circ \paren {\mathcal R_2 \circ \mathcal R_1} } \paren x\) Definition of Composition of Relations

$\blacksquare$


Sources