[picture of Bertrand Russell's shoes and socks]

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 may 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.

  1. If C is the collection of all nonempty subsets of {1,2,3,...}, then we can define f quite easily: just let f(S) be the smallest member of S.
  2. If C is the collection of all intervals of real numbers with positive, finite lengths, then we can define f(S) to be the midpoint of the interval S.
  3. If C is some more general collection of subsets of the real line, we may be able to define f by using a more complicated rule.
  4. However, if C is the collection of all nonempty subsets of the real line, it is not clear how to find a suitable function f. In fact, no one has ever found a suitable function f for this collection C, and there are convincing model-theortic arguments that no one ever will. (Of course, to prove this requires a precise definition of "find," etc.)
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 choice function f in proofs, as though it "exists" in some sense, even though 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.)

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 which universe we shall work in. Both possibilities are feasible -- i.e., neither accepting nor rejecting AC yields a contradiction; that follows from models devised by Gödel and Cohen. Some mathematicians have further investigated what happens when we reject AC but accept some weakened variant -- for example, CC (Countable Choice), which permits a sequence of arbitrary choices. 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.

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 Paradoxical Decomposition. Banach and Tarski used the Axiom of Choice to prove that 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 Decomposition seems to contradict some of our intuition about physics -- e.g., the Law of Conservation of Mass, from classical Newtonian physics. Consequently, the Decomposition is often called the Banach-Tarski Paradox. But actually, it only yields a complication, not a contradiction. If we assume a uniform density, only a set with a defined volume can have a defined mass. The notion of "volume" can be defined for many subsets of R3, and beginners might expect the notion to apply to all subsets of R3, but it does not. 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. Thus, the Banach-Tarski Paradox does not violate the Law of Conservation of Mass; it merely tells us that the notion of "volume" is more complicated than we might have expected.

By the way, the sets in the Banach-Tarski Decomposition cannot be described explicitly; we are merely able to prove their existence, like that of a choice function. One or more of the sets in the decomposition must be Lebesgue unmeasurable; thus a corollary of the Banach-Tarski Theorem is the fact that there exist sets that are not Lebesgue measurable. The existence of unmeasurable sets has a much shorter and easier proof, which can be found in every introductory textbook on measure theory. That proof also uses the Axiom of Choice, but doesn't mention the Banach-Tarski Decomposition.

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 a seemingly much simpler and more concrete setting: the integers. Let W be an infinite set (for instance, the integers). By a filter on the set W, we mean a method of classifying all subsets of W so that

It follows easily from these rules that a set and its complement cannot both be large. Thus, we do not get a filter on the integers by calling all infinite sets "large," since both the even integers and the odd integers are infinite sets. We do get an example of a filter by calling a set "large" if it is cofinite -- i.e., if its complement is finite. However, that example does not satisfy the next condition. An ultrafilter satisfies the preceding conditions plus this additional condition: For an example of an ultrafilter, pick some particular point w0 in W, and use this classification scheme: say that a set S is "large" if and only if w0 Î S. However, that example does not satisfy the next condition. A nonprincipal ultrafilter satisfies the preceding conditions plus this additional requirement: Now, the existence of such a classification scheme can be prove using the Axiom of Choice. (Sketch of proof: start from the filter of cofinite sets, and extend it to a maximal filter using Zorn's Lemma, also known as the Kuratowski-Zorn Theorem.) However, it turns out that we cannot actually find an explicit example of a nonprincipal ultrafilter. (This result may be simpler than the Banach-Tarski Paradox, but it does not really get us away from measure theory. A nonprincipal ultrafilter is essentially the same thing as a two-valued probability measure that is finitely additive but not countably additive.)

Bertrand Russell (more famous for his work in philosophy and political activism, but also an accomplished mathematician) once 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.

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 29 Nov 2001. Latest alterations 21 Mar 2003. My thanks to Andreas Blass, who assisted me with part of this page. This page has been selected by Open Here. Also, this page was chosen by KaBoL as the "cool math site of the week" for November 9, 1999 (Knot number 184).