Image of Subset under Relation is Subset of Image

From ProofWiki
Jump to: navigation, search

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 \left[{A}\right] \subseteq \mathcal R \left[{B}\right]$


In the notation of induced mappings, that would be written:

$A \subseteq B \implies \mathcal R^\to \left({A}\right) \subseteq \mathcal R^\to \left({B}\right)$


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$


Corollary 3

And similarly:


Let $C, D \subseteq T$.


Then:

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


Proof

Suppose $\mathcal R \left[{A}\right] \not \subseteq \mathcal R \left[{B}\right]$.

\(\displaystyle \mathcal R \left[{A}\right]\) \(\nsubseteq\) \(\displaystyle \mathcal R \left[{B}\right]\) $\quad$ $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \exists t \in \mathcal R \left[{A}\right]: \exists \left({s, t}\right) \in \mathcal R: s\) \(\notin\) \(\displaystyle B\) $\quad$ Definition of image $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle \exists s \notin B: s\) \(\in\) \(\displaystyle A\) $\quad$ Definition of ordered pair $\quad$
\(\displaystyle \implies \ \ \) \(\displaystyle A\) \(\nsubseteq\) \(\displaystyle B\) $\quad$ Definition of subset $\quad$


... and the result follows by the Rule of Transposition.

$\blacksquare$


Sources