Injection iff Left Inverse

Theorem

A mapping $f: S \to T, S \ne \varnothing$ is an injection iff:

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

where $g$ is a mapping.

That is, iff $f$ has a left inverse.

In general, that left inverse is not unique.

Uniqueness occurs under either of two circumstances:

• $S$ is a singleton
• $f$ is a surjection.

Proof

Proof 1

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

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

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

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

• 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$. Then we define:

$g \left({y}\right) = \begin{cases} x_0: & y \in T \setminus \operatorname{Im} \left({f}\right) \\ f^{-1} \left({y}\right): & y \in \operatorname{Im} \left({f}\right) \end{cases} $

Because $f$ is an injection, we know we can do this, as $f^{-1}: \operatorname{Im} \left({f}\right) \to S$ is a mapping, from Injection iff Inverse of Image Mapping.

So, for all $x \in S$, $g \circ f \left({x}\right) = g \left({f \left({x}\right)}\right)$ is the unique element of $S$ which $f$ maps to $f \left({x}\right)$.

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

iff:

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

iff:

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

iff:

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

which is our result.

$\blacksquare$

Proof of Non-Uniqueness

• If $f$ is a surjection, then $T \setminus \operatorname{Im} \left({f}\right) = \varnothing$, and we have that $g = f^{-1}$.

As $f^{-1}$ is uniquely defined $g$ is itself unique.

• If $S$ is a singleton then there can only be one mapping $g: T \to S$:

$\forall t \in T: g \left({t}\right) = s$

• If $f$ is not a surjection, then $T \setminus \operatorname{Im} \left({f}\right) \ne \varnothing$.

Let $t \in T \setminus \operatorname{Im} \left({f}\right)$.

We can now choose any $x_0 \in S$ such that $g \left({t}\right) = x_0$.

If $S$ is not a singleton, such an $x_0$ is not unique.

Hence the result.

$\blacksquare$

Also see

• Surjection iff Right Inverse

Sources

• Paul R. Halmos: Naive Set Theory (1960)... (previous)... (next): $\S 10$: Inverses and Composites: Exercise $\text{(i)}$
• Seth Warner: Modern Algebra (1965)... (previous)... (next): Exercise $5.6$
• Richard A. Dean: Elements of Abstract Algebra (1966): $\S 0.4$: Theorem $6$
• Richard A. Dean: Elements of Abstract Algebra (1966): $\S 1.3$: Exercise $5$
• George McCarty: Topology: An Introduction with Application to Topological Groups (1967): $\text{I}$: Theorem $7$
• T.S. Blyth: Set Theory and Abstract Algebra (1975): $\S 5$: Theorem $5.4$
• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): Appendix $\text{A}.7$: Proposition $\text{A}.7.1$