# Decidability of the Axiom of Choice

Everything that I read regarding Set Theory states that the Axiom of Choice is independent and undecidable within the context of Zermelo-Frankel Set Theory. My question is this: Is there any consistent form of Set Theory stronger than ZF in which the Axiom of Choice IS decidable?

Thanks guys...First time on here =)

---Dan

-
I don't know much about set theory, but I assume you're looking for an answer other than ZFC? – Zev Chonoles Feb 6 '10 at 0:17
Well, C is decidable in ZF-without-C too. And in my reading, the current post says "stronger than ZF". – Theo Johnson-Freyd Feb 6 '10 at 0:28
@Theo: Can you elaborate this? In what sense is the AC decidable in ZF ? – Johannes Hahn Feb 6 '10 at 0:31
A technical comment: instead of "consistent" one should say "relatively consistent", i.e., consistent if ZF is consistent. The point is that the consistency of ZF is not provable from ZF [nor from, as I understand it, by any acceptably "finitistic" formal system], by Godel's Second Incompleteness Theorem. – Pete L. Clark Feb 6 '10 at 0:32
@Johannes: I got confused by that too. I think that when Theo says ZF-without-C he means (ZG + ¬AC), in which AC is clearly decidable. – Anton Geraschenko Feb 6 '10 at 6:35

Assuming the consistency of ZF, the two minimal such theories are ZFC (= ZF + AC) and ZF + ¬AC. However, there are plenty of stronger statements that imply the Axiom of Choice over ZF, such as the Axiom of Constructibility (aka V = L) and V = HOD (every set is ordinal definable). There are also statements that refute the Axiom of Choice over ZF such as the Axiom of Determinacy and various "regularity axioms" such as "every subset of [0,1] is Lebesgue measurable" or "every uncountable subset of [0,1] contains a perfect set."

-
Giving up AC for lebesgue measurability is so shortsighted. =( – Harry Gindi Feb 6 '10 at 1:24
@Harry: And giving up AC for playing infinite games is childish. – François G. Dorais Feb 6 '10 at 1:26
^ This is a great comment. – Harry Gindi Feb 6 '10 at 1:45
I do not know of any serious set theorist that advocates giving up AC. We study determinacy because it gives insight into specific inner models, i.e., choice holds in V (of course) but fails in some inner models (because of, say, the presence of large cardinals in V). And it is not that one studies determinacy in order to play infinite games. It is that determinacy axioms highlight pointclasses of sets of reals that have nice regularity properties. In fact, determinacy can be recovered from appropriate combinations of these regularity properties, so one does not even need to mention games. – Andrés E. Caicedo Feb 23 '11 at 20:50

One should be carefull with the word "consistent". One of the fundamental results in axiomatic set theory is the incompleteness theorem of Gödel that states that any consistent (set) theory that is strong enough to do some specific arithmetic things (and every reasonable set theory should be strong enough to do that) cannot prove its own consistency. In particular: A consistent set theory that is stronger than ZF (in the sense that it implies ZF) cannot proven to be consistent with means of ZF. If it could, ZF would prove its own consistency and would therefore be inconsistent by Gödels theorem. As a result the stronger theory would be inconsistent as well.

Because ZFC "is" consistent (I do believe it is as do propably most other mathematicians who know about Gödel), this means that (absolut) consistency is not a good requirement because we will never know it for sure. ("know" in the sense that someone has a ZF(C)-proof of it)

A better requirement would be that the theory your looking for is relative consistent with ZF(C), i.e. if we assume that ZF(C) is consistent, then the other theory is consistent as well. Example: ZFC is relative consistent to ZF.

There are plenty of theories that are stronger than ZF, relative consitent to ZF and imply the axiom of choice, for example ZF+GCH. A result of Sierpinksi shows that ZF+GCH implies the axiom of choice. Another perhaps more popular example is ZF+(V=L). V=L implies not only the AC but the axiom of global choice, i.e. there is a well-ordering of the whole universe.

-
@JH: Oops, somehow I did not receive this answer as I was writing my comments above. Anyway, +1. – Pete L. Clark Feb 6 '10 at 0:36

There are, of course, exactly two ways for a theory to decide AC. Either it proves that AC is true, or it proves that AC is false.

Consequently, if you have a theory extending ZF and deciding AC, then either your theory includes ZFC or it includes ZF+¬AC. Thus, there are two minimal possibilities which meet your requirement, and any theory extending ZF and deciding AC must extend one of them.

The results of Godel on the constructible universe show that if ZF is consistent, then so is ZF+AC. And the results of Cohen on the forcing method show that if ZF is consistent, then so is ZF+¬AC. So both of these minimal theories are consistent, if ZF itself is consistent.

There are, of course, a huge variety of further extensions of ZFC that are intensely studied in set theory, and you can learn about them in any introductory graduate level set theory text. For example, one will want to know whether V=L, or whether CH holds, or GCH, or Diamond, whether there are Suslin trees or not, or large cardinals, and so on. Similarly, there are also a large variety of further extensions of ZF+¬AC that are studied, some quite intensely. For example, one might want to have the countable AC, or DC, or the Axiom of Determinacy and so on.

-

NF is inconsistent with choice: http://www.pnas.org/content/39/9/972.full.pdf+html

But there aren't even any relative consistency proofs. Interestingly, NF+urelements proves choice and is consistent if Peano Arithmetic is. More about NF here: http://plato.stanford.edu/entries/quine-nf/

-
Choice is consistent with NFU (unlike NF, per Specker's result), but NFU doesn't prove AC outright. – Ed Dean Feb 23 '11 at 21:56

There is an interesting question here: "Are there any set theories in which the question of choice is decided without inserting an axiom tailored to the purpose?"

As Jeremy points out, NF is inconsistent with choice. It's strongly implied in Holmes (PDF), though not stated outright, that the Axiom of Choice is independent of the other axioms of NFU, though it does state outright on p.95 that the problem of proving there are atoms without choice is open: specifically, if it's adopted, Specker's inconsistency proof becomes a proof that there are atoms.

Many set-class theories, in particular NBG and MK, have the axiom of limitation of size, which effectively says that every proper class is the same size. This implies a well-ordering of the class of all sets, and therefore global choice. There is a (very short) Wikipedia article on this axiom.

-
I don't see how you propose to judge whether an axiom is "tailored to the purpose" or not. Would you say that V=L is "tailored to the purpose"? – Oliver Feb 24 '11 at 0:50
I don't really have a general method in mind. If the original author were alive, I suppose I could just ask him. In the case of V=L I don't know enough about the context in which it was proposed, so I'd have to suspend judgment. – Ian Feb 24 '11 at 1:56
Well, Goedel did come up with the constructible universe $L$ in order to prove the consistency of ZFC assuming the consistency of ZF (and the consistency of GCH). So in this sense $V=L$ is tailored to imply AC. On the other hand, if you are inside a model $V$ of ZF, then $L$ is the smallest inner model of ZF that contains all the ordinals. So in this sense $L$ is a canonical object and it happens to satisfy AC (global choice, even). This shows that $V=L$ is a natural statement, independent of the fact that it implies choice. (I am not saying that ZF+$V=L$ is the right framework for math.) – Stefan Geschke Jul 6 '11 at 19:05