# Existence of surjection implies existence of injection? [duplicate]

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?

## marked as duplicate by Andrés E. Caicedo, Zach L., Sujaan Kunalan, user87543, TZakrevskiyDec 13 '13 at 9:42

• See also here. – Andrés E. Caicedo Dec 13 '13 at 2:11
• Without choice, we can have surjections without injections. We can in fact have an equivalence relation on $\mathbb R$ such that there are more equivalence classes than reals. – Andrés E. Caicedo Dec 13 '13 at 2:12
• @AndresCaicedo that last statement is surprising. Do you have a link or a citation? – Umberto P. Dec 13 '13 at 2:15
• Yes. See for example here. – Andrés E. Caicedo Dec 13 '13 at 2:20
• Just to be explicit: As shown in the links, it is an open problem whether your statement is equivalent to the (full) axiom of choice. It certainly needs at least some amount of choice to be proved. – Andrés E. Caicedo Dec 13 '13 at 17:13

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.
• @ncmathsadist I'm well aware that Zorn's Lemma is equivalent to the axiom of choice, but I don't see how that's relevant to this discussion. Your link to planetmath just reiterates the fact that "every surjection splits" is equivalent to the axiom of choice, which I commented on above, and which is the content of the accepted answer. In Asaf's answer here math.stackexchange.com/a/192486/7062, he says that it's still open whether "surjection $X\rightarrow Y$ implies injection $Y\rightarrow X$" implies the axiom of choice, which is what you claim. – Alex Kruckman Dec 13 '13 at 2:44