Restriction of Injection is Injection

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $f: S \to T$ be an injection.

Let $X \subseteq S$ be a subset of $S$.

Let $f \left[{X}\right]$ denote the image of $X$ under $f$.

Let $Y \subseteq T$ be a subset of $T$ such that $f \left[{X}\right] \subseteq Y$.


The restriction $f \restriction_{X \times Y}$ of $f$ to $X \times Y$ is an injection from $X$ to $Y$.


Proof

First we show that $f \restriction_{X \times Y}$ is a mapping from $X$ to $Y$.

By Restriction of Mapping is Mapping, $f \restriction_{X \times T}$ is a mapping from $X$ to $T$.

If $x \in X$, then by the definition of image:

$f \left({x}\right) \in f \left[{X}\right]$


Since $f \left[{X}\right] \subseteq Y$, $f \restriction_{X \times Y}$ is a mapping from $X$ to $Y$.

By definition of an injection:

$\forall s_1, s_2 \in S: f \left({s_1}\right) = f \left({s_2}\right) \implies s_1 = s_2$.


Suppose $f \restriction_{X \times Y}: X \to Y$ were not an injection.

Then $\exists x_1, x_2 \in X: x_1 \ne x_2, f \left({x_1}\right) = f \left({x_2}\right)$.

But then $\exists x_1, x_2 \in S: x_1 \ne x_2, f \left({x_1}\right) = f \left({x_2}\right)$.

So $f: S \to T$ would not then be an injection.


Hence the result.

$\blacksquare$