Image of Subset under Relation is Subset of Image

From ProofWiki
Jump to navigation Jump to 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 \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$


Sources