Proof that a function is surjective iff it has a right inverse

Proof

We prove the two directions separately. Only the second direction uses the axiom of choice.

1. Let $f \colon A \to B$ be a function.
2. First suppose that $f$ has a right inverse $h \colon B \to A$. So $f(h(b)) = b$ for each $b \in B$.
3. Let $b \in B$ and put $a = h(b) \in A$. By step 2, $f(a) = b$. So $f$ is surjective.
4. Now suppose that $f$ is surjective. For $b \in B$, let $F_b = f^{-1}(\set{b}) = \set{a \in A \mid f(a) = b}$ be the preimage of $\set{b}$.
5. Since $f$ is surjective, each $F_b$ is nonempty. Let $X = \set{F_b \mid b \in B}$. Then $X$ is a set of nonempty sets.
6. By the axiom of choice, there is a choice function $c \colon X \to \bigcup X$ with $c(S) \in S$ for each $S \in X$.
7. Each $F_b$ is a subset of $A$, so $\bigcup X \subseteq A$. Define $h \colon B \to A$ by $h(b) = c(F_b)$.
8. Let $b \in B$. By step 6, $h(b) = c(F_b) \in F_b$. By the definition of $F_b$, this says $f(h(b)) = b$.
9. By step 8, $f \circ h = \mathrm{id}_B$, where $\mathrm{id}_B$ is the identity function and $\circ$ is composition. So $h$ is a right inverse of $f$.
10. By steps 3 and 9, $f$ is surjective if and only if $f$ has a right inverse.