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.

  • 1
    Of course if you assume that some set $S$ admits a well-order, then you don’t need AC to say that $S$ admits a well-order. But what’s the point? In general you find yourself needing a well-order on a particular set that you already have in hand, and without AC you can’t guarantee that there is one. ‘Let $\langle S,\preceq\rangle$ isn’t likely to come up other than in the context of proving theorems about well-orders.2012-11-02
  • 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
    Now I'm glad I asked because I suspected the answer was no.2012-10-31
  • 0
    Actually, don't I have to assume that $f: S \to \mathbb N$ is also order-preserving in my second paragraph?2012-10-31
  • 0
    I guess one part of my question boils down to [this](http://chat.stackexchange.com/transcript/message/6707353#6707353).2012-10-31
  • 1
    @MattN.: I think that you may have been confusing yourself with an irrelevance. If $\langle,\preceq\rangle$ is a well-order, and $f:X\to S$ is a bijection, then (as you concluded for $X=\Bbb N$ with the usual order) $S$ is well-orderable by $s\le t$ iff $f^{-1}(s)\preceq f^{-1}(t)$ irrespective of any other order on $S$ that you may already have in hand. If, however, $f$ is strictly order-preserving with respect to some existing order on $S$, then that existing order is itself a well-order.2012-10-31
  • 0
    Yes! Exactly. Thank you very much! And there is an $X$ missing on the first line of your comment, right?2012-10-31
  • 0
    Sorry, @Brian, could you check my edit [here](http://math.stackexchange.com/questions/190747/finding-a-choice-function-without-the-choice-axiom)? That would be very nice of you.2012-11-01
  • 0
    Hm... In the threads you linked both sets are concrete examples of sets where one needs AC to construct a choice function. But my question is about assuming that we have a choice function without constructing it. For example, if I was writing a proof or lecture notes and I'd write "Let $S$ be a set and $f: P(S)\setminus \{\varnothing\} \to S$ a choice function..." -- would this make me be in ZFC or would I still be in ZF? Thank you for your help!2012-11-01
  • 1
    @MattN.: ZFC, unless you know something special about $S$. You **always** need AC, unless there is something special about the set that allows you actually to construct a choice function (e.g., being well-ordered).2012-11-01
  • 0
    Dear @Brian, I posted an answer of my own. I think you might have misunderstood my question. Sometimes it is difficult to ask a clear question, I apologise.2012-11-02
  • 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.