The statement that surjective maps are epimorphisms in the category of sets can be shown in a constructive way.


What about the inverse?


Is it possible to show that every epimorphism in the category of sets is surjective without reverting to a proof by contradiction / negation?



In the category of sets epimorphisms are surjective - Constructive Proof?
**Theorem:** Every epi is surjective.


*Proof.*
Let $h : A \to B$ be an epimorphism. We define maps $f, g : B \to \mathcal{P}(B)$ by
\begin{align\*}
 f(b) &= \{b\} \cap \mathrm{im}(h)\\
 g(b) &= \{b\}
\end{align\*}
where we recall that $\mathrm{im}(h) = \{b \in B \mid \exists a \in A \,.\, h(a) = b\}$.


For every $a \in A$ we have $f(h(a)) = \{h(a)\} = g(h(a))$, therefore $f = g$ as $h$ is epi. Now, for every $y \in B$ we have $\{y\} = g(y) = f(y) = \{y\} \cap \mathrm{im}(h)$, therefore $y \in \mathrm{im}(h)$. QED.


**Supplemental 2022-01-09:** Here is an improved version which uses a smaller codomain. We write $\Omega$ for the subobject classifier (the set of truth values).


*Proof.*
Let $h : A \to B$ be an epimorphism and $b \in B$. We define maps $f, g : B \to \Omega$ by
\begin{align\*}
 f(b') &{}\mathbin{{:}{=}} (b = b' \land \exists a \in A . h(a) = b')\\
 g(b') &{}\mathbin{{:}{=}} (b = b').
\end{align\*}


For every $a \in A$ we have
\begin{align\*}
 f(h(a)) &\Leftrightarrow (b = h(a) \land \exists a' \in A . h(a') = h(a)) \\
 &\Leftrightarrow (b = h(a)) \\
 &\Leftrightarrow g(h(a)),
\end{align\*}
therefore $f = g$ as $h$ is epi. Now
\begin{align\*}
 \top &\Leftrightarrow b = b \\
 &\Leftrightarrow g(b) = f(b) \\
 &\Leftrightarrow b = b \land \exists a \in A . h(a) = b \\
 &\Leftrightarrow \exists a \in A . h(a) = b. \quad \Box
\end{align\*}


