[picture of Bertrand Russell's shoes and socks] Click here to go to Eric Schechter's main web page

 

a home page for the
AXIOM  OF  CHOICE
-- an introduction and links collection by
Eric Schechter, Vanderbilt University

The Axiom of Choice (AC) was formulated about a century ago, and it was controversial for a few of decades after that; it might be considered the last great controversy of mathematics. It is now a basic assumption used in many parts of mathematics. In fact, assuming AC is equivalent to assuming any of these principles (and many others):

AC has many forms; here is one of the simplest:

Axiom of Choice. Let C be a collection of nonempty sets. Then we can choose a member from each set in that collection. In other words, there exists a function f defined on C with the property that, for each set S in the collection, f(S) is a member of S.

The function f is then called a choice function.

To understand this axiom better, let's consider a few examples.

The controversy was over how to interpret the words "choose" and "exists" in the axiom: In effect, when we accept the Axiom of Choice, this means we are agreeing to the convention that we shall permit ourselves to use a hypothetical choice function f in proofs, as though it "exists" in some sense, even in cases where we cannot give an explicit example of it or an explicit algorithm for it. (For an introduction to constructivism, you might take a look at my paper on that subject. The term has rather different, slightly related meanings in advanced mathematics and in mathematics education; I am referring to the former meaning here.)

To assert that a mathematical object "exists," even when you cannot give an example of it, is a little bit like this: Suppose that one day you go to a football game by yourself. There are thousands of other people in the stadium, but you don't know the names of any of them. (And let's suppose you're shy, so you're not about to ask anyone their name.) Then you know those people have names, but you cannot give any of those names. (Admittedly, this is only a metaphor, and not a perfect one; don't make too much of it.)

The "existence" of f -- or of any mathematical object, even the number "3" -- is purely formal. It does not have the same kind of solidity as your table and your chair; it merely exists in the mental universe of mathematics. Many different mathematical universes are possible. When we accept or reject the Axiom of Choice, we are specifying something about which mental universe we're choosing to work in. Both possibilities are feasible -- i.e., neither accepting nor rejecting AC yields a contradiction; that fact follows from models devised by Gödel and Cohen. However, most "ordinary" mathematicians -- i.e., most mathematicians who are not logicians or set theorists -- accept the Axiom of Choice chiefly because their work is simpler with the Axiom of Choice than without it.

Bertrand Russell was more famous for his work in philosophy and political activism, but he was also an accomplished mathematician. His book Introduction to Mathematical Philosophy includes some discussion of AC. Here is my paraphrasing of part of what he said:

To choose one sock from each of infinitely many pairs of socks requires the Axiom of Choice, but for shoes the Axiom is not needed.
The idea is that the two socks in a pair are identical in appearance, and so we must make an arbitrary choice if we wish to choose one of them. For shoes, we can use an explicit algorithm -- e.g., "always choose the left shoe." Why does Russell's statement mention infinitely many pairs? Well, if we only have finitely many pairs of socks, then AC is not needed -- we can choose one member of each pair using the definition of "nonempty," and we can repeat an operation finitely many times using the rules of formal logic (not discussed here).

Jerry Bona once said,

The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?
This is a joke. In the setting of ordinary set theory, all three of those principles are mathematically equivalent -- i.e., if we assume any one of those principles, we can use it to prove the other two. However, human intuition does not always follow what is mathematically correct. The Axiom of Choice agrees with the intuition of most mathematicians; the Well Ordering Principle is contrary to the intuition of most mathematicians; and Zorn's Lemma is so complicated that most mathematicians are not able to form any intuitive opinion about it.

For another indication of the controversy that initially surrounded the Axiom of Choice, consider this anecdote (recounted by Jan Mycielski in Notices of the AMS vol. 53 no. 2 page 209). Tarski, one of the early great researchers in set theory and logic, proved that AC is equivalent to the statement that any infinite set X has the same cardinality as the Cartesian product X x X. He submitted his article to Comptes Rendus Acad. Sci. Paris, where it was refereed by two very famous mathematicians, Fréchet and Lebesgue. Both wrote letters rejecting the article. Fréchet wrote that an implication between two well known truths is not a new result. And Lebesgue wrote that an implication between two false statements is of no interest. Tarski said that he never again submitted a paper to the Comptes Rendus.

AC permits arbitrary choices from an arbitrary collection of nonempty sets. Some mathematicians have investigated some weakened forms of AC, such as

The full strength of the Axiom of Choice does not seem to be needed for applied mathematics. Some weaker principle such as CC or DC generally would suffice. To see this, consider that any application is based on measurements, but humans can only make finitely many measurements. We can extrapolate and take limits, but usually those limits are sequential, so even in theory we cannot make use of more than countably many measurements. The resulting spaces are separable. Even if we use a nonseparable space such as L∞, this may be merely to simplify our notation; the relevant action may all be happening in some separable subspace, which we could identify with just a bit more effort. (Thus, in some sense, nonseparable spaces exist only in the imagination of mathematicians.) If we restrict our attention to separable spaces, then much of conventional analysis still works with AC replaced by CC or DC. However, the resulting exposition is then more complicated, and so this route is only followed by a few mathematicians who have strong philosophical leanings against AC.

A few pure mathematicians and many applied mathematicians (including, e.g., some mathematical physicists) are uncomfortable with the Axiom of Choice. Although AC simplifies some parts of mathematics, it also yields some results that are unrelated to, or perhaps even contrary to, everyday "ordinary" experience; it implies the existence of some rather bizarre, counterintuitive objects. Perhaps the most bizarre is the Banach-Tarski Paradox: It is possible to take the 3-dimensional closed unit ball,

B   =   {(x,y,z) ∈ R3 : x2 + y2 + z2 < 1}
and partition it into finitely many pieces, and move those pieces in rigid motions (i.e., rotations and translations, with pieces permitted to move through one another) and reassemble them to form two copies of B.

At first glance, the Banach-Tarski result seems to contradict some of our intuition about physics -- e.g., the Law of Conservation of Mass, from classical Newtonian physics. If we assume that the ball has a uniform density, then the Banach-Tarski Paradox seems to say that we can disassemble a one-kilogram ball into pieces and rearrange them to get two one-kilogram balls. But actually, the contradiction can be explained away: Only a set with a defined volume can have a defined mass. A "volume" can be defined for many subsets of R3 --- spheres, cubes, cones, icosahedrons, etc. --- and in fact a "volume" can be defined for nearly any subset of R3 that we can think of. This leads beginners to expect that the notion of "volume" is applicable to every subset of R3. But it's not. In particular, the pieces in the Banach-Tarski decomposition are sets whose volumes cannot be defined.

More precisely, Lebesgue measure is defined on some subsets of R3, but it cannot be extended to all subsets of R3 in a fashion that preserves two of its most important properties: the measure of the union of two disjoint sets is the sum of their measures, and measure is unchanged under translation and rotation. The pieces in the Banach-Tarski decomposition are not Lebesgue measurable. Thus, the Banach-Tarski Paradox gives as a corollary the fact that there exist sets that are not Lebesgue measurable. That corollary also has a much shorter proof (not involving the Banach-Tarski Paradox) which can be found in every introductory textbook on measure theory, but it too uses the Axiom of Choice.

Here is a brief sketch of that shorter proof: Work in "the real numbers modulo 1" -- that is, the number system that you get if you cut the interval [0,1) out of the real line and loop it around into a circle, so that 0 and 1 are the same number. (Like the way that 0 and 12 are the same on a circular clock.) In that number system, multiplication and division don't really work very well any more, but addition and subtraction still work fine, and so does Lebesgue measure. Let's call that number system T; its entire measure is 1. Now, the Axiom of Choice is used to "construct" a rather peculiar subset of T -- let us call it C -- with the property that the sets C+r = {x+r : x in C} are all disjoint from each other, for different values of the rational number r. The union of these sets is all of T. Now, if C were measurable, then so would each C+r, and they would all have the same measure, and their measures would add up to the measure of T -- that is, they would add up to 1. But how many of these C+r are there? There are a countable infinity of them. If the measure of C were zero, their sum would be zero. If the measure of C were positive, their sum would be infinite. You can't get 1, either way.

Personally, I am not surprised to find the Axiom of Choice coming into play in a subject that is so inherently complicated as unmeasurable sets. I am much more surprised to find AC coming into play in this simpler and more concrete example: I want to classify all subsets of {1, 2, 3, 4, 5, . . .} as "small" or not "small," defining the word "small" in such a way that

  1. any set with zero or one members is "small";
  2. any union of two "small" sets is "small"; and
  3. a set is"small" if and only if its complement isn't "small."
Now, without much difficulty I can give examples satisfying any two of those three rules: Does there exist a classification scheme satisfying all three rules? It turns out that such a classification scheme exists, but an example of such a classification scheme does not exist (which makes it a bit hard to visualize!). And by that I do not mean just that we haven't found an example yet. I mean that the proofs of existence are inherently nonconstructive -- i.e., they cannot be replaced by constructive proofs -- so no examples can ever be given. But the proof of that fact is very deep, and it raises interesting philosophical questions: In what sense does that classification scheme "exist"? (My own attitude is that I'm not really working with the classification schemes themselves; I'm just working with sentences about hypothetical classification schemes.)
Technical details for experts: To prove the existence of such a classification scheme, just call "large" the members of some nonprincipal ultrafilter on the positive integers, and call their complements "small." Note that, with this scheme, any superset of a "large" set is also "large." The converse is slightly more complicated: If you have a "small/large" classification, the "large" sets do not necessarily necessarily form a nonprincipal ultrafilter, but the supersets of "large" sets do. An introduction to nonprincipal ultrafilters can be found in my book and in many other places in the literature.
     The existence of nonprincipal ultrafilters follows easily from Zorn's Lemma, by arguments that will be obvious once you've digested all definitions involved (admittedly not a small task). But showing that the existence proof is inherently nonconstructive is much harder, and requires some definitions that I've made up. By an "example" I mean anything whose existence can be proved using just ZF+DC --- that is, I'll allow Dependent Choice but no higher relatives of AC.
     Let BP be the statement that "every subset of the reals has the Baire property." The existence of a nonpricipal ultrafilter on the integers implies not-BP (by fairly straightforward functional analysis and topology). But in 1984 Shelah proved that the consistency of ZF implies the consistency of ZF+DC+BP. Therefore, if ordinary set theory is free of contradictions, then ZF+DC cannot be used to prove not-BP. I say "if" because we don't know that for sure, and Gödel's Incompleteness Theorem assures us that we never will know the consistency of ZF for sure. However, I would say that ZF is empirically consistent: In a century of study, mathematicians have not yet found any contradictions in ZF, despite the incentive that any mathematician finding such an important proof would instantly be promoted to full professor at any university in the world.
     My example with positive integers might appear to be simpler than the Banach-Tarski Paradox, but it does not really get us completely away from measure theory. A nonprincipal ultrafilter can be reformulated as a two-valued probability measure that is finitely additive but not countably additive.

In the preceding paragraphs I have attempted to introduce the Axiom of Choice in the language of informal set theory (also known as "naive set theory"), in which one assumes that sets are "collections of objects," with the meanings of the words "collection" and "object" based on our everyday nonmathematical experience. However, this web page is merely an introduction to the subject, and gives no indication of the proofs. A mathematically precise study of AC would require formal set theory (also known as "axiomatic set theory"); that is the language spoken by the real experts in this subject. In formal set theory, we put aside any nonmathematical, notions of "set". Instead of working with imagined sets, we work with sentences about some objects that we call "sets." We begin with a list of axioms, i.e., properties that these abstract objects are assumed to satisfy. Generally we assume axioms that seem intuitively reasonable, but we assume as few axioms as possible -- we try to choose axioms that enable us to prove the other properties that we want. We assume nothing else beyond what is contained in those axioms; we may not use a property of sets just because it is "familiar" or "obvious." Then we study the nature of the proofs, to determine what kinds of things can or cannot be proved. The axiomatic approach is much drier, and less appealing to all but a few specialists who are interested in it; but its conclusions are much more reliable than any mere, informal discussion. In this web page I have attempted to summarize, in informal language, some of the conclusions that are reached by that formal theory.

Links Collection for AC

Please write to me if you have suggestions for additions or alterations to this web page. However, I will warn you that I am NOT a leading authority on the Axiom of Choice; I am not knowledgeable about much of the advanced research on the subject. I have posted this web page chiefly because (i) I like the Axiom of Choice; (ii) I think I have a good understanding of the elementary aspects of the subject; and (iii) I like posting web pages.

Introductory / elementary

Especially noteworthy books and/or researchers

Slightly more advanced and specialized topics

Formal logic and / or automatic theorem-proving

Miscellaneous

All links tested 7 Nov 2005. Latest alterations 11 Nov 2009. My thanks to Andreas Blass, who assisted me with part of this page.