# Image of Preimage under Relation is Subset

## Theorem

Let $\mathcal R \subseteq S \times T$ be a relation.

Then:

$B \subseteq T \implies \left({\mathcal R \circ \mathcal R^{-1} }\right) \left[{B}\right] \subseteq B$

where:

$\mathcal R \left[{B}\right]$ denotes the image of $B$ under $\mathcal R$
$\mathcal R^{-1} \left[{B}\right]$ denotes the preimage of $B$ under $\mathcal R$
$\mathcal R \circ \mathcal R^{-1}$ denotes composition of $\mathcal R$ and $\mathcal R^{-1}$.

## Proof

Let $B \subseteq T$.

Then:

 $\displaystyle y$ $\in$ $\displaystyle \left({\mathcal R \circ \mathcal R^{-1} }\right) \left({B}\right)$ $\displaystyle \implies \ \$ $\displaystyle y$ $\in$ $\displaystyle \mathcal R \left[{\mathcal R^{-1} \left[{B}\right]}\right]$ Definition of Composition of Relations $\displaystyle \implies \ \$ $\displaystyle \exists x \in \mathcal R^{-1} \left[{B}\right]: \left({x, y}\right)$ $\in$ $\displaystyle \mathcal R$ $\displaystyle \implies \ \$ $\displaystyle y$ $\in$ $\displaystyle B$

So by definition of subset:

$B \subseteq T \implies \left({\mathcal R \circ \mathcal R^{-1} }\right) \left[{B}\right] \subseteq B$

$\blacksquare$