Added to Favorites

Popular Searches

Definitions

In mathematics, the axiom of choice, or AC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin, even if there are infinitely many bins and there is no "rule" for which object to pick from each. The axiom of choice is not required if the number of bins is finite or if such a selection "rule" is available.

The axiom of choice was formulated in 1904 by Ernst Zermelo. Although originally controversial, it is now used without reservation by most mathematicians. One motivation for this use is that a number of important mathematical results, such as Tychonoff's theorem, require the axiom of choice for their proofs. Contemporary set theorists also study axioms that are not compatible with the axiom of choice, such as the axiom of determinacy. Unlike the axiom of choice, these alternatives are not ordinarily proposed as axioms for mathematics, but only as principles in set theory with interesting consequences.

- For any set of non-empty sets, X, there exists a choice function f defined on X.

Each choice function on a collection X of nonempty sets can be viewed as (or identified with) an element of the Cartesian product of the sets in X. This leads to an equivalent statement of the axiom of choice:

- An arbitrary Cartesian product of non-empty sets is non-empty.

One variation avoids the use of choice functions by, in effect, replacing each choice function with its range.

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

Another equivalent axiom only considers collections X that are essentially powersets of other sets:

- For any set A, the power set of A (minus the empty set) has a choice function.

- Every set has a choice function.

- For any set A there is a function f such that for any non-empty subset B of A, f(B) lies in B.

- There is a set A such that for all functions f (on the set of non-empty subsets of A), there is a B such that f(B) does not lie in B.

Not every situation requires the axiom of choice. For finite sets X, the axiom of choice follows from the other axioms of set theory. In that case it is equivalent to saying that if we have several (a finite number of) boxes, each containing at least one item, then we can choose exactly one item from each box. Clearly we can do this: We start at the first box, choose an item; go to the second box, choose an item; and so on. The number of boxes is finite, so eventually our choice procedure comes to an end. The result is an explicit choice function: a function that takes the first box to the first element we chose, the second box to the second element we chose, and so on. (A formal proof for all finite sets would use the principle of mathematical induction.)

For certain infinite sets X, it is also possible to avoid the axiom of choice. For example, suppose that the elements of X are sets of natural numbers. Every nonempty set of natural numbers has a smallest element, so to specify our choice function we can simply say that it maps each set to the least element of that set. This gives us a definite choice of an element from each set and we can write down an explicit expression that tells us what value our choice function takes. Any time it is possible to specify such an explicit choice, the axiom of choice is unnecessary.

The difficulty appears when there is no natural choice of elements from each set. If we cannot make explicit choices, how do we know that our set exists? For example, suppose that X is the set of all non-empty subsets of the real numbers. First we might try to proceed as if X were finite. If we try to choose an element from each set, then, because X is infinite, our choice procedure will never come to an end, and consequently, we will never be able to produce a choice function for all of X. So that won't work. Next we might try the trick of specifying the least element from each set. But some subsets of the real numbers don't have least elements. For example, the open interval (0,1) does not have a least element: If x is in (0,1), then so is x/2, and x/2 is always strictly smaller than x. So taking least elements doesn't work, either.

The reason that we are able to choose least elements from subsets of the natural numbers is the fact that the natural numbers come pre-equipped with a well-ordering: Every subset of the natural numbers has a unique least element under the natural ordering. Perhaps if we were clever we might say, "Even though the usual ordering of the real numbers does not work, it may be possible to find a different ordering of the real numbers which is a well-ordering. Then our choice function can choose the least element of every set under our unusual ordering." The problem then becomes that of constructing a well-ordering, which turns out to require the axiom of choice for its existence; every set can be well-ordered if and only if the axiom of choice is true.

A proof requiring the axiom of choice is, in one meaning of the word, nonconstructive: even though the proof establishes the existence of an object, it may be impossible to define the object in the language of set theory. For example, while the axiom of choice implies that there is a well-ordering of the real numbers, there are models of set theory with the axiom of choice in which no well-ordering of the reals is definable. As another example, a subset of the real numbers that is not Lebesgue measurable can be proven to exist using the axiom of choice, but it is consistent that no such set is definable.

Some mathematicians dislike the axiom of choice because it produces these intangibles. Because there is no canonical well-ordering of any set, a construction that relies on a well-ordering may not produce a canonical result, even if a canonical result is desired (as is often the case in category theory). The small community of mathematical constructivists posit that all existence proofs should be totally explicit; it should be possible to construct, in an explicit and canonical manner, anything that is proven to exist. They reject the full axiom of choice because it asserts the existence of an object without uniquely determining its structure. In fact the Diaconescu–Goodman–Myhill theorem shows how to derive the constructively unacceptable law of the excluded middle, or a restricted form of it, in constructive set theory from the assumption of the axiom of choice.

