MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

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

I've been going over the extremely interesting discussions about Axiom of Choice.

It looks to me like all the "weird" consequences of AC (Banach-Tarski etc) come from using it on uncountable collections of sets.

If, instead, we only believe the Axiom of Countable Choice, do we still get unintuitive consequences in the same sense ?

Apologies in advance if the question is vague.

share|cite|improve this question
Presumably, you want to do all this in classical logic. If you stick to intuitionistic logic then, since the countable axiom of choice has a computable realization, everything proved from it will be computable in a suitable sense. And computable things are typically "intuitive" and not too surprising. – Andrej Bauer May 2 '10 at 10:34
How much of Tychonoff and Hahn-Banach can we prove with countable choice? Perhaps we can show that a countable product of compact spaces is compact and that Hahn-Banach holds for separable spaces? But these would all be nice consequences, not unintuitive ones. – Andrej Bauer May 2 '10 at 15:59
It is consistent with countable choice that a product of nonempty sets may be empty, which I find at least as unintuitive as, say, Banach-Tarski. (Sorry for being deliberately obtuse.) – Dan Petersen May 2 '10 at 16:59
@Dan: The statement "All green cows are from Mars" is also consistent with the axiom of countable choice, but isn't a consequence of it (which is what Cosmonut asked for). Your example is a consequence of the statement "uncountable choice is false", not "countable choice is true". – Paul Siegel May 2 '10 at 17:21
up vote 14 down vote accepted

If you assume the existence of suitable large cardinals, then $L(\mathbb{R})$ is a model of the Axiom of Determinacy $AD$ and the Axiom of Dependent Choice $DC$. In particular, since $DC$ is stronger than the Axiom of Countable Choice $AC_{\omega}$, it follows that $AC_{\omega}$ is also true in $L(\mathbb{R})$. Since $L(\mathbb{R})$ satisfies $AD$, all subsets $X \subseteq \mathbb{R}$ and maps $f: \mathbb{R} \to \mathbb{R}$ are measurable, etc. So it seems extremely unlikely that you will find any unintuitive consequences of $AC_{\omega}$ in the more classical areas of mathematics.

share|cite|improve this answer
Unless, of course, you find it counterintuitive that all subsets of the reals are measurable. – Gerry Myerson May 3 '10 at 0:21
Gerry, Simon wasn't saying that that statement (all sets are measurable) is a consequence of $AC_\omega$, but rather, only that it is consistent with $AC_\omega$. Thus, his argument shows that one cannot expect any of the paradoxes arising from non-measurability to arise as consequences of $AC_\omega$. – Joel David Hamkins May 3 '10 at 0:43
Joel, many thanks. – Gerry Myerson May 3 '10 at 12:40

It seems that many people who express a willingness to use countable AC are often actually thinking of arguments that use a somewhat stronger principle, the principle of Dependent Choices (DC). Both involve making only countably many choices, but the difference is that the DC principle allows one to make countably many choices in succession, so that the later choices can depend on the earlier choices. So the two principles are similar, but it turns out that DC is provably stronger than countable choice. It is DC and not just countable choice that one uses when choosing, for example, a nested sequences of closed balls in a metric space, since the choice of the later balls depends on the earlier-selected larger balls. It is the DC principle rather than mere countable AC that makes many arguments in analysis and measure theory work out. For example, I believe that many of the remarks made in favor of countable choice in the previous questions you mention can be construed as equally supportive of DC.

For this reason, it may be sensible to replace countable choice in your question with DC.

But it turns out that for statements about countable objects, and more generally, for statements expressible in L(R), the consequences of DC and AC are exactly the same. The reason is that if DC holds, then there is a forcing extension of L(R) adding no new reals, but adding a well-ordering of the reals. Thus, the forcing extension L(R)[G] satisfies ZFC with full AC, and has the same L(R) as the original universe. Another way to say it is that the theory ZF + AC is conservative over ZF + DC for statements about L(R), which includes all projective statements (e.g. those involving only quantification over the reals) and more. I give some fuller details in this related MO answer, to a question about DC and countable objects.

In particular, it follows from this that for countable objects, and more generally for statements about L(R), the principles DC and AC have exactly the same paradoxical statements.

There is no need for large cardinals in this argument. Simon's point was that when there are large cardinals, then L(R) has highly regular features indeed, and so the classically paradoxical consequences of AC will not be found among statements about L(R). So this answer is a lower bound in the sense that Simon's is an upper bound.

share|cite|improve this answer

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.