Existence of surjection implies existence of injection?

Question

Let $A$ and $B$ be sets. If there exists a surjection $f : A \to B$ then there exists an injection $g : B \to A$.

Proof: given $b \in B$ select an element $a \in f^{-1}(b)$. Denote this element by $g(b)$. Then $g(b) \in f^{-1}(b)$ so that $f(g(b)) = b$. Consequently $g(b_1) = g(b_2)$ implies $f(g(b_1)) = f(g(b_2))$ so that $b_1 = b_2$. We conclude $g$ is an injection. QED

Is the axiom of choice required to make this argument rigorous?

Answer 1

I don't have a proof that the existence of any injection depends on the axiom of choice, but the existence of a right inverse is equivalent to AC, as follows. Let $X$ be a set not containing $\emptyset$ and consider the set $Y = \{(z, A)\ |\ z\in A \in X\}$. Define $f:Y\rightarrow X$ by $f((z,A)) = A$. If $g$ is a right inverse of $f$, then $g^*(A)$ given by the the first element of the ordered pair $g(A)$ is a choice function.

Answer 2

It is. In fact, I believe it can be show that the universal truth of this theorem is equivalent to the axiom of choice.