Inverse of Composite Relation

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\mathcal R_2 \circ \mathcal R_1 \subseteq S_1 \times S_3$ be the composite of the two relations $\mathcal R_1 \subseteq S_1 \times S_2$ and $\mathcal R_2 \subseteq S_2 \times S_3$.


Then:

$\paren {\mathcal R_2 \circ \mathcal R_1}^{-1} = \mathcal R_1^{-1} \circ \mathcal R_2^{-1}$


Proof

Let $\mathcal R_1 \subseteq S_1 \times S_2$ and $\mathcal R_2 \subseteq S_2 \times S_3$ be relations.

We assume that:

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

where $\Dom {\mathcal R}$ denotes domain and $\Cdm {\mathcal R}$ denotes codomain of a relation $\mathcal R$.

This is necessary for $\mathcal R_2 \circ \mathcal R_1$ to exist.


From the definition of an inverse relation, we have:

$\Dom {\mathcal R_2} = \Cdm {\mathcal R_2^{-1} }$
$\Cdm {\mathcal R_1} = \Dom {\mathcal R_1^{-1} }$


So we confirm that $\mathcal R_1^{-1} \circ \mathcal R_2^{-1}$ is defined.


\(\displaystyle \mathcal R_2 \circ \mathcal R_1\) \(=\) \(\displaystyle \set {\tuple {x, z}: x \in S_1, z \in S_3: \exists y \in S_2: \tuple {x, y} \in \mathcal R_1 \land \tuple {y, z} \in \mathcal R_2}\) Definition of Composition of Relations
\(\displaystyle \leadsto \ \ \) \(\displaystyle \paren {\mathcal R_2 \circ \mathcal R_1}^{-1}\) \(=\) \(\displaystyle \set {\tuple {z, x}: \tuple {x, z} \in \mathcal R_2 \circ \mathcal R_1}\) Definition of Inverse Relation
\(\displaystyle \) \(=\) \(\displaystyle \set {\tuple {z, x}: x \in S_1, z \in S_3: \exists y \in S_2: \tuple {x, y} \in \mathcal R_1 \land \tuple {y, z} \in \mathcal R_2}\) Definition of Composition of Relations
\(\displaystyle \) \(=\) \(\displaystyle \set {\tuple {z, x}: z \in S_3, x \in S_1: \exists y \in S_2: \tuple {z, y} \in \mathcal R_2^{-1} \land \tuple {y, x} \in \mathcal R_1^{-1} }\) Definition of Inverse Relation
\(\displaystyle \) \(=\) \(\displaystyle \mathcal R_1^{-1} \circ \mathcal R_2^{-1}\) Definition of Composition of Relations

$\blacksquare$


Sources