4
$\begingroup$

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

2 Answers 2

2

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.

  • 0
    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.2012-10-06
  • 0
    @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.2012-10-06
-2

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

  • 1
    But why can you pick such $g(y)$?2012-10-06
  • 0
    @AsafKaragila I was going to ask the same question.2012-10-06