Another argument against the axiom of choice is that it implies the existence of counterintuitive objects. One example of this is the Banach–Tarski paradox which says that it is possible to decompose ("carve up") the 3-dimensional solid unit ball into finitely many pieces and, using only rotations and translations, reassemble the pieces into two solid balls each with the same volume as the original. The pieces in this decomposition, constructed using the axiom of choice, are extremely complicated.

Despite these arguments, the majority of mathematicians accept the axiom of choice as a valid principle for proving new results in mathematics.

It is possible to prove many theorems using neither the axiom of choice nor its negation; this is common in constructive mathematics. Such statements will be true in any model of Zermelo–Fraenkel set theory (ZF), regardless of the truth or falsity of the axiom of choice in that particular model. The restriction to ZF renders any claim that relies on either the axiom of choice or its negation unprovable. For example, the Banach–Tarski paradox is neither provable nor disprovable from ZF alone: it is impossible to construct the required decomposition of the unit ball in ZF, but also impossible to prove there is no such decomposition. Similarly, all the statements listed below which require choice or some weaker version thereof for their proof are unprovable in ZF, but since each is provable in ZF plus the axiom of choice, there are models of ZF in which each statement is true. Statements such as the Banach–Tarski paradox can be rephrased as conditional statements, for example, "If AC holds, the decomposition in the Banach–Tarski paradox exists." Such conditional statements are provable in ZF when the original statements are provable from ZF and the axiom of choice.

By work of Kurt Gödel and Paul Cohen, the axiom of choice is logically independent of the other axioms of Zermelo–Fraenkel set theory (ZF). This means that neither it nor its negation can be proven to be true in ZF, if ZF is consistent. Consequently, if ZF is consistent, then ZFC is consistent and ZF¬C is also consistent. So the decision whether or not it is appropriate to make use of the axiom of choice in a proof cannot be made by appeal to other axioms of set theory. The decision must be made on other grounds.

One argument given in favor of using the axiom of choice is that it is convenient to use it: using it cannot hurt (cannot result in contradiction) and makes it possible to prove some propositions that otherwise could not be proved. Many theorems which are provable using choice are an elegant general character: every ideal in a ring is contained in a maximal ideal, every vector space has a basis, and every product of compact spaces is compact. Without the axiom of choice, these theorems may not hold for mathematical objects of large cardinality.

The proof of the independence result also shows that a wide class of mathematical statements, including all statements that can be phrased in the language of Peano arithmetic, are provable in ZF if and only if they are provable in ZFC. Statements in this class include the statement that P = NP, the Riemann hypothesis, and many other unsolved mathematical problems. When one attempts to solve problems in this class, it makes no difference whether ZF or ZFC is employed if the only question is the existence of a proof. It is possible, however, that there is a shorter proof of a theorem from ZFC than from ZF.

The axiom of choice is not the only significant statement which is independent of ZF. For example, the generalized continuum hypothesis (GCH) is not only independent of ZF, but also independent of ZF plus the axiom of choice (ZFC). However, ZF plus GCH implies AC, making GCH a strictly stronger claim than AC, even though they are both independent of ZF.

In class theories such as Von Neumann–Bernays–Gödel set theory and Morse–Kelley set theory, there is a possible axiom called the axiom of global choice which is stronger than the axiom of choice for sets because it also applies to proper classes. And the axiom of global choice follows from the axiom of limitation of size.

- Set theory
- Well-ordering theorem: Every set can be well-ordered. Consequently, every cardinal has an initial ordinal.
- If the set A is infinite, then A and A×A have the same cardinality.
- Trichotomy: If two sets are given, then either they have the same cardinality, or one has a smaller cardinality than the other.
- The Cartesian product of any nonempty family of nonempty sets is nonempty.
- König's theorem: Colloquially, the sum of a sequence of cardinals is strictly less than the product of a sequence of larger cardinals. (The reason for the term "colloquially", is that the sum or product of a "sequence" of cardinals cannot be defined without some aspect of the axiom of choice.)
- Every surjective function has a right inverse.
- Order theory
- Zorn's lemma: Every non-empty partially ordered set in which every chain (i.e. totally ordered subset) has an upper bound contains at least one maximal element.
- Hausdorff maximal principle: In any partially ordered set, every totally ordered subset is contained in a maximal totally ordered subset.
- Restricted Hausdorff maximal principle: In any partially ordered set there exists a maximal totally ordered subset.
- Algebra
- Every vector space has a basis.
- Every unital ring other than the trivial ring contains a maximal ideal.
- 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.

Examples of category-theoretic statements which require choice include:

- Every small category has a skeleton.
- If two small categories are weakly equivalent, then they are equivalent.
- Every continuous functor on a small-complete category which satisfies the appropriate solution set condition has a left-adjoint (the Freyd adjoint functor theorem).

