Prove that if $f:X\to Y$ is a surjective function between sets, then there must exist a function $g:Y\rightarrow X$ such that $f\circ g=1_Y$.

I know that the identity function is onto, and if $f$ has right inverse, then $f$ must be onto; although, I haven't seen a proof of this. A good hint would be nice.

  • 5
    $\begingroup$ Hint: axiom of choice. $\endgroup$
    – Berci
    Jul 10, 2013 at 21:51

2 Answers 2


Suppose that $f\colon A\to B$ is surjective, then for every $b\in B$ the set $F_b=\{a\in A\mid f(a)=b\}$ is non-empty. Therefore, using the axiom of choice, there is some $g$ which selects an element from $F_b$, that is $g(F_b)\in F_b$.

Now show that $g$ is actually a function from $B$ into $A$, and that $g$ is injective.

(You can't avoid the axiom of choice in this proof, because in fact this statement is equivalent to the axiom of choice, and often is taken as the statement of the axiom of choice.)


What would an inverse look like? For every element $y$ of $Y$, it would send $y$ to an element of $X$ in the preimage of $Y$. You can just make up such a map by choosing $g(y)$ to be any point in $f^{-1}(y).$

  • 9
    $\begingroup$ $\Large{\ldots\rm choosing \ldots}$ $\endgroup$
    – Pedro
    Jul 10, 2013 at 23:15

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .