# Definition:Injection

## Definition

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

An **injection** is a relation which is both one-to-one and left-total.

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

### Definition 4

Let $f$ be a mapping.

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

- $\forall y \in \Img f: \card {\map {f^{-1} } y} = \card {\set {f^{-1} \sqbrk {\set y} } } = 1$

where:

- $\Img f$ denotes the image set of $f$
- $\card {\, \cdot \,}$ denotes the cardinality of a set
- $\map {f^{-1} } y$ is the preimage of $y$
- $f^{-1} \sqbrk {\set y}$ is the preimage of the subset $\set y \subseteq \Img f$.

### Definition 5

Let $f: S \to T$ be a mapping where $S \ne \O$.

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

- $\exists g: T \to S: g \circ f = I_S$

where $g$ is a mapping.

That is, if and only if $f$ has a left inverse.

### Definition 6

Let $f: S \to T$ be a mapping where $S \ne \O$.

Then $f$ is an **injection** if and only if $f$ is left cancellable:

- $\forall X: \forall g_1, g_2: X \to S: f \circ g_1 = f \circ g_2 \implies g_1 = g_2$

where $g_1$ and $g_2$ are arbitrary mappings from an arbitrary set $X$ to the domain $S$ of $f$.

## Class-Theoretical Definition

In the context of class theory, the definition follows the same lines:

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

This can otherwise be put:

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

## Graphical Depiction

The following diagram depicts an injection $f$ from $S$ into $T$:

- $f: S \to T$

where $S$ and $T$ are the finite sets:

\(\ds S\) | \(=\) | \(\ds \set {a, b, c}\) | ||||||||||||

\(\ds T\) | \(=\) | \(\ds \set {p, q, r, s}\) |

and $f$ is defined as:

- $f = \set {\tuple {a, p}, \tuple {b, s}, \tuple {c, r} }$

Thus the images of each of the elements of $S$ under $f$ are:

\(\ds \map f a\) | \(=\) | \(\ds p\) | ||||||||||||

\(\ds \map f b\) | \(=\) | \(\ds s\) | ||||||||||||

\(\ds \map f c\) | \(=\) | \(\ds r\) |

The preimages of each of the elements of $T$ under $f$ are:

\(\ds \map {f^{-1} } p\) | \(=\) | \(\ds \set a\) | ||||||||||||

\(\ds \map {f^{-1} } q\) | \(=\) | \(\ds \O\) | ||||||||||||

\(\ds \map {f^{-1} } r\) | \(=\) | \(\ds \set c\) | ||||||||||||

\(\ds \map {f^{-1} } s\) | \(=\) | \(\ds \set b\) |

## Also known as

Authors who prefer to limit the jargon of mathematics tend to use the term:

However, because of the possible confusion with the term one-to-one correspondence, it is standard on $\mathsf{Pr} \infty \mathsf{fWiki}$ for the technical term **injection** to be used instead.

E.M. Patterson's idiosyncratic *Topology, 2nd ed.* of $1959$ refers to such a mapping as **biuniform**.

This is confusing, because a casual reader may conflate this with the definition of a **bijection**, which in that text is not explicitly defined at all.

An **injective mapping** is sometimes written:

- $f: S \rightarrowtail T$ or $f: S \hookrightarrow T$

In the context of class theory, an **injection** is often seen referred to as a **class injection**.

## Examples

### $2 x$ Function on Integers is Injective but not Surjective

Let $f: \Z \to \Z$ be the mapping defined on the set of integers as:

- $\forall x \in \Z: \map f x = 2 x$

Then $f$ is an injection, but not a surjection.

### $2 x + 1$ Function on Integers is Injective

Let $f: \Z \to \Z$ be the mapping defined on the set of integers as:

- $\forall x \in \Z: \map f x = 2 x + 1$

Then $f$ is an injection.

### $-x$ Function on Integers is Injective

Let $f: \Z \to \Z$ be the mapping defined on the set of integers as:

- $\forall x \in \Z: \map f x = -x$

Then $f$ is an injection.

### Square Function on $\N$ is Injective

Let $f: \N \to \N$ be the mapping defined as:

- $\forall n \in \N: \map f n = n^2$

Then $f$ is an injection, but not a surjection.

### Cube Function is Injective

Let $f: \R \to \R$ be the real function defined as:

- $\forall x \in \R: \map f x = x^3$

Then $f$ is an injection.

## Also see

- Subset equals Preimage of Image iff Mapping is Injection: a mapping $f$ is an
**injection**if and only if the preimage of the image of every subset of its domain equals that subset.

- Results about
**injections**can be found here.

## Sources

- 2002: Thomas Jech:
*Set Theory*(3rd ed.) ... (previous) ... (next): Chapter $1$: Power Set - 2008: David Nelson:
*The Penguin Dictionary of Mathematics*(4th ed.) ... (previous) ... (next): Entry:**one-to-one function (one-to-one mapping, one-to-one map)** - 2014: Christopher Clapham and James Nicholson:
*The Concise Oxford Dictionary of Mathematics*(5th ed.) ... (previous) ... (next): Entry:**injection, injective mapping**