In mathematics, the axiom of choice is an axiom of set theory. It was formulated about a century ago by Ernst Zermelo and has remained controversial to this day. It states the following:

Let X be a collection of non-empty sets. Then we can choose a member from each set in that collection.

Stated more formally:

There exists a function f defined on X such that for each set S in X, f(S) is an element of S.

Another formulation of the axiom of choice (AC) states:

Given any set of mutually exclusive non-empty sets, there exists at least one set that contains exactly one element in common with each of the non-empty sets.

Until the late 19th century, the axiom of choice was often used implicitly. For example, a proof might have, after establishing that the set S contains only non-empty sets, said "let F(X) be one of the members of X for all X in S." Here, the existence of the function F depends on the axiom of choice.

The principle seems obvious: if there are several boxes, each containing at least one item, the axiom simply states that one can choose exactly one item from each box. Although the statement sounds straightforward, the main issue is that the axiom of choice is unnecessary when one can come up with a rule to choose items from the sets, but it becomes necessary when such a rule can either not be found or when such a rule can be proved not to exist. Thus the controversy involves what it means to choose something from these sets, and what it means for a set to exist.

To see the issue, let us look at some sample sets.

1. Let X be any finite collection of non-empty sets.

Then f can be stated explicitly (out of set A choose a, ...), since the number of sets is finite.

Here the axiom of choice is not needed; the existence of the choice set follows from the other axioms of set theory.

2. Let X be the collection of all non-empty subsets of the natural numbers {0, 1, 2, 3, ... }.

Then f can be the function that chooses the smallest element in each set.

Again the axiom of choice is not needed, since we have a rule for doing the choosing.

3. Let X be the set of all sub-intervals of (0,1) with a length greater than 0.

Then f can be the function that chooses the midpoint of each interval.

Again the axiom of choice is not needed.

4. Let X be the collection of all non-empty subsets of the reals.

Now the existence of f is not so straightforward. There is no obvious definition of f that will guarantee success, and there are reasons to believe that such an f may not be definable. We cannot simply have f pick the smallest element as we did in example 2 because a set of real numbers need not have a smallest element; there is not, for example, a smallest rational number or a smallest positive real number. Perhaps under some ordering of the reals other than the usual one there would always be a smallest element. However, the other axioms of ZF set theory do not guarantee the existence of a well-ordering of the real numbers (or of any other uncountable set). In fact the statement that every set can be well-ordered is equivalent to the axiom of choice.

The axiom of choice asserts that there is some function f that will choose an element out of each set in the collection. It gives no indication of how the function would be defined, it simply mandates its existence. What is more, the axiom of choice asserts that a set exists even if it cannot be defined.

Theorems whose proofs involve the axiom of choice are always nonconstructive: they demonstrate the existence of something without telling us how to get it.

The axiom of choice has been proven to be logically independent of the remaining axioms of set theory; that is, it can be neither proven nor disproven from them (unless those remaining axioms contain an unknown contradiction). This is the result of work by Kurt Gödel and Paul Cohen. Thus no contradictions arise if the axiom of choice is rejected. However, most mathematicians accept either it, or a weakened variant of it, because it makes their jobs easier. Despite this, there is some study of systems in which the axiom of choice is either not true or at least not assumed (see also axiom of regularity). It is important to be aware of which proofs in mathematics use the axiom of choice and which do not. Furthermore, by contrast, there is a school of mathematical philosophy known as constructivism which asserts that proofs that assert the existence of something without defining how to get it are invalid, and this school rejects the axiom of choice.

The truth or falsity of the axiom of choice does not appear to be relevant to the physical world. The reason appears to be that all known sets corresponding to physical objects appear to be finite or at most countable, and with this limitation a choice function can always be defined, using the principle of induction, rendering the axiom of choice superfluous. Or, one could argue that all physically measurable quantities behave well under approximation and hence countable sets are adequate for mathematical modelling in the real world.

One reason that some mathematicians dislike the axiom of choice is that it implies the existence of some bizarre counter-intuitive objects. An example of this is the Banach-Tarski paradox which says in effect that it is possible to "carve up" the 3-dimensional solid unit ball into finitely many pieces and, using only rotation and translation, reassemble the pieces into two balls each with the same volume as the original. Note that the proof, like all proofs involving the axiom of choice, is an existence proof only: it does not tell us how to carve up the unit sphere to make this happen, it simply tells us that it can be done.

One of the most interesting aspects of the axiom of choice is the large number of places in mathematics that it shows up. There are also a remarkable number of important statements that are equivalent to the axiom of choice, most important among them Zorn's lemma and the well-ordering theorem: every set can be well-ordered. In fact, Zermelo initially introduced the axiom of choice in order to formalize his proof of the well-ordering principle.

Several central theorems in different branches of mathematics require the axiom of choice (or a weak version of it, such as the Boolean prime ideal theorem, the axiom of countable choice, or the axiom of dependent choice):

• Set theory
  • Any union of countably many countable sets is itself countable.
  • If the set A is infinite, then there exists an injection from the natural numbers N to A.
  • If the set A is infinite, then A and A×A have the same cardinality.
  • If two sets are given, then they either have the same cardinality, or one has a smaller cardinality than the other.

• Constructions of non-measurable sets (measure theory)
  • Vitali theorem
  • Hausdorff paradox
  • Banach-Tarski paradox
  • Sierpinski set

• Algebra
  • Every vector space has a basis.
  • Every ring contains a maximal ideal.
  • Every field has an algebraic closure.
  • Every field extension has a transcendence basis.
  • The Stone's representation theorem for Boolean algebras needs the Boolean prime ideal theorem.
• Functional analysis
  • The Hahn-Banach theorem in functional analysis, allowing the extension of linear functionals
  • The theorem that every Hilbert Space has an orthonormal basis.
  • The Banach-Alaoglu theorem about compactness of sets of functionals
  • The Baire category theorem about complete metric spaces, and its consequences, such as the open mapping theorem and the closed graph theorem.
• General topology
  • Tychonoff's theorem stating that every product of compact topological spaces is compact
  • In the product topology, the closure of a product of subsets is equal to the product of the closures.
  • Any product of complete uniform spaces is complete.
  • A uniform space is compact if and only if it is complete and totally bounded.
  • Every Tychonoff space has a Stone-Cech compactification.

Quotes

The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's Lemma?

— Jerry Bona

(The joke here is that, in truth, all three of these are mathematically equivalent, but the statement underscores the fact that most mathematicians find the axiom of choice to be intuitive, the well-ordering principle to be counterintuitive, and Zorn's lemma to be too complex to form any intuitive feeling about).

The Axiom of Choice is necessary to select a set from an infinite number of socks, but not an infinite number of shoes. Bertrand Russell

(The joke is that one can define a function to select from an infinite number of shoes by stating for example, to choose the left shoe. Without the axiom of choice, one may assert that such as function does not exist for socks, which are identical.)

The axiom gets its name not because mathematicians prefer it to other axioms.

— A. K. Dewdney

From the famous April Fool's Day article in the computer recreations column of the Scientific American, April 1989.

External links

• A leisurely introduction to the axiom, popular consequences, and further links are found at Eric Schechter's homepage (http://www.math.vanderbilt.edu/~schectex/ccc/choice.html).
• There are many people still doing work on the axiom of choice and its consequences. If you are interested in more, look up Paul Howard at EMU (http://www.emunix.emich.edu/~phoward/).