Surjection iff Epimorphism in Category of Sets
Theorem
Let $\mathbf{Set}$ be the category of sets.
Let $f: X \to Y$ be a morphism in $\mathbf{Set}$, i.e. a mapping.
Then $f$ is a surjection if and only if it is an epimorphism.
Proof
Necessary Condition
Suppose that $f$ is surjective.
Suppose further that we have mappings $g, h: Y \to Z$ such that $g \ne h$.
Then necessarily there exists some $y \in Y$ such that $\map g y \ne \map h y$ by Equality of Mappings.
As $f$ is surjective, it follows that there is an $x \in X$ such that $\map f x = y$.
Hence, we conclude that:
- $\map g {\map f x} \ne \map h {\map f x}$
which, again by Equality of Mappings, means that $g \circ f \ne h \circ f$.
Therefore, $f$ is epic, by the Rule of Transposition.
$\Box$
Sufficient Condition
Suppose that $f: X \twoheadrightarrow Y$ is an epimorphism.
By definition of surjection, it will suffice to show that:
- $\forall y \in Y: \exists x \in X: \map f x = y$
Let us reason by contradiction.
So suppose $f$ were not surjective.
Then there would be an $y_0 \in Y$ such that:
- $\forall x \in X: \map f x \ne y_0$
Consider the mappings defined by:
- $g: Y \to Y \cup \set Y, \map g y := y$
- $h: Y \to Y \cup \set Y, \map h y := \begin{cases} y & \text{if } y \ne y_0 \\
Y & \text{if } y = y_0 \end{cases}$
The assumption on $f$ yields that $g \circ f = h \circ f$.
Since $h \ne g$, it follows that $f$ cannot be epic.
This contradiction shows that $f$ is necessarily surjective.
$\blacksquare$
Sources
- 2010: Steve Awodey: Category Theory (2nd ed.) ... (previous) ... (next): $\S 2.1$
- 2010: Steve Awodey: Category Theory (2nd ed.) ... (next): $\S 2.8$: Exercise $2.1$