8
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Hint: axiom of choice. $\endgroup$ – Berci Jul 10 '13 at 21:51
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

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

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.