Composition of Mappings Induced by Relation

From ProofWiki
Jump to: navigation, search

Theorem

Let $A, B, C$ be non-empty sets.

Let $\mathcal R_1 \subseteq A \times B, \mathcal R_2 \subseteq B \times C$ be relations.


Let:

${\mathcal R_1}^\to: \mathcal P \left({A}\right) \to \mathcal P \left({B}\right)$

and

${\mathcal R_2}^\to: \mathcal P \left({B}\right) \to \mathcal P \left({C}\right)$

be the mappings induced by $\mathcal R_1$ and $\mathcal R_2$.


Then:

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


Proof

Let $S \subseteq A, S \ne \varnothing$.


Then:

\(\displaystyle \left({ {\mathcal R_2}^\to \circ {\mathcal R_1}^\to}\right) \left({S}\right)\) \(=\) \(\displaystyle {\mathcal R_2}^\to \left({ {\mathcal R_1}^\to \left({S}\right)}\right)\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left\{ {\mathcal R_2 \left({x}\right): x \in {\mathcal R_1}^\to \left({S}\right)}\right\}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left\{ {\mathcal R_2 \left({x}\right): \exists y \in S: \left({x, y}\right) \in \mathcal R_1}\right\}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left\{ {\mathcal R_2 \left({\mathcal R_1 \left({y}\right)}\right): y \in S}\right\}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left\{ {\mathcal R_2 \circ \mathcal R_1 \left({y}\right): y \in S}\right\}\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({\mathcal R_2 \circ \mathcal R_1}\right)^\to \left({S}\right)\) $\quad$ $\quad$


Now we treat the case where $S = \varnothing$:

\(\displaystyle \left({ {\mathcal R_2}^\to \circ {\mathcal R_1}^\to}\right) \left({\varnothing}\right)\) \(=\) \(\displaystyle \varnothing\) $\quad$ $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({\mathcal R_2 \circ \mathcal R_1}\right)^\to \left({\varnothing}\right)\) $\quad$ $\quad$

$\blacksquare$


Sources