Image of Composite Relation

From ProofWiki
Jump to: navigation, search

Theorem

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

Let $\mathcal R_2 \circ \mathcal R_1 \subseteq S_1 \times T_2$ be the composition of $\mathcal R_1$ and $\mathcal R_2$.


Then the image of $\mathcal R_2 \circ \mathcal R_1$ is given by:

$\operatorname{Im} \left({\mathcal R_2 \circ \mathcal R_1}\right) = \operatorname{Im} \left({\operatorname{Im} \left({\mathcal R_1}\right) \cap \operatorname{Im}^{-1} \left({\mathcal R_2}\right)}\right)$


Proof

We have by definition of composition of $\mathcal R_1$ and $\mathcal R_2$:

$\mathcal R_2 \circ \mathcal R_1 := \left\{{\left({x, z}\right) \in S_1 \times T_2: \exists y \in S_2 \cap T_1: \left({x, y}\right) \in \mathcal R_1 \land \left({y, z}\right) \in \mathcal R_2}\right\}$

Let $\left({x, z}\right) \in \mathcal R_2 \circ \mathcal R_1$.

By definition of image:

$z \in \operatorname{Im} \left({\mathcal R_2 \circ \mathcal R_1}\right)$.

By definition of composition of $\mathcal R_1$ and $\mathcal R_2$:

$z \in \operatorname{Im} \left({\mathcal R_2}\right)$

But also:

$z \in \operatorname{Im} \left({\operatorname{Im} \left({\mathcal R_1}\right)}\right)$

We also have that $\operatorname{Im} \left({\mathcal R_2}\right) = \operatorname{Im} \left({\operatorname{Im}^{-1} \left({\mathcal R_2}\right)}\right)$

That is: $z \in \operatorname{Im} \left({\operatorname{Im} \left({\mathcal R_1}\right)}\right) \cap \operatorname{Im} \left({\operatorname{Im}^{-1} \left({\mathcal R_2}\right)}\right)$