Axiom of choice

Illustration of the axiom of choice

In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory equivalent to the statement that a Cartesian product of a collection of non-empty sets is non-empty. Informally put, the axiom of choice says that given any collection of sets, each containing at least one element, it is possible to construct a new set by choosing one element from each set, even if the collection is infinite. Formally, it states that for every indexed family $(S_{i})_{i\in I}$ of nonempty sets, there exists an indexed set $(x_{i})_{i\in I}$ such that $x_{i}\in S_{i}$ for every $i\in I$. The axiom of choice was formulated in 1904 by Ernst Zermelo in order to formalize his proof of the well-ordering theorem.

Quotes

• The axiom of choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?

  Krantz, Steven G. (2002), "The axiom of choice", Handbook of Logic and Proof Techniques for Computer Science, Springer, pp. 121–126, doi:10.1007/978-1-4612-0115-1_9, ISBN 978-1-4612-6619-8 .

• The Axiom of Choice is necessary to select a set from an infinite number of pairs of socks, but not an infinite number of pairs of shoes [...] Among boots we can distinguish right and left, and therefore we can make a selection of one out of each pair, namely, we can choose all the right boots or all the left boots; but with socks no such principle of selection suggests itself, and we cannot be sure, unless we assume the multiplicative axiom, that there is any class consisting of one sock out of each pair. [...] There is no difficulty in doing this with the boots. The pairs are given as forming an ℵ₀, and therefore as the field of a progression. Within each pair, take the left boot first and the right second, keeping the order of the pair unchanged; in this way we obtain a progression of all the boots. But with the socks we shall have to choose arbitrarily, with each pair, which to put first; and an infinite number of arbitrary choices is an impossibility. Unless we can find a rule for selecting, i.e. a relation which is a selector, we do not know that a selection is even theoretically possible.

  Russell, Bertrand (1993). Introduction to mathematical philosophy. New York: Dover Publications. ISBN 978-0-486-27724-0. 

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

  A. K. Dewdney from the famous April Fools' Day article in the computer recreations column of the Scientific American, April 1989.