# Assuming a choice function for a set $S$

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?

-

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

-
Now I'm glad I asked because I suspected the answer was no. – Rudy the Reindeer Oct 31 '12 at 9:08
Actually, don't I have to assume that $f: S \to \mathbb N$ is also order-preserving in my second paragraph? – Rudy the Reindeer Oct 31 '12 at 10:09
I guess one part of my question boils down to this. – Rudy the Reindeer Oct 31 '12 at 11:53
@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. – Brian M. Scott Oct 31 '12 at 16:16
@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). – Brian M. Scott Nov 1 '12 at 13:08

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.

-

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.

-
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. – Brian M. Scott Nov 2 '12 at 7:48
Dear @BrianM.Scott, there was no point: I was confused. : / – Rudy the Reindeer Nov 2 '12 at 7:50