Surjection iff Right Inverse/Proof 1
Theorem
A mapping $f: S \to T, S \ne \O$ is a surjection if and only if:
- $\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 and only if $f$ has a right inverse.
Proof
Assume $\exists g: T \to S: f \circ g = I_T$.
From Identity Mapping is Surjection, $I_T$ is surjective, so $f \circ g$ is surjective.
So from Surjection if Composite is Surjection, $f$ is a surjection.
Note that the existence of such a $g$ requires that $S$ is non-empty.
Now, assume $f$ is a surjection.
Consider the indexed family of non-empty sets $\set {\map {f^{-1} } y}_{y \mathop \in T}$ where $\map {f^{-1} } y$ denotes the preimage of $y$ under $f$.
Using the axiom of choice, there exists a mapping $g: T \to S$ such that $\map g y \in \set {\map {f^{-1} } y}$ for all $y \in T$.
That is, $\map {\paren {f \circ g} } y = y$, as desired.
$\blacksquare$
Axiom of Choice
This proof depends on the Axiom of Choice.
Because of some of its bewilderingly paradoxical implications, the Axiom of Choice is considered in some mathematical circles 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.
Sources
- 1967: George McCarty: Topology: An Introduction with Application to Topological Groups ... (previous) ... (next): Chapter $\text{I}$: Sets and Functions: Composition of Functions: Theorem $8$
- 1996: H. Jerome Keisler and Joel Robbin: Mathematical Logic and Computability ... (previous) ... (next): Appendix $\text{A}.7$: Inverses: Proposition $\text{A}.7.2$