# Equivalence of Definitions of Injection/Definition 1 iff Definition 3

## Theorem

The following definitions of the concept of **Injection** are equivalent:

### Definition 1

A mapping $f$ is **an injection**, or **injective** if and only if:

- $\forall x_1, x_2 \in \Dom f: \map f {x_1} = \map f {x_2} \implies x_1 = x_2$

That is, an **injection** is a mapping such that the output uniquely determines its input.

### Definition 3

Let $f$ be a mapping.

Then $f$ is an injection if and only if:

- $f^{-1} {\restriction_{\Img f} }: \Img f \to \Dom f$ is a mapping

where $f^{-1} {\restriction_{\Img f} }$ is the restriction of the inverse of $f$ to the image set of $f$.

## Proof

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

Thus:

- $\forall x_1, x_2 \in S: \map f {x_1} = \map f {x_2} \implies x_1 = x_2$

First we note that:

- $t \in \Img f \implies \exists x \in \Dom f: \map f x = t$

thus fulfilling the condition for $f^{-1} {\restriction_{\Img f} }$ to be left-total.

Now let:

- $t \in \Img f: \tuple {t, y}, \tuple {t, z} \in f^{-1}$

Thus:

\(\displaystyle \tuple {t, y}, \tuple {t, z}\) | \(\in\) | \(\displaystyle f^{-1} {\restriction_{\Img f} }\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \tuple {y, t}, \tuple {z, t}\) | \(\in\) | \(\displaystyle f\) | Definition of Inverse of Mapping | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \map f y = t\) | \(=\) | \(\displaystyle \map f z\) | Equality of Elements in Range of Mapping | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle y\) | \(=\) | \(\displaystyle z\) | as $f$ is injective |

So by the definition of mapping, $f^{-1} {\restriction_{\Img f} }$ is a mapping.

So $f$ is an injection by definition 3.

$\Box$

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

Then:

- $f^{-1} {\restriction_{\Img f} }: \Img f \to \Dom f$ is a mapping

where $f^{-1} {\restriction_{\Img f} }$ is the restriction of the inverse of $f$ to the image set of $f$.

We need to show that:

- $\forall x, z \in \Dom f: \map f x = \map f z \implies x = z$

So, pick any $x, z \in \Dom f$ such that:

- $\map f x = \map f z$

Then:

\(\displaystyle \map f x\) | \(=\) | \(\displaystyle \map f z\) | |||||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \exists y \in \Dom f: \tuple {x, y}, \tuple {z, y}\) | \(\in\) | \(\displaystyle f\) | Definition of Mapping | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle \tuple {y, x}, \tuple {y, z}\) | \(\in\) | \(\displaystyle f^{-1} {\restriction_{\Img f} }\) | Definition of Inverse of Mapping | |||||||||

\(\displaystyle \leadsto \ \ \) | \(\displaystyle x\) | \(=\) | \(\displaystyle z\) | as it is specified that $f^{-1} {\restriction_{\Img f} }$ is a mapping |

So $f$ is an injection by definition 1.

$\blacksquare$

## Sources

- 1965: Seth Warner:
*Modern Algebra*... (previous) ... (next): $\S 5$: Theorem $5.2$ - 1975: W.A. Sutherland:
*Introduction to Metric and Topological Spaces*... (previous) ... (next): Notation and Terminology