Surjection iff Right Inverse
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.
Non-Uniqueness
A right inverse of $f$ is in general not unique.
Uniqueness occurs if and only if $f$ is a bijection.
Proof 1
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$
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:
- $\Img g \subseteq \Img f$
- $\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:
- $\Img {I_T} \subseteq \Img f$
- $\exists g: T \to S$ such that $g$ is a mapping and $f \circ g = I_T$.
But we know that:
- $\Img f \subseteq T = \Img {I_T}$
So by definition of set equality, the result follows.
$\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 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.
Also see
Sources
- 1965: J.A. Green: Sets and Groups ... (previous) ... (next): Chapter $3$. Mappings: Exercise $6$
- 1966: Richard A. Dean: Elements of Abstract Algebra ... (previous) ... (next): $\S 1.3$: Exercise $5$
- 1968: Ian D. Macdonald: The Theory of Groups ... (previous) ... (next): Appendix: Elementary set and number theory
- 1978: John S. Rose: A Course on Group Theory ... (previous) ... (next): $0$: Some Conventions and some Basic Facts
- 1982: P.M. Cohn: Algebra Volume 1 (2nd ed.) ... (previous) ... (next): Chapter $1$: Sets and mappings: $\S 1.3$: Mappings: Exercise $5$
- 2000: James R. Munkres: Topology (2nd ed.) ... (previous) ... (next): $1$: Set Theory and Logic: $\S 2$: Functions: Exercise $2.5 \ \text{(a)}$