Injection iff Left Inverse

From ProofWiki
Jump to: navigation, search

Theorem

A mapping $f: S \to T, S \ne \O$ 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.


Proof 1

Let:

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

From Identity Mapping is Injection, $I_S$ is injective, so $g \circ f$ is injective.

So from Injection if Composite is Injection, $f$ is an injection.

Note that the existence of such a $g$ requires that $S \ne \varnothing$.

$\Box$


Now, assume $f$ is an injection.

We now define a mapping $g: T \to S$ as follows.

As $S \ne \varnothing$, we choose $x_0 \in S$.

By definition of injection:

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

so it is possible to define:

$g \paren y = \begin{cases} x_0: & y \in T \setminus \Img f \\ f^{-1} \paren y: & y \in \Img f \end{cases}$
InjectionIffLeftInverse.png

So, for all $x \in S$:

$g \circ f \paren x = g \paren {f \paren x}$

is the unique element of $S$ which $f$ maps to $f \paren x$.

This unique element is $x$.

Thus $g \circ f = I_S$.

$\blacksquare$


Proof 2

Take the result Condition for Composite Mapping on Left:

Let $A, B, C$ be sets.

Let $f: A \to B$ and $g: A \to C$ be mappings.

Then:

$\forall x, y \in A: f \left({x}\right) = f \left({y}\right) \implies g \left({x}\right) = g \left({y}\right)$

if and only if:

$\exists h: B \to C$ such that $h$ is a mapping and $h \circ f = g$.


Let $C = A = S$, let $B = T$ and let $g = I_S$.

Then the above translates into:

$\exists h: T \to S$ such that $h$ is a mapping and $h \circ f = g$

if and only if:

$\forall x, y \in S: f \left({x}\right) = f \left({y}\right) \implies I_S \left({x}\right) = I_S \left({y}\right)$


But as $I_S \left({x}\right) = x$ and $I_S \left({y}\right) = y$ by definition of identity mapping, it follows that:

$\exists h: T \to S$ such that $h$ is a mapping and $h \circ f = g$

if and only if:

$\forall x, y \in S: f \left({x}\right) = f \left({y}\right) \implies x = y$

which is our result.

$\blacksquare$


Proof 3

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

Then $f$ is a one-to-many relation.

By Inverse of Many-to-One Relation is One-to-Many, $f^{-1}: T \to S$ is many-to-one.

By Many-to-One Relation Extends to Mapping, there is a Mapping $g: T \to S$ such that $f^{-1} \subseteq g$.

Let $\left({x, y}\right) \in g \circ f$.

Then:

$\exists z \in T: \left({x, z}\right) \in f, \left({z, y}\right) \in g$

Since $\left({x, z}\right) \in f$:

$\left({z, x}\right) \in f^{-1} \subseteq g$

Since $\left({z, y}\right) \in g$, $\left({z, x}\right) \in g$ and $g$ is a mapping:

$x = y$

so:

$\left({x, y}\right) \in I_S$

So we see that:

$g \circ f \subseteq I_S$


Let $x \in S$.

Then:

$\left({x, f \left({x}\right)}\right) \in f$

and:

$\left({f \left({x}\right), x}\right) \in f^{-1} \subseteq g$

So:

$\left({x, x}\right) \in g \circ f$

Thus:

$I_S \subseteq g \circ f$.

By definition of set equality:

$I_S = g \circ f$

$\blacksquare$


Also see


Sources