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

1 Answers 1

3

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
    @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