Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question

closed as unclear what you're asking by Andres Caicedo, Hagen von Eitzen, Andrey Rekalo, Davide Giraudo, dtldarek Jul 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

1 Answer 1

up vote 5 down vote accepted

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}$.

share|improve this answer
ZF? ZF is what? en.wikipedia.org/wiki/Zermelo–Fraenkel_set_theory –  Trancot Jul 14 '13 at 21:15
According to this paper, the partition principle says that a partition is not larger than the underlying set. The stronger form asked for here is however equivalent to AC, it is basically the category theorists version of AC ("Epimorphisms split."). –  Michael Greinecker Jul 14 '13 at 21:17
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
Thank you, @BrianM.Scott. –  Trancot Jul 14 '13 at 21:39
@Michael: Did you get the link from my recent answer on MO? –  Asaf Karagila Jul 15 '13 at 0:07

Not the answer you're looking for? Browse other questions tagged or ask your own question.