Axiom of Choice: An Invocation Necessary for A Proof on Surjectivity [closed]

Prove that if $f\colon X\rightarrow Y$ is surjective, then there must exist a function $g\colon Y\rightarrow X$ such that $f\circ g=1_Y$, where $1_Y$ is the identity map on $Y$.

-

closed as unclear what you're asking by Andres Caicedo, Hagen von Eitzen, Andrey Rekalo, Davide Giraudo, dtldarekJul 14 '13 at 22:01

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

What, exactly, are you asking? It appears from the title that you know how to prove the stated result. –  Brian M. Scott Jul 14 '13 at 20:37
And your question is whether this proof necessarily makes use of AC? –  Hagen von Eitzen Jul 14 '13 at 20:38
I think the OP wants a proof for the statement. He just so happened to know that the $\sf AC$ is necessary and used that fact to write a descriptive title. –  Git Gud Jul 14 '13 at 20:42

For each $y\in Y$ let $A_y=\{x\in X:f(x)=y\}$, and let $\mathscr{A}=\{A_y:y\in Y\}$. Then $\mathscr{A}$ is a non-empty family of non-empty sets, so it has a choice function $\varphi:\mathscr{A}\to\bigcup\mathscr{A}$; that is, $\varphi(A)\in A$ for each $A\in\mathscr{A}$. Now define $g:Y\to X:y\mapsto\varphi(A_y)$.
This result is known as the Partition principle. It is not known whether it is equivalent to the axiom of choice, or whether it is strictly weaker, but it is independent of $\mathsf{ZF}$.
This is not quite the partition principle, that simply states that whenever there is a surjection $f:A\to B$, then there is an injection $g:B\to A$. –  Andres Caicedo Jul 14 '13 at 21:22