Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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?


share|cite|improve this question
up vote 2 down vote accepted

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.

share|cite|improve this answer
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$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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