Composition of Direct Image Mappings of Relations

From ProofWiki
Jump to navigation Jump to 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: \powerset A \to \powerset B$

and

${\mathcal R_2}^\to: \powerset B \to \powerset C$

be the direct image mappings of $\mathcal R_1$ and $\mathcal R_2$.


Then:

$\paren {\mathcal R_2 \circ \mathcal R_1}^\to = {\mathcal R_2}^\to \circ {\mathcal R_1}^\to$


Proof

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


Then:

\(\displaystyle \map {\paren { {\mathcal R_2}^\to \circ {\mathcal R_1}^\to} } S\) \(=\) \(\displaystyle \map { {\mathcal R_2}^\to} {\map { {\mathcal R_1}^\to } S}\)
\(\displaystyle \) \(=\) \(\displaystyle \set {\map {\mathcal R_2} x: x \in \map { {\mathcal R_1}^\to } S}\)
\(\displaystyle \) \(=\) \(\displaystyle \set {\map {\mathcal R_2} x: \exists y \in S: \tuple {x, y} \in \mathcal R_1}\)
\(\displaystyle \) \(=\) \(\displaystyle \set {\map {\mathcal R_2} {\map {\mathcal R_1} y}: y \in S}\)
\(\displaystyle \) \(=\) \(\displaystyle \set {\map {\mathcal R_2 \circ \mathcal R_1} y: y \in S}\)
\(\displaystyle \) \(=\) \(\displaystyle \map {\paren {\mathcal R_2 \circ \mathcal R_1}^\to} S\)


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

\(\displaystyle \map {\paren { {\mathcal R_2}^\to \circ {\mathcal R_1}^\to} } \O\) \(=\) \(\displaystyle \O\)
\(\displaystyle \) \(=\) \(\displaystyle \map {\paren {\mathcal R_2 \circ \mathcal R_1}^\to} \O\)

$\blacksquare$