1
$\begingroup$

As mentioned in the title I should prove that a function $f\colon X\to Y$ is surjective if and only if there exists a function $g\colon Y\to X$ such that $f\circ g=id_Y$ using the well ordering Theorem (i.e. that every set can be well-ordered).

Of course the statement is well known and not so difficult to prove but I don't know how to use the well ordering Theorem for the proof.

$\endgroup$
8
  • 1
    $\begingroup$ As far as I know, the wel-ordering principle is a statement about the positive integers, are $X$ and $Y$ subsets of $\mathbb{N}$? $\endgroup$
    – Javi
    Aug 11, 2018 at 9:28
  • 1
    $\begingroup$ maybe you're referring to the well ordering theorem which states that every set can be well-ordered. $\endgroup$
    – Kenny Lau
    Aug 11, 2018 at 9:31
  • 1
    $\begingroup$ I'm curious, how would you prove it without using well-order? I find it much more natural to use it than to use some sort of choice. $\endgroup$
    – Git Gud
    Aug 11, 2018 at 9:35
  • $\begingroup$ In my assignment it is stated with the well ordering principle, but I agree after looking up the exact terminology that the well ordering Theorem which states that every set can be well-ordered must be the right name. But I still don't know how to prove the statment using that. $\endgroup$
    – Algebra
    Aug 11, 2018 at 9:36
  • 1
    $\begingroup$ Yes, when you choose a preimage for each point, you are using the axiom of choice. It’s easy to see why the well ordering principle implies the axiom of choice, cause it allows you to define your choices as the least. $\endgroup$ Aug 11, 2018 at 10:36

1 Answer 1

4
$\begingroup$

By the well-ordering principle, $X$ can be well-ordered.

"$\Rightarrow$" For every $y\in Y$, consider $f^{-1}(y)\subset X$ which is a non-empty subset, because $f$ is surjective. Using the well-order it has a least element $x_y$. Now, define $g(y):=x_y$. Then $f(g(y))=f(x_y)=y$, so $f\circ g=id_Y$.

"$\Leftarrow$" $id_Y$ is surjective, so $f\circ g$ is surjective, so $f$ must be surjective. No need of the well ordering principle here.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .