Relevance of the Axiom of Choice

THE AXIOM OF CHOICE

There are many equivalent statements of the Axiom of Choice. The following version gave rise to its name:

For any set X there is a function f, with domain , so that f(x) is a member of x for every nonempty x in X.

Such an f is called a ``choice function" on X. [Note that means X with the empty set removed. Also note that in Zermelo-Fraenkel set theory all mathematical objects are sets so each member of X is itself a set.]

The Axiom of Choice (AC) is one of the most discussed axioms of mathematics, perhaps second only to Euclid's parallel postulate. The axioms of set theory provide a foundation for modern mathematics in the same way that Euclid's five postulates provided a foundation for Euclidean geometry, and the questions surrounding AC are the same as the questions that surrounded Euclid's Parallel Postulate:

1. Can it be derived from the other axioms?
2. Is it consistent with the other axioms?
3. Should we accept it as an axiom?

For many sets, including any finite set, the first six axioms of set theory (abbreviated ZF) are enough to guarantee the existence of a choice function but there do exist sets for which AC is required to show the existence of a choice function. The existence of such sets was proved in 1963 by Paul Cohen. This means that AC cannot be derived from the other six axioms; in other words ``AC is independent of ZF." This answers question [1] posed above.

The question of whether AC is consistent with the other axioms (question [2] above) was answered by Goedel in 1938. Goedel showed that if the other axioms are consistent then AC is consistent with them. This is a ``relative consistency" proof which is the best we can hope for because of Goedel's Second Incompleteness Theorem.

The third question, ``Should we accept it as an axiom?", moves us into the realm of philosophy. Today there are three major schools of thought concerning the use of AC:

1. Accept it as an axiom and use it without hesitation.
2. Accept it as an axiom but use it only when you cannot find a proof without it.
3. AC is unacceptable.

Most mathematicians today belong to school A. Mathematicians who are in school B are usually there because of a belief in Occam's Razor (use as few assumptions as possible when explaining something) or an interest in metamathematics. There are a growing number of people moving to school C, especially computer scientists who work on automated reasoning using constructive type theories.

Underlying the schools of thought about the use of AC are views about truth and the nature of mathematical objects. Three major views are platonism, constructivism, and formalism.

Platonism

A platonist believes that mathematical objects exist independent of the human mind, and a mathematical statement, such as AC, is objectively either true or false. A platonist accepts AC only if it is objectively true, and probably falls into school A or C depending on her belief. If she isn't sure about AC's truth then she may be in school B so that once she finds out the truth about AC she will know which theorems are true.

Constructivism

A constructivist believes that the only acceptable mathematical objects are ones that can be constructed by the human mind, and the only acceptable proofs are constructive proofs. Since AC gives no method for constructing a choice set constructivists belong to school C.

Formalism

A formalist believes that mathematics is strictly symbol manipulation and any consistent theory is reasonable to study. For a formalist the notion of truth is confined to the context of mathematical models, e.g., a formalist would say "The parallel postulate is false in Riemannian geometry." but she wouldn't say "The parallel postulate is false." A formalist will probably not allign herself with any school. She will comfortably switch between A, B, and C depending on her current interests.

So: Should you accept the Axiom of Choice? Here are some arguments for and against it.

Against

• It's not as simple, aesthetically pleasing, and intuitive as the other axioms.
• It is equivalent to many statements which are not intuitive such as "Every set can be well ordered." How, for example, would you well order the reals?
• With it you can derive non-intuitive results, such as the existence of a discontinuous additive function, the existence of a non-measurable set of reals, and the Banach-Tarski Paradox (see the next section of the sci.math FAQ).
• It is nonconstructive - it conjures up a set without providing any sort of procedure for its construction.

For

The acceptance of AC is based on the belief that our intuition about finite sets can be extended to infinite sets. The main argument for accepting it is that it is useful. Many important, intuitively plausible theorems are equivalent to it or depend on it. For example these statements are equivalent to AC:

• Every vector space has a basis.
• Trichotomy of Cardinals: For any cardinals k and l, either k<l or k=l or k>l.
• Tychonoff's Theorem: The product of compact spaces is compact in the product topology.
• Zorn's Lemma: Every nonempty partially ordered set P in which each chain has an upper bound in P has a maximal element.

And these statements depend on AC (i.e., they cannot be proved in ZF without AC):

• The union of countably many countable sets is countable.
• Every infinite set has a denumerable subset.
• The Loewenheim-Skolem Theorem: Any first-order theory which has a model has a denumerable model.
• The Baire Category Theorem: The reals are not the union of countably many nowhere dense sets (i.e., the reals are not meager).
• The Ultrafilter Theorem: Every Boolean algebra has an ultrafilter on it.

Alternatives to AC

• Accept only a weak form of AC such as the Denumerable Axiom of Choice (every denumerable set has a choice function) or the Axiom of Dependent Choice.
• Accept an axiom that implies AC such as the Axiom of Constructibility (V=L) or the Generalized Continuum Hypothesis (GCH).
• Adopt AC as a logical axiom (Hilbert suggested this with his epsilon axiom). If set theory is done in such a logical formal system the Axiom of Choice will be a theorem.
• Accept a contradictory axiom such as the Axiom of Determinacy.
• Use a completely different framework for mathematics such as Category Theory. Note that within the framework of Category Theory Tychonoff's Theorem can be proved without AC (Johnstone, 1981).

Test Yourself: When is AC necessary?

If you are working in Zermelo-Fraenkel set theory without the Axiom of Choice, can you choose an element from...

1. a finite set?
2. an infinite set?
3. each member of an infinite set of singletons (i.e., one-element sets)?
4. each member of an infinite set of pairs of shoes?
5. each member of inifinite set of pairs of socks?
6. each member of a finite set of sets if each of the members is infinite?
7. each member of an infinite set of sets if each of the members is infinite?
8. each member of a denumerable set of sets if each of the members is infinite?
9. each member of an infinite set of sets of rationals?
10. each member of a denumerable set of sets if each of the members is denumberable?
11. each member of an infinite set of sets if each of the members is finite?
12. each member of an infinite set of finite sets of reals?
13. each member of an infinite set of sets of reals?
14. each member of an infinite set of two-element sets whose members are sets of reals?

The answers to these questions with explanations are accessible through http://www.jazzie.com/ii/math/index.html

References

Benacerraf, Paul and Putnam, Hilary. "Philosophy of Mathematics: Selected Readings, 2nd edition." Cambridge University Press, 1983.

Dauben, Joseph Warren. "Georg Cantor: His Mathematics and Philosophy of the Infinite." Princeton University Press, 1979.

A. Fraenkel, Y. Bar-Hillel, and A. Levy with van Dalen, Dirk. "Foundations of Set Theory, Second Revised Edition." North-Holland, 1973.

Johnstone, Peter T. "Tychonoff's Theorem without the Axiom of Choice." Fundamenta Mathematica 113: 21-35, 1981.

Leisenring, Albert C. "Mathematical Logic and Hilbert's Epsilon-Symbol." Gordon and Breach, 1969.

Maddy, "Believing the Axioms, I", J. Symb. Logic, v. 53, no. 2, June 1988, pp. 490-500, and "Believing the Axioms II" in v.53, no. 3.

Moore, Gregory H. "Zermelo's Axiom of Choice: Its Origins, Development, and Influence." Springer-Verlag, 1982.

Rubin, Herman and Rubin, Jean E. "Equivalents of the Axiom of Choice II." North-Holland, 1985.

This section of the FAQ is Copyright (c) 1994 Nancy McGough. Send comments and or corrections relating to this part to nancym@ii.com. The most up to date version of this section of the sci.math FAQ is accesible through http://www.jazzie.com/ii/math/index.html