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?

  • 2
    $\begingroup$ 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$. $\endgroup$ – StrangerLoop Jul 29 '14 at 15:52
  • $\begingroup$ See Left and right inverses in Inverse function. $\endgroup$ – Mauro ALLEGRANZA Jul 29 '14 at 15:52
  • $\begingroup$ @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? $\endgroup$ – mauna Jul 29 '14 at 16:28
  • 1
    $\begingroup$ 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 :) $\endgroup$ – Mauro ALLEGRANZA Jul 29 '14 at 16:31

This is a consequence of AXIOM OF CHOICE

  • 2
    $\begingroup$ Could you clarify what you mean here? "This" could refer to multiple concepts... and explaining how it's a consequence would be best. $\endgroup$ – apnorton Jul 29 '14 at 16:22
  • $\begingroup$ 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 $\endgroup$ – mauna Jul 29 '14 at 16:26
  • $\begingroup$ 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)$ $\endgroup$ – Hamou Jul 29 '14 at 16:27
  • $\begingroup$ "This" = "$f$ is a surjection $\Rightarrow \exists g:Y\to X,f\circ g=I_Y$" $\endgroup$ – Hamou Jul 29 '14 at 17:11
  • $\begingroup$ thanks. Could you please also explain where the axiom of choice comes into play (like what anorton asked?) $\endgroup$ – mauna Jul 30 '14 at 1:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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