Image of Preimage under Relation is Subset

From ProofWiki
Jump to navigation Jump to search

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$


Also see