# Finding an inverse injection for a surjection

Question:

Let $X$ and $Y$ be sets, and let $f\colon X\to Y$ be a surjection. Prove that there is an injection $g\colon Y\to X$ such that $f(g(y)) = y$ for every $y\in Y$.

I do not have an idea how to prove this theorem. I could not even find a starting point. Could you please give me a hint?

Regards

-

This cannot be proved "naively". Indeed this question is an equivalent formulation of an axiom known as The Axiom of Choice.

The axiom of choice says that given a family of non-empty sets, we can choose one element from each member of the family.

Using the axiom of choice, note that for every $y\in Y$ the set $f^{-1}(y)$ is non-empty. We therefore have a function which chooses one element from each preimage, call it $g$. This function is as wanted, since $g(y)\in f^{-1}(y)$ and therefore $f(g(y))=y$ as wanted, this also implies $g$ is injective because if $y_1\neq y_2$ then $g(y_1)$ and $g(y_2)$ are taken from disjoint sets.

-
thank you once more for your reply. I am wondering if there exists a book which includes theorems and proofs about sets&functions that I can check for help. Because for example I spent to much time to prove this question naively but if I had a book like that I would just look up and find the answer. – Amadeus Bachmann Oct 6 '12 at 23:09
@Zxy: Well, that depends on what you are looking to do with set theory. I think that you would do fine with an introductory chapter in calculus/algebra books or so. If you wish to study more set theory, there are some questions on the site about references for introductory set theory. – Asaf Karagila Oct 6 '12 at 23:16

Just pick any $g(y)\in f^{-1}\{y\}$ for every $y$.

-
But why can you pick such $g(y)$? – Asaf Karagila Oct 6 '12 at 22:58
@AsafKaragila I was going to ask the same question. – Amadeus Bachmann Oct 6 '12 at 23:05