# Image of Subset under Relation is Subset of Image

## Theorem

Let $S$ and $T$ be sets.

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

Let $A, B \subseteq S$ such that $A \subseteq B$.

Then the image of $A$ is a subset of the image of $B$:

$A \subseteq B \implies \mathcal R \sqbrk A \subseteq \mathcal R \sqbrk B$

In the notation of direct image mappings, this can be written:

$A \subseteq B \implies \map {\mathcal R^\to} A \subseteq \map {\mathcal R^\to} B$

### Corollary 1

The same applies to the preimage, as follows.

Let $C, D \subseteq T$.

Then:

$C \subseteq D \implies \mathcal R^{-1} \left[{C}\right] \subseteq \mathcal R^{-1} \left[{D}\right]$

where $\mathcal R^{-1} \left[{C}\right]$ is the preimage of $C$ under $\mathcal R$.

### Corollary 2

The same applies for a mapping $f: S \to T$ and its inverse $f^{-1} \subseteq T \times S$, whether $f^{-1}$ is a mapping or not.

Let $A, B \subseteq S$ such that $A \subseteq B$.

Then the image of $A$ is a subset of the image of $B$:

$A \subseteq B \implies f \sqbrk A \subseteq f \sqbrk B$

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

$\forall A, B \in \powerset S: A \subseteq B \implies \map {f^\to} A \subseteq \map {f^\to} B$

### Corollary 3

And similarly:

Let $C, D \subseteq T$.

Then:

$C \subseteq D \implies f^{-1} \sqbrk C \subseteq f^{-1} \sqbrk D$

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

$\forall C, D \in \powerset T: C \subseteq D \implies \map {f^\gets} C \subseteq \map {f^\gets} D$

## Proof

Suppose $\mathcal R \sqbrk A \not \subseteq \mathcal R \sqbrk B$.

 $\displaystyle \mathcal R \sqbrk A$ $\nsubseteq$ $\displaystyle \mathcal R \sqbrk B$ $\displaystyle \leadsto \ \$ $\displaystyle \exists t \in \mathcal R \sqbrk A: \exists \tuple {s, t} \in \mathcal R: s$ $\notin$ $\displaystyle B$ Definition of Image of Subset under Relation $\displaystyle \leadsto \ \$ $\displaystyle \exists s \notin B: s$ $\in$ $\displaystyle A$ Definition of Ordered Pair $\displaystyle \leadsto \ \$ $\displaystyle A$ $\nsubseteq$ $\displaystyle B$ Definition of Subset

The result follows by the Rule of Transposition.

$\blacksquare$