Definition:Injection

From ProofWiki
Jump to: navigation, search

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


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:

\(\displaystyle S\) \(=\) \(\displaystyle \set {a, b, c}\) $\quad$ $\quad$
\(\displaystyle T\) \(=\) \(\displaystyle \set {p, q, r, s}\) $\quad$ $\quad$

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:

\(\displaystyle \map f a\) \(=\) \(\displaystyle p\) $\quad$ $\quad$
\(\displaystyle \map f b\) \(=\) \(\displaystyle s\) $\quad$ $\quad$
\(\displaystyle \map f c\) \(=\) \(\displaystyle r\) $\quad$ $\quad$
Injection.png
$S$ is the domain of $f$.
$T$ is the codomain of $f$.
$\set {p, r, s}$ is the image of $f$.


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

\(\displaystyle \map {f^{-1} } p\) \(=\) \(\displaystyle \set a\) $\quad$ $\quad$
\(\displaystyle \map {f^{-1} } q\) \(=\) \(\displaystyle \O\) $\quad$ $\quad$
\(\displaystyle \map {f^{-1} } r\) \(=\) \(\displaystyle \set c\) $\quad$ $\quad$
\(\displaystyle \map {f^{-1} } s\) \(=\) \(\displaystyle \set b\) $\quad$ $\quad$


Also known as

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

one-one (or 1-1) or one-to-one for injective
one-one mapping or one-to-one mapping for injection.

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.


An injective mapping is sometimes written:

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


The $\LaTeX$ code for \(f: S \rightarrowtail T\) is f: S \rightarrowtail T .

The $\LaTeX$ code for \(f: S \hookrightarrow T\) is f: S \hookrightarrow T .


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.


Cube Function is Injective

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

$\forall x \in \R: f \paren x = x^3$

Then $f$ is an injection.


Also see

  • Results about injections can be found here.