# 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$