Axiom of choice: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older edit
corrected &nsbp; to  
 
(3 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{about|the mathematical concept|the band named after it|Axiom of Choice (band)}}
Click here http://tinyurl.com/qd4atl3 and use coupon code LEINBO for 57% off on the [https://plus.google.com/113161777187625782423/posts/FxHchjUWyF8 Legal Insider Bot] Software
{{Use dmy dates|date=June 2013}}
[[File:Axiom of choice.svg|thumb|250px|(S<sub>''i''</sub>) is a [[indexed family|family]] of sets indexed over the [[real number]]s '''R'''; that is, there is a set S<sub>''i''</sub> for each real number ''i'', with a small sample shown above. Each set contains a nonzero, and possibly infinite, number of elements. The axiom of choice allows us to arbitrarily select a single element from each set, forming a corresponding family of elements (''x''<sub>''i''</sub>) also indexed over the real numbers, with ''x''<sub>''i''</sub> drawn from S<sub>''i''</sub>. In general the collections may be indexed over any set <span style="font-family:serif;">''I''</span>, not just '''R'''.]]
 
In [[mathematics]], the '''axiom of choice''', or '''AC''', is an [[axiom]] of [[set theory]] equivalent to the statement that "''the [[cartesian product#Infinite products|product]] of a collection of non-empty sets is non-empty''". It states that for every indexed [[Family of sets|family]] <math>(S_i)_{i \in I}</math> of [[nonempty]] sets there exists an indexed family <math>(x_i)_{i \in I}</math> of elements such that <math>x_i \in S_i</math> for every <math>i \in I</math>.  The axiom of choice was formulated in 1904 by [[Ernst Zermelo]] in order to formalize his proof of the [[well-ordering theorem]].<ref name="Zermelo, 1904">{{cite journal| first=Ernst| last=Zermelo| year=1904| url=http://gdz.sub.uni-goettingen.de/no_cache/en/dms/load/img/?IDDOC=28526 |format=reprint|title=Beweis, dass jede Menge wohlgeordnet werden kann| journal=Mathematische Annalen| volume=59| issue=4| pages=514–16|doi=10.1007/BF01445300}}</ref>
 
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. In many cases such a selection can be made without invoking the axiom of choice; this is in particular the case if the number of bins is finite, or if a selection rule is available: a distinguishing property that happens to hold for exactly one object in each bin. To give an informal example, for any (even infinite) collection of pairs of shoes, one can pick out the left shoe from each pair to obtain an appropriate selection, but for an infinite collection of pairs of socks (assumed to have no distinguishing features), such a selection can be obtained only by invoking the axiom of choice.
 
Although originally controversial, the axiom of choice is now used without reservation by most mathematicians,<ref>Jech, 1977, p. 348''ff''; Martin-Löf 2008, p. 210.</ref> and it is included in Zermelo–Fraenkel set theory with the axiom of choice ([[ZFC]]), the standard form of [[axiomatic set theory]]. One motivation for this use is that a number of generally accepted 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]]. The axiom of choice is avoided in some varieties of constructive mathematics, although there are varieties of constructive mathematics in which the axiom of choice is embraced.
 
==Statement==
A [[choice function]] is a function ''f'', defined on a collection ''X'' of nonempty sets, such that for every set ''s'' in ''X'', ''f''(''s'') is an element of ''s''.  With this concept, the axiom can be stated:
:For any set ''X'' of nonempty sets, there exists a choice function ''f'' defined on ''X''.
 
Formally, this may be expressed as follows:
 
:<math>\forall X \left[ \emptyset \notin X \implies \exists f \colon X \rarr \bigcup X \quad \forall A \in X \, ( f(A) \in A ) \right] \,.</math>
 
Thus the negation of the axiom of choice states that there exists a set of nonempty sets which has no choice function.
 
