Inmathematics, theaxiom of choice, abbreviatedAC orAoC, is anaxiom ofset theory. Informally put, the axiom of choice says that given anycollection of non-empty sets, it is possible to construct a new set by choosing one element from each set, even if the collection isinfinite. Formally, it states that for everyindexed family ofnonempty sets, there exists an indexed set such that for every. The axiom of choice was formulated in 1904 byErnst Zermelo in order to formalize his proof of thewell-ordering theorem.[1]The axiom of choice is equivalent to the statement that everypartition has atransversal.[2]
In many cases, a set created by choosing elements can be made without invoking the axiom of choice, particularly if the number of sets from which to choose the elements is finite, or if a canonical rule on how to choose the elements is available — some distinguishing property that happens to hold for exactly one element in each set. An illustrative example is sets picked from the natural numbers. From such sets, one may always select the smallest number, e.g. given the sets {{4, 5, 6}, {10, 12}, {1, 400, 617, 8000}}, the set containing each smallest element is {4, 10, 1}. In this case, "select the smallest number" is achoice function. Even if infinitely many sets are collected from the natural numbers, it will always be possible to choose the smallest element from each set to produce a set. That is, the choice function provides the set of chosen elements. But no definite choice function is known for the collection of all non-empty subsets of the real numbers. In that case, the axiom of choice must be invoked.
Bertrand Russell coined an analogy: for any (even infinite) collection of pairs of shoes, one can pick out the left shoe from each pair to obtain an appropriate collection (i.e. set) of shoes; this makes it possible to define a choice function directly. For aninfinite collection of pairs of socks (assumed to have no distinguishing features such as being a left sock rather than a right sock), there is no obvious way to make a function that forms a set out of selecting one sock from each pair without invoking the axiom of choice.[3]
Although originally controversial, the axiom of choice is now used without reservation by most mathematicians,[4] and is included in the standard form ofaxiomatic set theory,Zermelo–Fraenkel set theory with the axiom of choice (ZFC). One motivation for this is that a number of generally accepted mathematical results, such asTychonoff'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 theaxiom of determinacy. While some varieties ofconstructive mathematics avoid the axiom of choice, others embrace it.
Achoice function (also called selector or selection) is a function, defined on a collection of nonempty sets, such that for every set in, is an element of. With this concept, the axiom can be stated:
Axiom—For any set of nonempty sets, there exists a choice function that is defined on and maps each set of to an element of that set.
Formally, this may be expressed as follows:
Thus, thenegation of the axiom may be expressed as the existence of a collection of nonempty sets which has no choice function. Formally, this may be derived making use of the logical equivalence of
Each choice function on a collection of nonempty sets is an element of theCartesian product of the sets in. This is not the most general situation of a Cartesian product of afamily of sets, where a given set can occur more than once as a factor; however, one can focus on elements of such a product that select the same element every time a given set appears as factor, and such elements correspond to an element of the Cartesian product of alldistinct sets in the family. The axiom of choice asserts the existence of such elements; it is therefore equivalent to the statement:
In this article and other discussions of the Axiom of Choice the following abbreviations are common:
There are many other equivalent statements of the axiom of choice. These are equivalent in the sense that, in the presence of other basic axioms of set theory, they imply the axiom of choice and are implied by it.
One variation avoids the use of choice functions by, in effect, replacing each choice function with its range:
This can be formalized in first-order logic as:
Note that is logically equivalent to.
In English, this first-order sentence reads:
This guarantees for anypartition of a set the existence of a subset of containing exactly one element from each part of the partition.
Another equivalent axiom only considers collections that are essentially powersets of other sets:
Authors who use this formulation often speak of thechoice function on, but this is a slightly different notion of choice function. Its domain is the power set of (with the empty set removed), and so makes sense for any set, whereas with the definition used elsewhere in this article, the domain of a choice function on acollection of sets is that collection, and so only makes sense for sets of sets. With this alternate notion of choice function, the axiom of choice can be compactly stated as
which is equivalent to
The negation of the axiom can thus be expressed as:
The usual statement of the axiom of choice does not specify whether the collection of nonempty sets is finite or infinite, and thus implies that everyfinite collection of nonempty sets has a choice function. However, that particular case is a theorem of the Zermelo–Fraenkel set theory without the axiom of choice (ZF); it is easily proved by theprinciple of finite induction.[8] In the even simpler case of a collection ofone set, a choice function just corresponds to an element, so this instance of the axiom of choice says that every nonempty set has an element; this holds trivially. The axiom of choice can be seen as asserting the generalization of this property, already evident for finite collections, to arbitrary collections.
Until the late 19th century, the axiom of choice was often used implicitly, although it had not yet been formally stated. For example, after having established that the setX contains only non-empty sets, a mathematician might have said "letF(s) be one of the members ofs for alls inX" to define a functionF. In general, it is impossible to prove thatF exists without the axiom of choice, but this seems to have gone unnoticed until Zermelo.
The nature of the individual nonempty sets in the collection may make it possible to avoid the axiom of choice even for certain infinite collections. For example, suppose that each member of the collectionX is a nonempty subset of the natural numbers. Every such subset 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 makes it unnecessary to add the axiom of choice to our axioms of set theory.
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 selection forms a legitimate set (as defined by the other ZF axioms of set theory)? For example, suppose thatX is the set of all non-empty subsets of thereal numbers. First we might try to proceed as ifX were finite. If we try to choose an element from each set, then, becauseX is infinite, our choice procedure will never come to an end, and consequently we shall never be able to produce a choice function for all ofX. Next we might try specifying the least element from each set. But some subsets of the real numbers do not have least elements. For example, the openinterval (0,1) does not have a least element: ifx is in (0,1), then so isx/2, andx/2 is always strictly smaller thanx. So this attempt also fails.
Additionally, consider for instance the unit circleS, and the action onS by a groupG consisting of all rational rotations, that is, rotations by angles which are rational multiples of π. HereG is countable whileS is uncountable. HenceS breaks up into uncountably many orbits under G. Using the axiom of choice, we could pick a single point from each orbit, obtaining an uncountable subsetX ofS with the property that all of its translates byG are disjoint from X. The set of those translates partitions the circle into a countable collection of pairwise disjoint sets, which are all pairwise congruent. SinceX is not measurable for any rotation-invariant countably additive finite measure onS, finding an algorithm to form a set from selecting a point in each orbit requires that one add the axiom of choice to our axioms of set theory. Seenon-measurable set for more details.
In classical arithmetic, the natural numbers arewell-ordered: for every nonempty subset of the natural numbers, there is a unique least element under the natural ordering. In this way, one may specify a set from any given subset. One 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-orderedif and only if the axiom of choice holds.
A proof requiring the axiom of choice may establish the existence of an object without explicitlydefining the object in the language of set theory. For example, while the axiom of choice implies that there is awell-ordering of the real numbers, there are models of set theory with the axiom of choice in which no individual well-ordering of the reals is definable. Similarly, although a subset of the real numbers that is notLebesgue measurable can be proved to exist using the axiom of choice, it isconsistent that no such set is definable.[9]
The axiom of choice asserts the existence of these intangibles (objects that are proved to exist, but which cannot be explicitly constructed), which may conflict with some philosophical principles.[10] Because there is nocanonical well-ordering of all sets, 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 incategory theory). This has been used as an argument against the use of the axiom of choice.
Another argument against the axiom of choice is that it implies the existence of objects that may seem counterintuitive.[11] One example is theBanach–Tarski paradox, which says that it is possible to decompose 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, arenon-measurable sets.
Despite these seemingly paradoxical results, most mathematicians accept the axiom of choice as a valid principle for proving new results in mathematics. But the debate is interesting enough that it is considered notable when a theorem in ZFC (ZF plus AC) islogically equivalent (with just the ZF axioms) to the axiom of choice, and mathematicians look for results that require the axiom of choice to be false, though this type of deduction is less common than the type that requires the axiom of choice to be true.
Theorems of ZF hold true in anymodel of that theory, regardless of the truth or falsity of the axiom of choice in that particular model. The implications of choice below, including weaker versions of the axiom itself, are listed because they are not theorems of ZF. The Banach–Tarski paradox, for example, 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. Such statements can be rephrased as conditional statements—for example, "If AC holds, then 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.
As discussed above, in the classical theory of ZFC, the axiom of choice enablesnonconstructive proofs in which the existence of a type of object is proved without an explicit instance being constructed. In fact, in set theory andtopos theory,Diaconescu's theorem shows that the axiom of choice implies thelaw of excluded middle. The principle is thus not available inconstructive set theory, where non-classical logic is employed.
The situation is different when the principle is formulated inMartin-Löf type theory. There and higher-orderHeyting arithmetic, the appropriate statement of the axiom of choice is (depending on approach) included as an axiom or provable as a theorem.[12] A cause for this difference is that the axiom of choice in type theory does not have theextensionality properties that the axiom of choice in constructive set theory does.[13] The type theoretical context is discussed further below.
Different choice principles have been thoroughly studied in the constructive contexts and the principles' status varies between different school and varieties of the constructive mathematics.Some results in constructive set theory use theaxiom of countable choice or theaxiom of dependent choice, which do not imply the law of the excluded middle.Errett Bishop, who is notable for developing a framework forconstructive analysis, argued that an axiom of choice was constructively acceptable, saying
A choice function exists in constructive mathematics, because a choice is implied by the very meaning of existence.[14]
Although the axiom of countable choice in particular is commonly used in constructive mathematics, its use has also been questioned.[15]
It has been known since as early as 1922 that the axiom of choice may fail in a variant of ZF withurelements, through the technique ofpermutation models introduced byAbraham Fraenkel[16] and developed further byAndrzej Mostowski.[17] The basic technique can be illustrated as follows: Letxn andyn be distinct urelements forn=1, 2, 3..., and build a model where each set is symmetric under the interchangexn ↔yn for all but a finite number ofn. Then the setX = {{x1,y1}, {x2,y2}, {x3,y3}, ...} can be in the model but sets such as{x1,x2,x3, ...} cannot, and thusX cannot have a choice function.
In 1938,[18]Kurt Gödel showed that thenegation of the axiom of choice is not a theorem of ZF by constructing aninner model (theconstructible universe) that satisfies ZFC, thus showing that ZFC is consistent if ZF itself is consistent. In 1963,Paul Cohen employed the technique offorcing, developed for this purpose, to show that, assuming ZF is consistent, the axiom of choice itself is not a theorem of ZF. He did this by constructing a much more complex model that satisfies ZF¬C (ZF with the negation of AC added as axiom) and thus showing that ZF¬C is consistent. Cohen's model is asymmetric model, which is similar to permutation models, but uses "generic" subsets of the natural numbers (justified by forcing) in place of urelements.[19]
Together these results establish that the axiom of choice islogically independent of ZF. The assumption that ZF is consistent is harmless because adding another axiom to an already inconsistent system cannot make the situation worse. Because of independence, the decision whether to use the axiom of choice (or its negation) in a proof cannot be made by appeal to other axioms of set theory. It must be made on other grounds.
One argument in favor of using the axiom of choice is that it is convenient because it allows one to prove some simplifying propositions that otherwise could not be proved. Many theorems provable using choice are of an elegant general character: the cardinalities of any two sets are comparable, every nontrivialring with unity has amaximal ideal, everyvector space has abasis, everyconnected graph has aspanning tree, and everyproduct ofcompact spaces is compact, among many others. Frequently, the axiom of choice allows generalizing a theorem to "larger" objects. For example, it is provable without the axiom of choice that every vector space of finite dimension has a basis, but the generalization to all vector spaces requires the axiom of choice. Likewise, a finite product of compact spaces can be proven to be compact without the axiom of choice, but the generalization to infinite products (Tychonoff's theorem) requires the axiom of choice.
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 ofPeano arithmetic, are provable in ZF if and only if they are provable in ZFC.[20] Statements in this class include the statement thatP = NP, theRiemann hypothesis, and many other unsolved mathematical problems. When attempting 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 that is independent of ZF. For example, thegeneralized continuum hypothesis (GCH) is not only independent of ZF, but also independent of ZFC. However, ZF plus GCH implies AC, making GCH a strictly stronger claim than AC, even though they are both independent of ZF.
Theaxiom of constructibility and thegeneralized continuum hypothesis each imply the axiom of choice and so are strictly stronger than it. In class theories such asVon Neumann–Bernays–Gödel set theory andMorse–Kelley set theory, there is an axiom called theaxiom of global choice that is stronger than the axiom of choice for sets because it also applies to proper classes. The axiom of global choice follows from theaxiom of limitation of size. Tarski's axiom, which is used inTarski–Grothendieck set theory and states (in the vernacular) that every set belongs tosomeGrothendieck universe, is stronger than the axiom of choice.
There are important statements that, assuming the axioms ofZF but neither AC nor ¬AC, are equivalent to the axiom of choice.[21] The most important among them areZorn's lemma and thewell-ordering theorem. In fact, Zermelo initially introduced the axiom of choice in order to formalize his proof of the well-ordering theorem.
Several results incategory theory invoke the axiom of choice for their proof. These results might be weaker than, equivalent to, or stronger than the axiom of choice, depending on the strength of the technical foundations. For example, if one defines categories in terms of sets, that is, as sets of objects and morphisms (usually called asmall category), then there is nocategory of all sets, and so it is difficult for a category-theoretic formulation to apply to all sets. On the other hand, other foundational descriptions of category theory are considerably stronger, and an identical category-theoretic statement of choice may be stronger than the standard formulation, à la class theory, mentioned above.
Examples of category-theoretic statements which require choice include:
There are several weaker statements that are not equivalent to the axiom of choice but are closely related. One example is theaxiom of dependent choice (DC). A still weaker example is theaxiom of countable choice (ACω or CC), which states that a choice function exists for any countable set of nonempty sets. These axioms are sufficient for many proofs in elementarymathematical analysis, and are consistent with some principles, such as the Lebesgue measurability of all sets of reals, that are disprovable from the full axiom of choice.
Given an ordinal parameter α ≥ ω+2 — for every setS with rank less than α,S is well-orderable. Given an ordinal parameter α ≥ 1 — for every setS withHartogs number less than ωα,S is well-orderable. As the ordinal parameter is increased, these approximate the full axiom of choice more and more closely.
Other choice axioms weaker than axiom of choice include theBoolean prime ideal theorem and theaxiom of uniformization. The former is equivalent in ZF toTarski's 1930ultrafilter lemma: everyfilter is a subset of someultrafilter.
One of the most interesting aspects of the axiom of choice is the large number of places in mathematics where it shows up. Here are some statements that require the axiom of choice in the sense that they are not provable from ZF but are provable from ZFC (ZF plus AC). Equivalently, these statements are true in all models of ZFC but false in some models of ZF.
There are several historically important set-theoretic statements implied by AC whose equivalence to AC is open. Zermelo cited the partition principle, which was formulated before AC itself, as a justification for believing AC. In 1906, Russell declared PP to be equivalent, but whether the partition principle implies AC is an old open problem in set theory,[35] and the equivalences of the other statements are similarly hard old open problems. In everyknown model of ZF where choice fails, these statements fail too, but it is unknown whether they can hold without choice.
If we abbreviate by BP the claim that every set of real numbers has theproperty of Baire, then BP is stronger than ¬AC, which asserts the nonexistence of any choice function on perhaps only a single set of nonempty sets. Strengthened negations may be compatible with weakened forms of AC. For example, ZF + DC[36] + BP is consistent, if ZF is.
It is also consistent with ZF + DC that every set of reals isLebesgue measurable, but this consistency result, due toRobert M. Solovay, cannot be proved in ZFC itself, but requires a mildlarge cardinal assumption (the existence of aninaccessible cardinal). The much strongeraxiom of determinacy, or AD, implies that every set of reals is Lebesgue measurable, has the property of Baire, and has theperfect 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 manyWoodin cardinals).
Quine's system of axiomatic set theory,New Foundations (NF), takes its name from the title ("New Foundations for Mathematical Logic") of the 1937 article that introduced it. In the NF axiomatic system, the axiom of choice can be disproved.[37]
There are models of Zermelo-Fraenkel set theory in which the axiom of choice is false. We shall abbreviate "Zermelo-Fraenkel set theory plus the negation of the axiom of choice" by ZF¬C. For certain models of ZF¬C, it is possible to validate the negation of some standard ZFC theorems. As any model of ZF¬C is also a model of ZF, it is the case that for each of the following statements, there exists a model of ZF in which that statement is true.
For proofs, seeJech (2008).
Additionally, by imposing definability conditions on sets (in the sense ofdescriptive set theory) one can often prove restricted versions of the axiom of choice from axioms incompatible with general choice. This appears, for example, in theMoschovakis coding lemma.
Intype theory, a different kind of statement is known as the axiom of choice. This form begins with two types, σ and τ, and a relationR between objects of type σ and objects of type τ. The axiom of choice states that if for eachx of type σ there exists ay of type τ such thatR(x,y), then there is a functionf from objects of type σ to objects of type τ such thatR(x,f(x)) holds for allx of type σ:
Unlike in set theory, the axiom of choice in type theory is typically stated as anaxiom scheme, in whichR varies over all formulas or over all formulas of a particular logical form.
Let us call Zermelo's 1908 formulation the combinatorial axiom of choice: CAC: Any collection of mutually disjoint nonempty sets has a transversal.
| Overview |  | |
|---|---|---|
| Axioms | ||
| Operations | ||
| ||
| Set types | ||
| Theories | ||
| ||
| Set theorists | ||
| General | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Theorems (list) and paradoxes | |||||||||
| Logics |
| ||||||||
| Set theory |
| ||||||||
| Formal systems (list), language and syntax |
| ||||||||
| Proof theory | |||||||||
| Model theory | |||||||||
| Computability theory | |||||||||
| Related | |||||||||
| International | |
|---|---|
| National | |
| Other | |
