# Preimage of Image under Relation is Superset

## Theorem

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

Then:

$A \subseteq S \implies A \subseteq \paren {\mathcal R^{-1} \circ \mathcal R} \sqbrk A$

where:

$\mathcal R \sqbrk A$ denotes the image of $A$ under $\mathcal R$
$\mathcal R^{-1} \sqbrk A$ denotes the preimage of $A$ under $\mathcal R$
$\mathcal R^{-1} \circ \mathcal R$ denotes composition of $\mathcal R^{-1}$ and $\mathcal R$.

This can be expressed in the language and notation of direct image mappings and inverse image mappings as:

$\forall A \in \powerset S: A \subseteq \map {\paren {\mathcal R^\gets \circ \mathcal R^\to} } A$

## Proof

Suppose $A \subseteq S$.

We have:

 $\displaystyle x$ $\in$ $\displaystyle A$ $\displaystyle \leadsto \ \$ $\displaystyle \set x$ $\subseteq$ $\displaystyle A$ Singleton of Element is Subset $\displaystyle \leadsto \ \$ $\displaystyle \mathcal R \sqbrk {\set x}$ $\subseteq$ $\displaystyle \mathcal R \sqbrk A$ Image of Subset under Relation is Subset of Image $\displaystyle \leadsto \ \$ $\displaystyle \mathcal R^{-1} \sqbrk {\mathcal R \sqbrk {\set x} }$ $\subseteq$ $\displaystyle \mathcal R^{-1} \sqbrk {\mathcal R \sqbrk A}$ Image of Subset under Relation is Subset of Image: Corollary 1 $\displaystyle \leadsto \ \$ $\displaystyle x$ $\in$ $\displaystyle \mathcal R^{-1} \sqbrk {\mathcal R \sqbrk A}$ Definition of Relation $\displaystyle \leadsto \ \$ $\displaystyle x$ $\in$ $\displaystyle \paren {\mathcal R^{-1} \circ \mathcal R} \sqbrk A$ Definition of Composition of Relations

So by definition of subset:

$A \subseteq S \implies A \subseteq \paren {\mathcal R^{-1} \circ \mathcal R} \sqbrk A$

$\blacksquare$