Subset of Image

Theorem

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

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 language of induced mappings, that would be written:

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

Corollary 1

The same applies to the preimage, as follows.

Let $C, D \subseteq T$.

Then:

$C \subseteq D \implies f_{\mathcal R^{-1}} \left({C}\right) \subseteq f_{\mathcal R^{-1}} \left({D}\right)$

where $\mathcal R^{-1}$ is the inverse of $\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 $f: S \to T$ be a mapping.

Let:

• $A, B \subseteq S$
• $C, D \subseteq T$

Then:

• $A \subseteq B \implies f \left({A}\right) \subseteq f \left({B}\right)$
• $C \subseteq D \implies f^{-1} \left({C}\right) \subseteq f^{-1} \left({D}\right)$

Proof

Suppose $\mathcal R \left({A}\right) \not \subseteq \mathcal R \left({B}\right)$.

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

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

$\blacksquare$

Proof of Corollary 1

As $\mathcal R^{-1}$ is itself a relation, by definition of inverse relation, the main result applies directly.

$\blacksquare$

Proof of Corollary 2

As $f: S \to T$ is a mapping, it is also a relation, and thus:

$f \subseteq S \times T$

and so is its inverse:

$f^{-1} \subseteq T \times S$

Hence, as for Corollary 1, the main result applies directly.

$\blacksquare$

Sources

• T.S. Blyth: Set Theory and Abstract Algebra (1975): $\S 5$: Theorem $5.1: \ \text{(i), (j)}$
• B. Hartley and T.O. Hawkes: Rings, Modules and Linear Algebra (1970): $\S 2.2$
• Thomas A. Whitelaw: An Introduction to Abstract Algebra (1978)... (previous)... (next): $\S 21.3$