2
$\begingroup$

What I understand so far:

If $S$ is any set then AC gives us a choice function, that is, $f: P(S)\setminus \{\varnothing \} \to S$ such that $f$ returns an element of $A \in P(S) \setminus \{\varnothing \}$.

Assume we have a bijection $f: S \to \mathbb N$. Then $S$ is well-ordered (since $\mathbb N$ is) and we know that we can explicitly give a choice function if $S$ is well-ordered: define $f: P(S) \setminus \{ \varnothing \} \to S$ to be the function that returns the least element of $A$.

Hope my understanding so far is correct.


Now assume we have a set $S$ for which we also assume that we have a choice function $f: P(S)\setminus \{ \varnothing \} \to S$. Does one need AC to assume the existence of such a choice function?

3 Answers 3

0

No, one does not need choice. In the absence of AC, $S$ might or might not be well-ordered. For example $S = \{1,2,3\}$ certainly admits a choice function even without AC. So it is perfectly fine, in ZF, to assume that $S$ is a set that is well-ordered.

It's the same as saying "Let $f$ be a continuous function...". Of course, not all functions are continuous but assuming that we have an $f$ that is, is a perfectly ok thing to do.

  • 0
    Dear @BrianM.Scott, there was no point: I was confused. : /2012-11-02
3

Yes, in general. See Asaf’s answers here and here for the case in which $S=\Bbb R$.

  • 0
    I think I made my question confusing by using the word arbitrary.2012-11-02
1

To prove the existence of a choice function on $P(S)\setminus\{\varnothing\}$, for an arbitrary $S$, you need to assume that $S$ can be well-ordered. If this is true in ZF then you are done, otherwise you need some choice.

In fact such choice function exists if and only if $S$ can be well-ordered.

Your answer gives an example for sets which can be well-ordered in ZF, and therefore the existence of such choice function can be proved in ZF. On the other hand, proving such function exists for $S=\mathbb R$ is impossible without assuming some choice.

Of course, if you assume that such $f$ exists, then you need no choice to prove such $f$ exists... but that is begging the question.