Surjection iff Right Inverse

Theorem

A mapping $f: S \to T, S \ne \varnothing$ is a surjection iff:

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

where:

$g$ is a mapping

$I_T$ is the identity mapping on $T$.

That is, if $f$ has a right inverse.

In general, that right inverse is not unique.

Uniqueness occurs iff $f$ is an injection.

Proof

Proof 1

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

From Identity Mapping is a Surjection, $I_T$ is surjective, so $f \circ g$ is surjective.

So from Surjection if Composite is a Surjection, $f$ is a surjection.

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

• Now, assume $f$ is a surjection. Then:

$\forall y \in T: f^{-1} \left({\left\{{y}\right\}}\right) \ne \varnothing$

Let $f^{-1} \left({\left\{{y}\right\}}\right) = X_y = \left\{{x_{y_1}, x_{y_2}, \ldots}\right\}$

Using the Axiom of Choice, for each $y \in T$ we can choose any of the elements $x_{y_1}, x_{y_2}, \ldots$ to be identified as $x_y$, and thereby define:

$g: T \to S: g \left({y}\right) = x_y$

Then we see that $f \circ g \left({y}\right) = f \left({x_y}\right) = y$

and thus $f \circ g = I_T$.

$\blacksquare$

Proof 2

Take the result Condition for Composite Mapping on Right:

Let $A, B, C$ be sets.

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

Then:

$\operatorname{Im} \left({g}\right) \subseteq \operatorname{Im} \left({f}\right)$

iff:

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

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

Then the above translates into:

$\operatorname{Im} \left({I_T}\right) \subseteq \operatorname{Im} \left({f}\right)$

iff:

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

But we know that $\operatorname{Im} \left({f}\right) \subseteq T = \operatorname{Im} \left({I_T}\right)$.

So by definition of set equality, the result follows.

$\blacksquare$

Proof of Non-Uniqueness

If $f$ is not an injection then:

$\exists y \in T: \exists x_1, x_2 \in S: f \left({x_1}\right) = y = f \left({x_2}\right)$

Hence we have more than one choice in $f^{-1}\left({\left\{{y}\right\}}\right)$ for how to map $g \left({y}\right)$.

This does not happen iff $f$ is an injection.

Hence the result.

$\blacksquare$

Axiom of Choice

This theorem depends on the Axiom of Choice.

Because of some of its bewilderingly paradoxical implications, the Axiom of Choice is considered to be controversial.

Most mathematicians are convinced of its truth and insist that it should nowadays be generally accepted.

However, others consider its implications so counter-intuitive and nonsensical that they adopt the philosophical position that it cannot be true.

Also see

• Injection iff Left Inverse

Sources

• 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 $8$
• T.S. Blyth: Set Theory and Abstract Algebra (1975): $\S 5$: Theorem $5.6$
• H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability (1996): Appendix $\text{A}.7$: Proposition $\text{A}.7.2$