Each choice function on a collection ''X'' of nonempty sets is an element of the [[Cartesian product#Infinite products|Cartesian product]] of the sets in ''X''. This is not the most general situation of a Cartesian product of a [[indexed family|family]] of sets, where a same 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 all ''distinct'' sets in the family. The axiom of choice asserts the existence of such elements; it is therefore equivalent to:
 
:Given any family of nonempty sets, their Cartesian product is a nonempty set.
 
=== Nomenclature ZF, AC, and ZFC ===
In this article and other discussions of the '''Axiom of Choice''' the following abbreviations are common:
*AC &ndash; the Axiom of Choice.
*ZF &ndash; [[Zermelo–Fraenkel set theory]] omitting the Axiom of Choice.
*ZFC &ndash; [[Zermelo–Fraenkel set theory]], extended to include the Axiom of Choice.
 
===Variants===
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.
: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''.<ref>Herrlich, p. 9.</ref>
This guarantees for any [[partition of a set|partition]] of a set ''X'' the existence of a subset ''C'' of ''X'' containing exactly one element from each part of the partition.
 
Another equivalent axiom only considers collections ''X'' that are essentially powersets of other sets:
:For any set A, the [[power set]] of A (with the empty set removed) has a choice function.
Authors who use this formulation often speak of the ''choice function on A'', but be advised that this is a slightly different notion of choice function.  Its domain is the powerset of ''A'' (with the empty set removed), and so makes sense for any set ''A'', whereas with the definition used elsewhere in this article, the domain of a choice function on a ''collection 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
:Every set has a choice function.<ref>[[Patrick Suppes]], "Axiomatic Set Theory", Dover, 1972 (1960), ISBN 0-486-61630-4, p. 240</ref>
which is equivalent to
:For any  set A there is a function ''f'' such that for any non-empty subset B of ''A'', ''f''(''B'') lies in ''B''.
The negation of the axiom can thus be expressed as:
: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''.
 
=== Restriction to finite sets ===
The statement of the axiom of choice does not specify whether the collection of nonempty sets is finite or infinite, and thus implies that every [[finite set|finite collection]] of nonempty sets has a choice function. However, that particular case is a theorem of [[Zermelo–Fraenkel set theory]] without the axiom of choice (ZF); it is easily proved by [[mathematical induction]].<ref>Tourlakis (2003), pp. 209–210, 215–216.</ref> In the even simpler case of a collection of ''one'' 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.
 
==Usage==
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 set ''X'' contains only non-empty sets, a mathematician might have said "let ''F(s)'' be one of the members of ''s'' for all ''s'' in ''X''."  In general, it is impossible to prove that ''F'' exists without the axiom of choice, but this seems to have gone unnoticed until [[Zermelo]].
 
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]] to prove "for every natural number ''k'', every family of ''k'' nonempty sets has a choice function.") This method cannot, however, be used to show that every countable family of nonempty sets has a choice function, as is asserted by the [[axiom of countable choice]]. If the method is applied to an infinite sequence (''X''<sub>''i''</sub> : ''i''∈ω) of nonempty sets, a function is obtained at each finite stage, but there is no stage at which a choice function for the entire family is constructed, and no "limiting" choice function can be constructed, in general, in ZF without the axiom of choice.
 
==Examples==
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 collection ''X'' 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 apply the axiom of choice.
 
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 number]]s.  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''.  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 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 this attempt also fails.
 
