# Composition of Mappings Induced by Relation

## 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$