Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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

share|cite|improve this answer
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.

share|cite|improve this answer
up vote 0 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.