Additionally, consider for instance the unit circle ''S'', and the action on ''S'' by a group ''G'' consisting of all rational rotations. Namely, these are rotations by angles which are rational multiples of&nbsp;''π''. Here ''G'' is countable while ''S'' is uncountable. Hence ''S'' breaks up into uncountably many orbits under&nbsp;''G''. Using the axiom of choice, we could pick a single point from each orbit, obtaining an uncountable subset ''X'' of ''S'' with the property that all of its translates by G are disjoint from&nbsp;''X''. The set of those translates partitions the circle into a countable collection of disjoint sets, which are all pairwise congruent. Since ''X'' is not measurable for any rotation-invariant countably additive finite measure on ''S'', finding an algorithm to select a point in each orbit requires the axiom of choice. See [[non-measurable set#Example|non-measurable set]] for more details.
 
The reason that we are able to choose least elements from subsets of the natural numbers is the fact that the natural numbers are [[well-order]]ed: every nonempty subset of the natural numbers has a unique least element under the natural ordering.  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-ordered if and only if the axiom of choice holds.
 
==Criticism and acceptance==
 
A proof requiring the axiom of choice may establish the existence of an object without explicitly [[definable set|defining]] 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. Similarly, although a subset of the real numbers that is not [[Lebesgue measure|Lebesgue measurable]] can be proven to exist using the axiom of choice, it is [[consistent]] that no such set is definable.
 
The axiom of choice produces these intangibles (objects that are proven to exist, but which cannot be explicitly constructed), which may conflict with some philosophical principles. Because there is no [[Canonical form|canonical]] 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 in [[category 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 counterintuitive objects. One example 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 [[non-measurable set]]s.
 
Despite these facts, most mathematicians accept the axiom of choice as a valid principle for proving new results in mathematics. The debate is interesting enough, however, that it is considered of note when a theorem in ZFC (ZF plus AC) is [[logical equivalence|logically 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 which requires the axiom of choice to be true.
 
It is possible to prove many theorems using neither the axiom of choice nor its negation; such statements will be true in any [[model theory|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, 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.
 
== In constructive mathematics ==
 
As discussed above, in ZFC, the axiom of choice is able to provide "[[nonconstructive proof]]s" in which the existence of an object is proved although no explicit example is constructed. ZFC, however, is still formalized in classical logic. The axiom of choice has also been thoroughly studied in the context of constructive mathematics, where non-classical logic is employed.  The status of the axiom of choice varies between different varieties of constructive mathematics.
 
In [[Martin-Löf type theory]] and higher-order [[Heyting arithmetic]], the appropriate statement of the axiom of choice is (depending on approach) included as an axiom or provable as a theorem.<ref>[[Per Martin-Löf]], ''[http://www.cs.cmu.edu/afs/cs/Web/People/crary/819-f09/Martin-Lof80.pdf Intuitionistic type theory]'', 1980.
[[Anne Sjerp Troelstra]], ''Metamathematical investigation of intuitionistic arithmetic and analysis'', Springer, 1973.</ref> [[Errett Bishop]] argued that the 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."<ref>[[Errett Bishop]] and [[Douglas S. Bridges]], ''Constructive analysis'', Springer-Verlag, 1985.</ref>
 
In [[constructive set theory]], however, [[Diaconescu's theorem]] shows that the axiom of choice implies the [[Law of excluded middle]] (unlike in Martin-Löf type theory, where it does not). Thus the axiom of choice is not generally available in constructive set theory. A cause for this difference is that the axiom of choice in type theory does not have the [[extensionality]] properties that the axiom of choice in constructive set theory does.<ref>[[Per Martin-Löf]], "100 Years of Zermelo’s Axiom of Choice: What was the Problem with It?", ''The Computer Journal'' (2006) 49 (3): 345-350. doi: 10.1093/comjnl/bxh162</ref>
 
Some results in constructive set theory use the [[axiom of countable choice]] or the [[axiom of dependent choice]], which do not imply the law of the excluded middle in constructive set theory. Although the axiom of countable choice in particular is commonly used in constructive mathematics, its use has also been questioned.<ref>Fred Richman, “Constructive mathematics without choice”, in: Reuniting the Antipodes—Constructive and Nonstandard Views of the Continuum (P. Schuster et al., eds), Synthèse Library 306, 199–205, Kluwer Academic Publishers, Amsterdam, 2001.</ref>
 
==Independence==
 
Assuming ZF is consistent, [[Kurt Gödel]] showed that the ''negation'' of the axiom of choice is not a theorem of ZF by constructing an [[inner model]] (the [[constructible universe]]) which satisfies ZFC and thus showing that ZFC is consistent. Assuming ZF is consistent, [[Paul Cohen (mathematician)|Paul Cohen]] employed the technique of [[forcing (mathematics)|forcing]], developed for this purpose, to show that the axiom of choice itself is not a theorem of ZF by constructing a much more complex model which satisfies ZF¬C (ZF with the negation of AC added as axiom) and thus showing that ZF¬C is consistent. Together these results establish that the axiom of choice is [[Independence (mathematical logic)|logically 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 of the axiom of choice (or its negation) 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 because it allows one to prove some simplifying propositions that otherwise could not be proved. Many theorems which are provable using choice are of an elegant general character: every [[Ideal_(ring_theory)|ideal]] in a ring is contained in a [[maximal ideal]], every [[vector space]] has a [[Basis_(linear_algebra)|basis]], and every [[Product topology|product]] of [[compact space]]s 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.<ref>This is because arithmetical statements are [[absoluteness (mathematical logic)|absolute]] to the [[constructible universe]] ''L''. [[Shoenfield's absoluteness theorem]] gives a more general result.</ref> 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 [[Continuum hypothesis#The generalized continuum hypothesis|generalized 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.
 
==Stronger axioms==
The [[axiom of constructibility]] implies the axiom of choice, and is strictly stronger than it. The [[Continuum hypothesis#The generalized continuum hypothesis|generalized continuum hypothesis]] implies the axiom of choice, and is strictly stronger than it.
 
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]].
 
==Equivalents==
There are important statements that, assuming the axioms of [[Zermelo–Fraenkel set theory|ZF]] but neither AC nor ¬AC, are equivalent to the axiom of choice.  The most important among them are [[Zorn's lemma]] and the [[well-ordering theorem]].  In fact, Zermelo initially introduced the axiom of choice in order to formalize his proof of the well-ordering theorem.
 
*[[Set theory]]
**[[Well-ordering theorem]]: Every set can be well-ordered. Consequently, every [[cardinal number|cardinal]] has an [[initial ordinal]].
**[[Tarski's theorem]]: For every infinite set ''A'', there is a [[bijective map]] between the sets  ''A'' and ''A''×''A''.
**[[Trichotomy (mathematics)|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#Infinite products|Cartesian product]] of any family of nonempty sets is nonempty.
**[[König's theorem (set theory)|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 [[Inverse function#Left and right inverses|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. The restricted principle "Every partially ordered set has a maximal totally ordered subset" is also equivalent to AC over ZF.
**[[Tukey's lemma]]: Every non-empty collection of [[finite character]] has a maximal element with respect to inclusion.
**[[Antichain]] principle: Every partially ordered set has a maximal [[antichain]].
 
*[[Abstract algebra]]
**Every [[vector space]] has a [[basis (linear algebra)|basis]].<ref>{{cite journal|last=Blass|first=Andreas|title=Existence of bases implies the axiom of choice|journal=Contemporary mathematics|year=1984|volume=31}}</ref>
**Every unital [[ring (mathematics)|ring]] other than the trivial ring contains a [[maximal ideal]].
**For every non-empty set ''S'' there is a [[binary operation]] defined on ''S'' that gives it a [[group structure and the axiom of choice|group structure]].<ref>[[András Hajnal|A. Hajnal]], A. Kertész: Some new algebraic equivalents of the axiom  of choice, ''Publ. Math. Debrecen'', '''19'''(1972),  339&ndash;340, see also H. Rubin, J. Rubin, ''Equivalents of the axiom of choice, II'', [[North-Holland Publishing Company|North-Holland]], 1985, p. 111.</ref> (A [[cancellation property|cancellative]] binary operation is enough.)
 
*[[Functional analysis]]
**The closed unit ball of the dual of a [[normed vector space]] over the reals has an [[extreme point]].
 
*[[Point-set topology]]
**[[Tychonoff's theorem]]: Every [[product topology|product]] of [[Compact space|compact]] [[topological space]]s is compact.
**In the product topology, the [[closure (topology)|closure]] of a product of subsets is equal to the product of the closures.
 
*[[Mathematical logic]]
**If ''S'' is a set of sentences of [[first-order logic]] and ''B'' is a consistent subset of ''S'', then ''B'' is included in a set that is maximal among consistent subsets of ''S''.  The special case where ''S'' is the set of '''all''' first-order sentences in a given [[signature (logic)|signature]] is weaker, equivalent to the [[Boolean prime ideal theorem]]; see the section "Weaker forms" below.
 
*[[Graph theory]]
**Every [[connected graph]] has a [[spanning tree]].<ref>{{citation|title=Trees|first=Jean-Pierre|last=Serre|authorlink=Jean-Pierre Serre|page=23|publisher=Springer|series=Springer Monographs in Mathematics|year=2003}}; {{citation
| last = Soukup | first = Lajos
| contribution = Infinite combinatorics: from finite to infinite
| doi = 10.1007/978-3-540-77200-2_10
| location = Berlin
| mr = 2432534
| pages = 189–213
| publisher = Springer
| series = Bolyai Soc. Math. Stud.
| title = Horizons of combinatorics
| volume = 17
| year = 2008}}. See in particular Theorem 2.1, [http://books.google.com/books?id=kIKW18ENfUMC&pg=PA192 pp.&nbsp;192–193].</ref>
 
=== Category theory ===
There are several results in [[category theory]] which 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 a [[small category]]), or even locally small categories, whose hom-objects are sets, then there is no [[category of sets|category 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:
*Every small [[category (mathematics)|category]] has a [[skeleton (category theory)|skeleton]].
*If two small categories are weakly equivalent, then they are [[equivalence of categories|equivalent]].
*Every continuous functor on a small-complete category which satisfies the appropriate solution set condition has a [[adjoint functors|left-adjoint]] (the Freyd adjoint functor theorem).
 
==Weaker forms==
There are several weaker statements that are not equivalent to the axiom of choice, but are closely related. One example is the [[axiom of dependent choice]] (DC). A still weaker example is the [[axiom of countable choice]] (AC<sub>ω</sub> or CC), which states that a choice function exists for any countable set of nonempty sets. These axioms are sufficient for many proofs in elementary [[mathematical 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.
 
Other choice axioms weaker than axiom of choice include the [[Boolean prime ideal theorem]] and the [[Uniformization (set theory)|axiom of uniformization]].  The former is equivalent in ZF to the existence of an [[ultrafilter]] containing each given filter, proved by Tarski in 1930.
 
===Results requiring AC (or weaker forms) but weaker than it===<!-- This section is linked from [[Basis (linear algebra)]] -->
One of the most interesting aspects of the axiom of choice is the large number of places in mathematics that 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.
 
*[[Set theory]]
**Any [[union (set theory)|union]] of countably many [[countable sets]] is itself countable.
**If the set ''A'' is [[infinite set|infinite]], then there exists an [[injective function|injection]] from the [[natural number]]s '''N''' to ''A'' (see [[Dedekind infinite]]).
**Every infinite [[determinacy#Basic notions|game]] <math>G_S</math> in which <math>S</math> is a [[Borel set|Borel]] subset of [[Baire space (set theory)|Baire space]] is [[determinacy#Basic notions|determined]].
 
*[[Measure theory]]
**The [[Vitali set|Vitali theorem]] on the existence of [[non-measurable set]]s 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 (mathematics)|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 '''[[real numbers|R]]''' and '''[[complex numbers|C]]''' are isomorphic.<ref>http://www.cs.nyu.edu/pipermail/fom/2006-February/009959.html</ref> and <ref>http://journals.cambridge.org/action/displayFulltext?type=1&fid=4931240&aid=4931232</ref>
 
*[[Functional analysis]]
**The [[Hahn–Banach theorem]] in [[functional analysis]], allowing the extension of [[linear map|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 space|complete]] [[metric space]]s, and its consequences, such as the [[open mapping theorem (functional analysis)|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]].
 
*[[Mathematical logic]]
**[[Gödel's completeness theorem]] for first-order logic: every consistent set of first-order sentences has a completion. That is, every consistent set of first-order sentences can be extended to a maximal consistent set.
 
==Stronger forms of the negation of AC==
Now, consider stronger forms of the negation of AC.  For example, if we abbreviate by BP the claim that every set of real numbers has the [[property 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.  Note that strengthened negations may be compatible with weakened forms of AC.  For example, ZF + DC<ref>[[Axiom of dependent choice]]</ref> + BP is consistent, if ZF is.
 
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 cardinal]]s).
 
==Statements consistent with the negation of AC==
There are models of Zermelo-Fraenkel set theory in which the axiom of choice is false.  We will 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 prove the negation of some standard facts.
Note that any model of ZF¬C is also a model of ZF, so for each of the following statements, there exists a model of ZF in which that statement is true.
 
*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 ''f'' is [[Sequential continuity|sequentially continuous]] at ''a'', i.e., for any sequence {''x<sub>n</sub>''} converging to ''a'', lim<sub>''n''</sub> f(''x<sub>n</sub>'')=f(a).
*There exists a model of ZF¬C which has an infinite set of real numbers without a countably infinite subset.
*There exists a model of ZF¬C in which real numbers are a countable union of countable sets.<ref>Jech, Thomas (1973) "The axiom of choice", ISBN 0-444-10484-4, CH. 10, p. 142.</ref>
*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.
*There exists a model of ZF¬C in which there is a free [[complete boolean algebra]] on countably many generators.<ref name="Stavi, 1974">{{cite journal| first= Jonathan | last=Stavi| year=1974| url=http://www.springerlink.com/content/d5710380t753621u/ |format=reprint|title=A model of ZF with an infinite free complete Boolean algebra| journal=Israel Journal of Mathematics| volume=20| issue= 2| pages=149–163|doi=10.1007/BF02757883}}</ref>
 
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<sup>''n''</sup> 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.
 
==Quotes==
"The Axiom of Choice is obviously true, the [[Well-ordering theorem|well-ordering principle]] obviously false, and who can tell about [[Zorn's lemma]]?" —&nbsp;[[Jerry Bona]]
:This is a joke: although the three are all mathematically equivalent, many 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." —&nbsp;[[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.
 
"Tarski tried to publish his theorem [the equivalence between AC and 'every infinite set ''A'' has the same cardinality as ''A''x''A''', see above] in [[Comptes rendus de l'Académie des sciences|Comptes Rendus]], but [[Maurice René Fréchet|Fréchet]] and [[Henri Lebesgue|Lebesgue]] refused to present it. Fréchet wrote that an implication between two well known [true] propositions is not a new result, and Lebesgue wrote that an implication between two false propositions is of no interest".
:Polish-American mathematician [[Jan Mycielski]] relates this anecdote in a 2006 article in the Notices of the AMS.
 
"The axiom gets its name not because mathematicians prefer it to other axioms." —&nbsp;[[A. K. Dewdney]]
:This quote comes from the famous [[April Fools' Day]] article in the ''computer recreations'' column of the ''[[Scientific American]]'', April 1989.
 
== Notes ==
<references />
 
==References==
* Horst Herrlich, ''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.
* Per Martin-Löf, "100 years of Zermelo's axiom of choice: What was the problem with it?", in ''Logicism, Intuitionism, and Formalism: What Has Become of Them?'', Sten Lindström, Erik Palmgren, Krister Segerberg, and Viggo Stoltenberg-Hansen, editors (2008). ISBN 1-4020-8925-2
*Gregory H Moore, "Zermelo's axiom of choice, Its origins, development and influence", [[Springer Science+Business Media|Springer]]; 1982. ISBN 0-387-90670-3, available as a [[Dover Publications]] reprint, 2013, ISBN 0-486-48841-1.
*Herman Rubin, Jean E. Rubin: Equivalents of the axiom of choice. North Holland, 1963. Reissued by [[Elsevier]], April 1970. ISBN 0-7204-2225-6.
*Herman Rubin, Jean E. Rubin: Equivalents of the Axiom of Choice II. North Holland/Elsevier, July 1985, ISBN 0-444-87708-8.
*George Tourlakis, ''Lectures in Logic and Set Theory. Vol. II: Set Theory'', [[Cambridge University Press]], 2003. ISBN 0-511-06659-7
*[[Ernst Zermelo]], "Untersuchungen über die Grundlagen der Mengenlehre I," ''Mathematische Annalen 65'': (1908) pp.&nbsp;261–81. [http://www.digizeitschriften.de/no_cache/home/jkdigitools/loader/?tx_jkDigiTools_pi1%5BIDDOC%5D=361762 PDF download via digizeitschriften.de]
::Translated in: [[Jean van Heijenoort]], 2002. ''From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931''. New edition. [[Harvard University 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.
 
==External links==
*{{springer|title=Axiom of choice|id=p/a014270}}
*[http://www.apronus.com/provenmath/choice.htm 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.
*[http://www.math.purdue.edu/~hrubin/JeanRubin/Papers/conseq.html Consequences of the Axiom of Choice], based on the book by [http://www.emunix.emich.edu/~phoward/ Paul Howard] and Jean Rubin.
*{{sep entry|axiom-choice|The Axiom of Choice|[[John Lane Bell]]}}
 
{{Set theory}}
 
{{DEFAULTSORT:Axiom Of Choice}}
[[Category:Axiom of choice| ]]

Latest revision as of 06:44, 23 December 2014

Click here http://tinyurl.com/qd4atl3 and use coupon code LEINBO for 57% off on the Legal Insider Bot Software

Retrieved from "https://en.formulasearchengine.com/index.php?title=Axiom_of_choice&oldid=218481"