Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers 2

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|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
add comment

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

share|improve this answer
1  
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
add comment

Your Answer

 
discard

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.