# Why is the axiom of choice separated from the other axioms?

I don't know much about set theory or foundational mathematics, this question arose just out of curiosity. As far as I know, the widely accepted axioms of set theory is the Zermelo-Fraenkel axioms with the axiom of choice. But the last axiom seems to be the most special out of these axioms. A lot of theorems specifically mention that they depend on the axiom of choice. So, what is so special about this axiom?

I know that a lot of funny results occur when we assume the axiom of choice, such as the Banach-Tarski paradox. However, we are assuming the other ZF axioms at the same time. So why do we blame it to the axiom of choice, not the others? To me, the axiom of regularity is less convincing than the axiom of choice (though it's probably due to my lack of understanding).

-
Wow, there's even an axiom-of-choice tag. – bjorn Apr 15 '12 at 9:48
For one thing AC is quite a bit longer to state formally than the other axioms of ZFC, since it requires formulating either the property of being a function or of being a well-ordering. Both are certainly possible, but te expressions aren't all that appetising, and you'll not that for instance AC is the only axiom of ZFC that is not actually spelled out on Wikipedia, nor in the book(s) that served as a source for it. – Marc van Leeuwen Apr 15 '12 at 10:09
@Marc: That is not true. It is not longer than the replacement axiom. – Asaf Karagila Apr 15 '12 at 10:12
I am no expert but I think ZF is more or less equivalent to PA plus Cons(PA) (=the axiom of infinity), so it is really a basic theory. You would not consider resting to it. The axiom of regularity is more a restriction on what sets can be constructed, while the axiom of choice adds sets, and paradoxical ones at that. It really is apart, for very practical reasons. It changes the way you do mathematics, the way you build objects. – plm Apr 15 '12 at 10:24
I am not sure that "more or less equivalent" means, but ZF proves the consistency of finite type theory, which includes second-order arithmetic, which is stronger than PA + Infinity, so ZF is not equivalent to the latter in terms of consistency strength. – Carl Mummert Apr 15 '12 at 12:32

This is a historical issue really.

Originally set theory was developed by Cantor and the well ordering principle was somewhat assumed in the background (e.g. Cantor's proof of the Cantor-Bernstein theorem was a corollary from the fact that every two cardinalities are comparable).

In 1904 Zermelo formulated the axiom of choice and proved its equivalence to the well ordering principle. He later formulated more axioms which described our intuition about sets, therefore removing the "naivity" from the Cantorian set theory. He did not add the axiom of foundations, nor the schema of replacement. Those were the result of Skolem and Fraenkel which were popularized by von Neumann.

The axiom of choice remained controversial, the thought that the continuum can be well-ordered was mind boggling and caused many people feel uneasy about this axiom. Further results like the Banach-Tarski paradox did not help to accept this axiom either.

Prior to set theory most mathematics was somewhat constructive in the sense that things were finitely generated or approximated by finitary means (e.g. limits of sequences). It requires quite the leap of faith to go from things you can pretty much write down to things which you cannot describe but only prove their existence. In this sense the axiom of choice augments the way we do mathematics by allowing us to discuss objects which we cannot describe in full.

It was questionable, therefore, whether this axiom is even consistent with the rest of the axioms of set theory. Gödel proved this consistency in the late 1940's while Cohen proved the consistency of its negation in the 1960's (it is important to remark that if we allow non-set elements to exist then Fraenkel already proved these things in the 1930's).

Nowadays it is considered normal to assume the axiom of choice, but there are natural situations in which one would like to remove it or find himself in universes where the axiom of choice does not hold. This makes questions like "How much choice is needed here?" important for these contexts.

-
Happy birthday, Asaf! – Gerry Myerson Apr 15 '12 at 10:19
@Gerry: Thanks, but you're a day late.. :-) – Asaf Karagila Apr 15 '12 at 10:23
In this answer I miss two further reasons for setting choice apart: looking at Zermelo set theory the axiom of choice is special in two respects: 1) The naive idea of the nonconstructive nature of choice which seems to be in contrast to the other axioms that intuitively give well-determined sets 2) Choice is special in that it isn't a special case of the problematic Unrestricted Comprehension principle. – t.b. Apr 15 '12 at 11:07
@t.b.: It's funny you say that. I just read my answer again and came to the same conclusion about the first part. I was on my way to edit when your comment popped into my inbox! :-) – Asaf Karagila Apr 15 '12 at 11:08
I guess my "two" reasons are two ways of expressing the same (and extensionality isn't a special case of comprehension either). Two more things (this time two for real): 1) It's Fraenkel and 2) a belated Happy Birthday! – t.b. Apr 15 '12 at 11:16

In ZFC, there are three particular axioms that are less obvious than the others: regularity, replacement, and choice. (Replacement is an axiom scheme, but we can ignore that difference for this purpose).

Of these, regularity (well foundedness of $\in$) is the easiest to deal with. Although there is no reason to think that our naive conception of sets eliminates the possibility that there is a set which is a member of itself, it also turns out that we essentially never construct such sets in the course of ordinary mathematics. Thus the axiom of regularity does little harm (in removing things that we care about). It does do some good, as well-founded models of set theory are much more convenient to study. Most mathematicians never think about it.

The axiom of replacement is odd because it is hard to motivate directly from the notion of the cumulative hierarchy; replacement is essentially about the length of the ordinals rather than about which sets exist at each level of the cumulative hierarchy. There are very few mathematical arguments outside of set theory that actually use this axiom, though. The main examples are the Borel determinacy theorem and some theorems from category theory. Thus most mathematicians rarely notice it, it is not mentioned in many undergraduate books outside set theory, and except for set theorists I expect few would be able to state it without thought.

The axiom of choice is odd because it is a set-existence principle, but as t.b. says in a comment it is not implied by the other set-existence scheme in ZFC, the separation scheme. Unlike replacement, though, the axiom of choice can be motivated from the naive construction of the cumulative hierarchy. Historically, the axiom of choice was a flashpoint for certain discussions about constructiveness in mathematics, and for this reason, many authors in the past marked results that used the axiom of choice so that it was clear when it was used. This habit has decreased over time as the arguments from the early 20th century have faded somewhat into history; a side-effect of the habit is that it reinforced the lingering idea that there was something unique about the axiom of choice compared to the rest of ZFC.

All three of these axioms (regularity, replacement, choice) are, at various times, separated off from the rest of ZFC, leaving behind weaker set theories. The main reason that people think of the axiom of choice as special, rather than regularity or replacement, is that the axiom of choice has been the one that is most discussed in popularizations and undergraduate textbooks. But from the point of view of ZFC it is not at all the only axiom that requires effort to motivate.

-
I always think of replacement as a very natural thing: if we have a function whose domain is a set then its image is also a set. Furthermore, in "modern" categorical views this really means that there is some "unlimited" richness in sets, and every function is a morphism in the category of sets. This is better than the separation axiom schema which only says that a subclass of a set is a set - but that too is a very natural thing to assume. Perhaps I just did "enough" set theory to feel those are very natural. – Asaf Karagila Apr 15 '12 at 12:37
@Asaf: the issue is that we can naively make the cumulative hierarchy, and as long as there is no last ordinal it will satisfy most of the axioms of ZFC, but replacement requires us for the first time to assume something stronger about the order type of the ordinals. Shoenfield went into this in depth in his article in the Handbook of Mathematical Logic. – Carl Mummert Apr 15 '12 at 12:40
Thank you for the reference. I will take a look sometime soon. – Asaf Karagila Apr 15 '12 at 12:42
This is great Carl, I have just seen you do research in inverse mathematics. I really feel replacement is very natural, like Asaf, it feels harmless, but I may be wrong. Are there weird constructions using it? And if we use other languages, like arithmetic, is it not implied by very natural axioms? It has a similar flavor to union and pairing. So, what do you think about conjecturing that 2nd-order arithmetic is equivalent (in a reasonable way) to ZF-Power Set? – plm Apr 15 '12 at 15:28
@plm: For the strength of ZFC without powerset, see arxiv.org/abs/1110.2430 – Carl Mummert Apr 15 '12 at 18:12

The basic axiom of "naive set theory" is general comprehension: For any property $P$, you may form the set consisting of all elements satisfying $P$. Russell's paradox shows that general comprehension is inconsistent, so you need to break it down into more restricted types of comprehension.

The other axioms of ZF (except for well-foundedness) are all special cases of general comprehension. For example, the Power Set axiom asserts that the class of all subsets of $X$ is a set. Replacement with respect $\phi(x,y)$ asserts that the class of pairs $(x,y)$ satisfying $\phi(x,y)$ is a set. Separation asserts is obviously a sub-case of general comprehension.

Choice is very different, because it asserts the existence of a set which does not satisfy a specific defining sentence.

-

I'd like to add a quote (for which I forgot the reference) which I think, goes like this:

The axiom of choice is obviously true, the well-ordering theorem is obviously false, and nobody knows about Zorn's lemma.

(Please correct me if I remembered it wrong...)

-
This should really be a comment. (The Wikipedia page for the Axiom of choice attributes this quote to Jerry Bona) – Asaf Karagila Apr 15 '12 at 12:47
This is usually attributed to Jerry Bona in the form "The Axiom of Choice is obviously true, the Well–Ordering Principle is obviously false; and who can tell about Zorn’s Lemma?" – t.b. Apr 15 '12 at 12:48
Thanks! Probably a comment would have been better... However, I thought that the equivalence of these three things and their anticipation by mathematicians can shed some light on why this axiom is somehow different than the others... – Dirk Apr 15 '12 at 12:51
I have to say that knowing a few more equivalents I can honestly say that these three are far far from being surprising. – Asaf Karagila Apr 15 '12 at 13:37
Hmm...obviously an extremely old answer, but I was just wondering why the axiom of choice is necessary if Zorn's lemma is equivalent and can be proved using just ZF? – Evan Zamir May 20 at 0:35