# Help to prove the existance of a function

Let $f:X \rightarrow Y$ be a function. Prove that there exists a function $g:Y \rightarrow X$ such that $f \circ g = I_Y$ if and only if $f$ is a surjection.

I need help on proving the following:

$f$ is a surjection $\Rightarrow \exists g:Y \rightarrow X, f \circ g = I_y$

What I've tried:

$f$ is a surjection $\Rightarrow \forall y \in Y, \exists x \in X, f(x)=y$, definition of a surjection

From here, I thought of constructing a function, $g:Y \rightarrow X$, since all $y$s have some preimage, $x \in X$ . But this will not be possible if $f$ is not injective. In that case, the codomain of $g$ will need to be appropriately restricted, so that $y_1=y_2 \Rightarrow g(y_1)=g(y_2)$. But I can't restrict the codomain of $g$ since the conclusion requires the codomain of $g$ to be exactly $X$. I don't know what else to do. Also, is my attempt anywhere near a solution or am I thinking about this problem in a wrong way?

• The codomain is different from the range. $g$ needn't take on ALL values in $X$. So, you pretty much have the solution already. It's perfectly fine to write $g:Y \mapsto X$ even when the range of $g$ is not all of $X$. – StrangerLoop Jul 29 '14 at 15:52
• See Left and right inverses in Inverse function. – Mauro ALLEGRANZA Jul 29 '14 at 15:52
• @MauroALLEGRANZA I see that the wikipedia article says that constructing $g$ in general requires axiom of choice. If I have not studied the axiom of choice, would my attempt be acceptable? – mauna Jul 29 '14 at 16:28
• See the answer to this post. If you are at the "elementary" level of set-theory, I think would be acceptable if you do not mention AC. But at some point in your proof you have to say "... and now I choose an y ...". Be aware of this :) – Mauro ALLEGRANZA Jul 29 '14 at 16:31

This is a consequence of AXIOM OF CHOICE

• Could you clarify what you mean here? "This" could refer to multiple concepts... and explaining how it's a consequence would be best. – apnorton Jul 29 '14 at 16:22
• Besides what anorton said, is there a way to prove it without relying on the Axiom of Choice? The text I am using does not cover it at all so I am wondering if there are alternative answers – mauna Jul 29 '14 at 16:26
• For each $y\in Y$, you can choose an element $x$ in $f^{-1}(\{y\})$ (wish is not empty by hypothesis ), and put $x=g(y)$ – Hamou Jul 29 '14 at 16:27
• "This" = "$f$ is a surjection $\Rightarrow \exists g:Y\to X,f\circ g=I_Y$" – Hamou Jul 29 '14 at 17:11
• thanks. Could you please also explain where the axiom of choice comes into play (like what anorton asked?) – mauna Jul 30 '14 at 1:58