Other choice axioms weaker than axiom of choice include the Boolean prime ideal theorem and the axiom of uniformization.

- 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 (see Dedekind infinite).
- Every infinite game $G\_S$ in which $S$ is a Borel subset of Baire space is determined.
- Measure theory
- The Vitali theorem on the existence of non-measurable sets which states that there is a subset of the real numbers that is not Lebesgue measurable.
- The Hausdorff paradox.
- The Banach–Tarski paradox.
- The Lebesgue measure of a countable disjoint union of measurable sets is equal to the sum of the measures of the individual sets.
- Algebra
- Every field has an algebraic closure.
- Every field extension has a transcendence basis.
- Stone's representation theorem for Boolean algebras needs the Boolean prime ideal theorem.
- The Nielsen-Schreier theorem, that every subgroup of a free group is free.
- The additive groups of R and C are isomorphic.
- 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.
- On every infinite-dimensional topological vector space there is a discontinuous linear map.
- General topology
- A uniform space is compact if and only if it is complete and totally bounded.
- Every Tychonoff space has a Stone–Čech compactification.

It is also consistent with ZF + DC that every set of reals is Lebesgue measurable; however, this consistency result, due to Robert M. Solovay, cannot be proved in ZFC itself, but requires a mild large cardinal assumption (the existence of an inaccessible cardinal). The much stronger axiom of determinacy, or AD, implies that every set of reals is Lebesgue measurable, has the property of Baire, and has the perfect set property (all three of these results are refuted by AC itself). ZF + DC + AD is consistent provided that a sufficiently strong large cardinal axiom is consistent (the existence of infinitely many Woodin cardinals).

- There exists a model of ZF¬C in which there is a function f from the real numbers to the real numbers such that f is not continuous at a, but for any sequence {x
_{n}} converging to a, lim_{n}f(x_{n})=f(a). - There exists a model of ZF¬C in which real numbers are a countable union of countable sets.
- There exists a model of ZF¬C in which there is a field with no algebraic closure.
- In all models of ZF¬C there is a vector space with no basis.
- There exists a model of ZF¬C in which there is a vector space with two bases of different cardinalities.

For proofs, see Thomas Jech, The Axiom of Choice, American Elsevier Pub. Co., New York, 1973.

- There exists a model of ZF¬C in which every set in R
^{n}is measurable. Thus it is possible to exclude counterintuitive results like the Banach–Tarski paradox which are provable in ZFC. Furthermore, this is possible whilst assuming the Axiom of dependent choice, which is weaker than AC but sufficient to develop most of real analysis. - In all models of ZF¬C, the generalized continuum hypothesis does not hold.

- This is a joke: although the three are all mathematically equivalent, 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 for any intuition.

"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 observation here is that one can define a function to select from an infinite number of pairs of shoes by stating for example, to choose the left shoe. Without the axiom of choice, one cannot assert that such a function exists for pairs of socks, because left and right socks are (presumably) indistinguishable from each other.

"The axiom gets its name not because mathematicians prefer it to other axioms." — A. K. Dewdney

- This quote comes from the famous April Fools' Day article in the computer recreations column of the Scientific American, April 1989.

- Herrlich, Horst, Axiom of Choice, Springer Lecture Notes in Mathematics 1876, Springer Verlag Berlin Heidelberg (2006). ISBN 3-540-30989-6.
- Paul Howard and Jean Rubin, "Consequences of the Axiom of Choice". Mathematical Surveys and Monographs 59; American Mathematical Society; 1998.
- Thomas Jech, "About the Axiom of Choice." Handbook of Mathematical Logic, John Barwise, ed., 1977.
- Gregory H Moore, "Zermelo's axiom of choice, Its origins, development and influence", Springer; 1982. ISBN 0-387-90670-3
- Ernst Zermelo, "Untersuchungen über die Grundlagen der Mengenlehre I," Mathematische Annalen 65: (1908) pp. 261-81. PDF download via digizeitschriften.de

- Translated in: Jean van Heijenoort, 2002. From Frege to Godel: A Source Book in Mathematical Logic, 1879-1931. New edition. Harvard Univ. Press. ISBN 0-674-32449-8

- *1904. "Proof that every set can be well-ordered," 139-41.

- *1908. "Investigations in the foundations of set theory I," 199-215.

- Axiom of Choice and Its Equivalents at ProvenMath includes formal statement of the Axiom of Choice, Hausdorff's Maximal Principle, Zorn's Lemma and formal proofs of their equivalence down to the finest detail.
- Consequences of the Axiom of Choice, based on the book by Paul Howard and Jean Rubin.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday October 05, 2008 at 03:12:59 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday October 05, 2008 at 03:12:59 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.