Axiom of choice: Difference between revisions
Jump to navigation
Jump to search
imported>Tito Omburo m Undid revision 1294714974 by Goodphy (talk) |
imported>Trovatore →Statement: The variable X is not used elsewhere in the statement, so it isn't needed and could be confusing |
||
| Line 3: | Line 3: | ||
{{Redirect-distinguish|ZF¬C|ZFC (disambiguation)}} | {{Redirect-distinguish|ZF¬C|ZFC (disambiguation)}} | ||
{{Use dmy dates|date=October 2021}} | {{Use dmy dates|date=October 2021}} | ||
[[File:Axiome du choix. | [[File:Axiome du choix.svg|thumb|Illustration of the axiom of choice, with each set ''S''<sub>''i''</sub> represented as a jar and its elements represented as marbles. Each element ''x''<sub>''i''</sub> is represented as a marble on the right. Colors are used to suggest a functional association of marbles after adopting the choice axiom. The existence of such a choice function is in general independent of ZF for collections of infinite cardinality, even if all ''S''<sub>''i''</sub> are finite.]] | ||
[[File:Axiom of choice.svg|thumb | [[File:Axiom of choice.svg|thumb|(S<sub>''i''</sub>) is an infinite [[indexed 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 at least one, and possibly infinitely many, elements. The axiom of choice allows us to 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>, (called index set whose elements are used as indices for elements in a set) not just '''R'''.]] | ||
In [[mathematics]], the '''axiom of choice''', abbreviated '''AC''' or '''AoC''', is an [[axiom]] of [[set theory]]. Informally put, the axiom of choice says that given any [[Family of sets|collection]] of non-empty sets, it is possible to construct a new set by choosing one element from each set, even if the collection is [[Infinite set|infinite]]. Formally, it states that for every [[indexed family]] <math>(S_i)_{i \in I}</math> of [[nonempty]] sets, there exists an indexed set <math>(x_i)_{i \in I}</math> 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]].{{sfn|Zermelo|1904}} | In [[mathematics]], the '''axiom of choice''', abbreviated '''AC''' or '''AoC''', is an [[axiom]] of [[set theory]]. Informally put, the axiom of choice says that given any [[Family of sets|collection]] of non-empty sets, it is possible to construct a new set by choosing one element from each set, even if the collection is [[Infinite set|infinite]]. Formally, it states that for every set <math>I</math> and every <math>I</math>-[[indexed family]] <math>(S_i)_{i \in I}</math> of [[nonempty]] sets, there exists an <math>I</math>-indexed set <math>(x_i)_{i \in I}</math> of elements of <math>\cup_{i\in I}S_i</math> 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]].{{sfn|Zermelo|1904}} | ||
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 | 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 (in which induction can be applied), 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 {{brace|{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 a [[choice function]]. Even if infinitely many sets are collected from the natural numbers, it will always be possible to form a choice function from choosing the smallest element from each set to produce a set; the axiom of choice is not needed here. On the other hand, for the collection of all non-empty subsets of the real numbers, there is ''no'' known ''canonical'' rule by which one can choose one element from each of these subsets. In that case, the axiom of choice must be invoked to construct the desired choice function. | ||
[[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 | [[Bertrand Russell]] coined an analogy: for any (even infinite) collection of unordered 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 without using the axiom of choice. However, for an infinite collection of unordered pairs of ''socks'' (assumed to have no distinguishing features such as being a left sock rather than a right sock), there is no ''natural'' (i.e., canonical) way of choosing one sock from each pair, so one must appeal to the axiom of choice to construct the desired choice function.{{sfn|Jech|1977|p=351}} | ||
Although originally controversial, the axiom of choice is now used without reservation by most mathematicians,<ref>{{harvnb|Jech|1977|p=348 ff}}; {{harvnb|Mac Lane|1986|pages= | Although originally controversial, the axiom of choice is now used without reservation by most mathematicians,<ref>{{harvnb|Jech|1977|p=348 ff}}; {{harvnb|Mac Lane|1986|pages=366–367}}; {{harvnb|Martin-Löf|2008|p=210}}. According to {{harvnb|Mendelson|1964|p=201}}: "The status of the Axiom of Choice has become less controversial in recent years. To most mathematicians it seems quite plausible and it has so many important applications in practically all branches of mathematics that not to accept it would seem to be a wilful hobbling of the practicing mathematician."</ref> and is included in the standard form of [[axiomatic 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 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]]. While some varieties of [[Constructivism (mathematics)|constructive mathematics]] avoid the axiom of choice, others embrace it. | ||
==Statement== | ==Statement== | ||
A [[choice function]] (also called selector or selection) is a function <math>f</math>, defined on a collection <math>X</math> of nonempty sets, such that for every set <math>A</math> in <math>X</math>, <math>f(A)</math> is an element of <math>A</math>. With this concept, the axiom can be stated: | A [[choice function]] (also called selector or selection) is a function <math>f</math>, defined on a collection <math>X</math> of nonempty sets, such that for every set <math>A</math> in <math>X</math>, <math>f(A)</math> is an element of <math>A</math>. With this concept, the axiom can be stated: | ||
{{math theorem|For any set <math>X</math> of nonempty sets, there exists a choice function | {{math theorem|For any set <math>X</math> of nonempty sets, there exists a choice function <math>f</math> that is defined on <math>X</math> and maps each set of <math>X</math> to an element of that set. | ||
| name = Axiom | | name = Axiom | ||
}} | }} | ||
| Line 23: | Line 22: | ||
Formally, this may be expressed as follows: | Formally, this may be expressed as follows: | ||
<math display="block">\forall X \left[ \varnothing \in X \lor \exist f \left[ \mathrm{dom} \ f = X \land \forall A \in X \left[ f\left(A\right) \in A \right] \right] \right].</math> | |||
Each choice function on a family <math>X</math> of nonempty sets is an element of the [[Cartesian product#Infinite Cartesian products|Cartesian product]] of the sets in <math>X</math>, and vice versa. Therefore an equivalent form of the axiom of choice is: | |||
{{block indent|The Cartesian product of any collection of nonempty sets is nonempty.}} | |||
This form implies a more general form where the Cartesian product is of a general [[indexed family]] of sets (which may contain duplicates), since one can always select the same element from duplicate factors. | |||
===Nomenclature=== | ===Nomenclature=== | ||
In this article and other discussions of the | In this article and other discussions of the axiom of choice the following abbreviations are common: | ||
*AC – the | *AC – the axiom of choice. More rarely, AoC is used.{{sfn|Rosenberg|2021}} | ||
*ZF – [[Zermelo–Fraenkel set theory]] omitting the | *ZF – [[Zermelo–Fraenkel set theory]] omitting the axiom of choice. | ||
*ZFC – Zermelo–Fraenkel set theory, extended to include the | *ZFC – Zermelo–Fraenkel set theory, extended to include the axiom of choice. | ||
===Variants=== | ===Variants=== | ||
| Line 48: | Line 42: | ||
One variation avoids the use of choice functions by, in effect, replacing each choice function with its range: | One variation avoids the use of choice functions by, in effect, replacing each choice function with its range: | ||
{{block indent|Given any set <math>X</math>, if the empty set is not an element of <math>X</math> and the elements of <math>X</math> are [[pairwise disjoint]], then there exists a set <math>C</math> such that its intersection with any of the elements of <math>X</math> contains exactly one element.<ref>{{harvnb|Herrlich|2006|p=9}}. According to {{harvnb|Suppes|1972|p=243}}, this was the formulation of the axiom of choice which was originally given by {{harvnb|Zermelo|1904}}. See also {{harvnb|Halmos|1960|p=60}} for this formulation.</ref>}} | |||
This can be formalized in first-order logic as: | This can be formalized in first-order logic as: | ||
<math> | <math display="block"> | ||
\begin{align} | \begin{align} | ||
\forall x (& \\ | \forall x (& \\ | ||
| Line 61: | Line 55: | ||
</math> | </math> | ||
Note that <math>P \or Q \or R</math> is logically equivalent to <math>(\lnot P \and \lnot Q) \implies R</math>. | Note that <math>P \or Q \or R</math> is logically equivalent to <math>(\lnot P \and \lnot Q) \implies R</math>. In English, this first-order sentence reads: | ||
In English, this first-order sentence reads: | |||
{{block indent|Given any set <math>X</math>,}} | |||
{{block indent|<math>X</math> contains the empty set as an element or}} | |||
{{block indent|the elements of <math>X</math> are not pairwise disjoint or}} | |||
{{block indent|there exists a set <math>C</math> such that its intersection with any of the elements of <math>X</math> contains exactly one element.}} | |||
This guarantees for any [[partition of a set]] <math>X</math> the existence of a subset <math>C</math> of <math>X</math> containing exactly one element from each part of the partition. | This guarantees for any [[partition of a set]] <math>X</math> the existence of a subset <math>C</math> of <math>X</math> containing exactly one element from each part of the partition. | ||
Another equivalent axiom only considers collections <math>X</math> that are essentially powersets of other sets: | Another equivalent axiom only considers collections <math>X</math> that are essentially powersets of other sets: | ||
{{block indent|For any set <math>A</math>, the [[power set]] of <math>A</math> (with the empty set removed) has a choice function.}} | |||
Authors who use this formulation often speak of the ''choice function on <math>A</math>'', but this is a slightly different notion of choice function. | Authors who use this formulation often speak of the ''choice function on <math>A</math>'', but this is a slightly different notion of choice function. Its domain is the power set of <math>A</math> (with the empty set removed), and so makes sense for any set <math>A</math>, 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 | ||
{{block indent|Every set has a choice function.{{sfn|Suppes|1972|p=240}}}} | |||
which is equivalent to | which is equivalent to | ||
{{block indent|For any set <math>A</math> there is a function <math>f:\mathcal P(A)\setminus\{ \emptyset \} \to A </math> such that for any non-empty subset <math>B</math> of <math>A</math>, <math>f(B)</math> lies in <math>B</math>.}} | |||
The negation of the axiom can thus be expressed as: | The negation of the axiom can thus be expressed as: | ||
{{block indent|There is a set <math>A</math> such that for all functions <math>f</math> (on the set of non-empty subsets of <math>A</math>), there is a subset <math>B</math> such that <math>f(B)</math> does not lie in <math>B</math>.}} | |||
==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''" to define a function ''F''. 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 full axiom of choice. For a finite collection of 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 form a set through choosing exactly one item from each box. Clearly, we can do this with the principle of finite induction: 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 induction guarantees that our choice procedure is well-defined and eventually terminates. 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. This shows that the axiom of choice restricted to finite sets (i.e., the statement "for every natural number ''k'', every family of ''k'' nonempty sets has a choice function") is a direct consequence of the axiom of finite induction and does not need anything beyond ZF. However, this argument will not work if the collection of sets ''X'' is infinite. For example, to show that every infinite sequence of nonempty sets has a choice function, as is asserted by the [[axiom of countable choice]], one needs to go beyond finite induction to countably transfinite induction. If the above 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 (within ZF). Countable transfinite induction (a.k.a. the [[axiom of dependent choice]]) essentially guarantees the existence of such a "limiting" choice function, and thus implies the axiom of countable choice. It is however weaker than the full axiom of choice.--> <!--This whole section needs rewriting; it says something kind of true, but equates choice with induction, which is wrong. Choice is induction plus choosing. --> | |||
==Examples== | |||
=== Cases where the axiom of choice is not needed === | |||
The existence of a choice function for a [[finite set|finite collection]] of nonempty sets can be proved by the [[mathematical induction|principle of finite induction]], without appealing to the axiom of choice.{{sfn|Tourlakis|2003|pp=209–210, 215–216}} The proof uses the fact that, given a ''single'' nonempty set {{tmath|A}}, [[first-order logic]] allows choosing some concrete {{tmath|a \in A}}. However, since a proof in first-order logic must be finite, one cannot make an infinite number of choices with first-order logic alone. | |||
Another case where the axiom of choice is not needed is when there exists an explicit rule that gives a ''canonical'' choice function. For example, if each member of the collection {{tmath|X}} is a nonempty subset of the natural numbers, then one such explicit rule is to choose the ''smallest element'' of each {{tmath|A \in X}}. The canonical choice function that maps each {{tmath|A \in X}} to its smallest element can again be constructed in ZF without the axiom of choice. | |||
In general, if the union of all sets in {{tmath|X}} can be [[well-order]]ed, then a choice function for {{tmath|X}} can be constructed without using the axiom of choice. Note that it does not suffice that each {{tmath|A \in X}} can be well-ordered, since the axiom of choice may be needed to choose a ''canonical well-ordering'' for each {{tmath|A}} anyway. | |||
== | === Real numbers === | ||
As an example where the axiom of choice is required, let {{tmath|X}} be set of all non-empty subsets of the [[real number]]s. Choosing the least element from each set no longer works, because some subsets of the real numbers do not have least elements. For example, the [[open interval]] {{tmath|(0,1)}} does not have a least element: if {{tmath|x}} is in {{tmath|(0,1)}}, then so is {{tmath|x/2}}, and {{tmath|x/2}} is always strictly smaller than {{tmath|x}}. This strategy fails here because the natural order of real numbers is not a [[well-order]]. | |||
If there exists a different ordering of the real numbers which is a well-ordering, then applying the least-element strategy with respect to that ordering would give a choice function for {{tmath|X}}. Conversely, if there exists a choice function for {{tmath|X}}, then the proof of the [[well-ordering theorem]] would show that a well-ordering of the real numbers does exist. | |||
=== Constructing a non-measurable set === | |||
{{main|Non-measurable set#Examples}} | |||
Let {{tmath|S}} be the unit circle, and {{tmath|G}} be the group consisting of all rational rotations (i.e., rotations by angles which are rational multiples of {{tmath|\pi}}). Since {{tmath|G}} is countable while {{tmath|S}} is uncountable, {{tmath|S}} must break up into uncountably many [[orbit (group theory)|orbit]]s under the action of {{tmath|G}}. | |||
Using the axiom of choice, we could pick a single point from each orbit, obtaining an uncountable subset {{tmath|X}} of {{tmath|S}} with the property that all of its translates by {{tmath|G}} are disjoint from {{tmath|X}}. The set of those translates partitions the circle into a countable collection of pairwise disjoint sets, which are all pairwise congruent. The set {{tmath|X}} will be non-measurable for any rotation-invariant countably additive measure on {{tmath|S}}: if {{tmath|X}} has zero measure, countable additivity would imply that the whole circle has zero measure. If {{tmath|X}} has positive measure, countable additivity would show that the circle has infinite measure. | |||
Applying a similar construction to the three-dimensional ball can result in a set that is non-measurable even for any rotation-invariant ''finitely'' additive measure, as shown by the [[Banach–Tarski paradox]]. | |||
==Criticism and acceptance== | ==Criticism and acceptance== | ||
A proof requiring the axiom of choice may establish the existence of an object without | A proof requiring the axiom of choice may establish the existence of an object without ''canonically'' [[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 individual well-ordering of the reals is definable. Similarly, although a subset of the real numbers that is not [[Lebesgue measure|Lebesgue measurable]] can be proved to exist using the axiom of choice, it is [[consistent]] that no such set is definable.{{sfn|Fraenkel|Bar-Hillel|Lévy|1973|pp=69–70}} | ||
The axiom of choice asserts the existence of these intangibles (objects that are proved to exist, but which cannot be | The axiom of choice asserts the existence of these intangibles (objects that are proved to exist, but which cannot be constructed in any ''canonical'' way), which may conflict with some philosophical principles.{{sfn|Rosenbloom|2005|page=147}} Because there is no 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 objects that may seem counterintuitive.<ref>{{harvnb|Dawson|2006}}: "The axiom of choice, though it had been employed unconsciously in many arguments in analysis, became controversial once made explicit, not only because of its non-constructive character, but because it implied such extremely unintuitive consequences as the Banach–Tarski paradox."</ref> One example is the [[Banach–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, are [[non-measurable set]]s. | Another argument against the axiom of choice is that it implies the existence of objects that may seem counterintuitive.<ref>{{harvnb|Dawson|2006}}: "The axiom of choice, though it had been employed unconsciously in many arguments in analysis, became controversial once made explicit, not only because of its non-constructive character, but because it implied such extremely unintuitive consequences as the Banach–Tarski paradox."</ref> One example is the [[Banach–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, are [[non-measurable set]]s. | ||
| Line 115: | Line 116: | ||
==In constructive mathematics== | ==In constructive mathematics== | ||
As discussed above, in the classical theory of ZFC, the axiom of choice enables [[nonconstructive proof]]s in which the existence of a type of object is proved without an explicit instance | As discussed above, in the classical theory of ZFC, the axiom of choice enables [[nonconstructive proof]]s in which the existence of a type of object is proved without an explicit canonical construction of an instance of this type. In fact, in set theory and [[topos theory]], [[Diaconescu's theorem]] shows that the axiom of choice implies the [[law of excluded middle]]. The principle is thus not available in [[constructive set theory]], where non-classical logic is employed. | ||
The situation is different when the principle is formulated in [[Martin-Löf type theory]]. There 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]], ''[https://www.cs.cmu.edu/afs/cs/Web/People/crary/819-f09/Martin-Lof80.pdf Intuitionistic type theory]'', 1980. | The situation is different when the principle is formulated in [[Martin-Löf type theory]]. There 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]], ''[https://www.cs.cmu.edu/afs/cs/Web/People/crary/819-f09/Martin-Lof80.pdf Intuitionistic type theory]'', 1980. | ||
| Line 135: | Line 136: | ||
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 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. | 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 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 nontrivial [[Ring (mathematics)|ring]] | 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 nontrivial unital [[Ring (mathematics)|ring]] has a [[maximal ideal]], every [[vector space]] has a [[Basis (linear algebra)|basis]], every [[connected graph]] has a [[spanning tree]], and every [[Product topology|product]] of [[compact space]]s 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 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 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 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 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. | ||
| Line 142: | Line 143: | ||
==Stronger axioms== | ==Stronger axioms== | ||
The [[axiom of constructibility]] and the [[Continuum hypothesis#The generalized continuum hypothesis|generalized continuum hypothesis]] each imply the axiom of choice and | The [[axiom of constructibility]] and the [[Continuum hypothesis#The generalized continuum hypothesis|generalized continuum hypothesis]] each imply the axiom of choice and are strictly stronger than it. In class theories such as [[Von Neumann–Bernays–Gödel set theory]] and [[Morse–Kelley set theory]], there is an axiom called the [[axiom 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 the [[axiom of limitation of size]]. Tarski's axiom, which is used in [[Tarski–Grothendieck set theory]] and states (in the vernacular) that every set belongs to {{em|some}} [[Grothendieck universe]], is stronger than the axiom of choice. | ||
==Equivalents== | ==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.<ref>See {{harvnb|Moore|2013|pages=330–334}}, for a structured list of 74 equivalents. See {{harvnb|Howard|Rubin|1998|pp=11–16}}, for 86 equivalents with source references.</ref> 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. | 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 (that is, their truth values in ZF, while undecidable, are the same as that of AC).<ref>See {{harvnb|Moore|2013|pages=330–334}}, for a structured list of 74 equivalents. See {{harvnb|Howard|Rubin|1998|pp=11–16}}, for 86 equivalents with source references.</ref> 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]] | *[[Set theory]] | ||
**[[Tarski's theorem about choice]]: For every infinite set | **Trichotomy: The cardinalities of any two sets are comparable with each other. That is, given any two sets, an [[injective function|injection]] exists from (at least) one of the sets to the other. | ||
**[[Tarski's theorem about choice]]: For every infinite set <math>A</math>, the sets <math>A</math> and <math>A\times A</math> have the same [[cardinality]]; i.e., there exists a [[bijective function|bijection]] between them. | |||
**Every [[surjective function|surjection]] <math>f:S\to T</math> has a [[Inverse function#Left and right inverses|right inverse]]; i.e., there exists a function <math>g:T\to S</math> such that <math>f\circ g = \mathrm{id}_T</math>. | |||
**Every [[surjective function]] has a [[Inverse function#Left and right inverses|right inverse]]. | **For every disjoint collection <math>\mathcal{C}</math> of nonempty sets, there exists a set <math>C\subseteq\cup_{S \in \mathcal{C}}(S)</math> that intersects each member of <math>\mathcal{C}</math> in exactly one element. That is, every [[partition of a set]] has a [[transversal (combinatorics)|transversal]].<ref>{{cite web|url=https://plato.stanford.edu/entries/axiom-choice/|title=The Axiom of Choice|website=Stanford Encyclopedia of Philosophy|first=Bell|last=John|date=December 10, 2021|access-date=December 2, 2024|quote=Let us call Zermelo's 1908 formulation the combinatorial axiom of choice: CAC: Any collection of mutually disjoint nonempty sets has a transversal.}}</ref> | ||
**The [[Cartesian product#Infinite Cartesian products|Cartesian product]] of any family of nonempty sets is nonempty. | **If a relation <math>R</math> from a set <math>X</math> to a set <math>Y</math> has the property that for every <math>x \in X</math>, there is a <math>y \in Y</math> with <math>x R y</math>, then there exists a function <math>f:X\to Y</math> such that <math>x R f(x)</math> for all <math>x\in X</math>. | ||
** | **The [[Cartesian product#Infinite Cartesian products|Cartesian product]] of any [[indexed family]] of nonempty sets is nonempty. That is, for any set <math>I</math>, and any <math>I</math>-indexed family <math>(S_i)_{i\in I}</math> of nonempty sets, there exists an <math>I</math>-indexed set <math>(s_i)_{i\in I}</math> of elements in <math>\cup_{i\in I}(S_i)</math> such that <math>s_i\in S_i</math> for all <math>i \in I</math>. | ||
**[[Well-ordering theorem]]: Every set | **In any collection <math>\mathcal{A}</math> of nonempty sets, there exists a disjoint subcollection <math>\mathcal{C}</math> of sets whose union <math>\cup_{S\in\mathcal{C}}(S)</math> intersects all the members of <math>\mathcal{A}</math>. (Note that such a disjoint subcollection is precisely one that is ''maximal'' with respect to set inclusion.) | ||
**[[ | **For any set <math>X</math>, there exists a ''maximal'' (under set inclusion) collection <math>\mathcal{A}</math> of subsets of <math>X</math> for which every ''finite'' subcollection <math>\mathcal{C}</math> of <math>\mathcal{A}</math> has a nonempty intersection <math>\cap_{S\in\mathcal{C}}(S)</math>. (This statement is key to a standard proof of [[Tychonoff's theorem]].) | ||
**[[Hausdorff maximal principle]]: Every partially ordered set has a maximal chain. Equivalently, in | **[[Well-ordering theorem]]: Every set <math>A</math> has a [[well-ordered set|well-ordering]] (i.e., a [[totally ordered set|total ordering]] in which every nonempty subset of <math>A</math> has a minimum element). Consequently, every [[cardinal number|cardinal]] has an [[initial ordinal]]. | ||
**[[ | **For every [[ordinal number|ordinal]] <math>\alpha</math>, the powerset (i.e., the set of all subsets) of <math>\alpha</math> has a well-ordering. | ||
**[[ | **[[Hausdorff maximal principle]]: Every [[partially ordered set]] has a maximal [[totally ordered set|chain]] (with respect to inclusion). Equivalently, in a partially ordered set, every chain can be extended to a maximal chain. | ||
**The | **[[Antichain]] principle: Every partially ordered set has a maximal [[antichain]] (with respect to inclusion). Equivalently, in any partially ordered set, every antichain can be extended to a maximal antichain. | ||
**[[Zorn's lemma]]: If <math>(A,<)</math> is any partially ordered set in which every chain has an upper bound in <math>A</math>, then <math>(A,<)</math> has at least one maximal element. | |||
**[[Kuratowski's lemma]]: If <math>\mathcal{A}</math> is any family of sets with the property that for any subfamily <math>\mathcal{C}</math> of <math>\mathcal{A}</math> totally ordered by set inclusion, the union <math>\cup_{A\in\mathcal{C}}(A)</math> is an element of <math>\mathcal{A}</math>, then <math>\mathcal{A}</math> has at least one element ''maximal'' with respect to inclusion. | |||
**[[Tukey's lemma]]: If <math>\mathcal{A}</math> is any family of subsets of a set <math>X</math> with the property that a set <math>B\subseteq X</math> is an element of <math>\mathcal{A}</math> iff every ''finite'' subset of <math>B</math> is an element of <math>\mathcal{A}</math>, then <math>\mathcal{A}</math> has at least one element ''maximal'' with respect to inclusion. | |||
**[[König's theorem (set theory)|König's theorem]]: Informally, the sum of a sequence of cardinals is strictly less than the product of a sequence of larger cardinals. (The reason for the term "informally" is that the sum or product of a "sequence" of cardinals cannot itself be defined without some aspect of the axiom of choice.) | |||
*[[Abstract algebra]] | *[[Abstract algebra]] | ||
**Every [[vector space]] has a [[basis (linear algebra)|basis]] | **Every [[vector space]] has a [[basis (linear algebra)|basis]]; equivalently, every [[linearly independent]] subset of a vector space can be extended to a basis, while every [[span (linear algebra)|spanning subset]] contains a basis. In the language of [[module theory]], all vector spaces are [[free module]]s.<ref>{{cite conference | ||
| last = Blass | first = Andreas | | last = Blass | first = Andreas | ||
| contribution = Existence of bases implies the axiom of choice | | contribution = Existence of bases implies the axiom of choice | ||
| doi = 10.1090/conm/031/763890 | | doi = 10.1090/conm/031/763890<!--doi.org link is dead--> | ||
| url = https://www.semanticscholar.org/paper/Existence-of-bases-implies-the-axiom-of-choice-Blass/156d82acf678351a1442fd4cba8f2c7ad4019bfa | |||
| mr = 763890 | | mr = 763890 | ||
| pages = 31–33 | | pages = 31–33 | ||
| publisher = American Mathematical Society | location = Providence, | | publisher = American Mathematical Society | location = Providence, Rhode Island | ||
| series = Contemporary Mathematics | | series = Contemporary Mathematics | ||
| title = Axiomatic set theory | | title = Axiomatic set theory | ||
| publication-place = Boulder, Colorado | |||
| orig-year = 1983 | |||
| volume = 31 | | volume = 31 | ||
| year = 1984| isbn = 978-0-8218-5026-8 | | year = 1984 | ||
| isbn = 978-0-8218-5026-8 | |||
**[[Krull's theorem]]: Every unital [[ring (mathematics)|ring]] | }}</ref>{{verification needed|reason=publication place and year are duplicated|date=April 2026}} | ||
**For every non-empty set | **[[Krull's theorem]]: Every nontrivial unital [[ring (mathematics)|ring]] contains a [[maximal ideal]]; equivalently, every proper [[ideal (ring theory)|ideal]] of a unital ring can be extended to a maximal ideal. | ||
**For every non-empty set <math>S</math> there is a [[binary operation]] defined on <math>S</math> that gives it a [[group (mathematics)|group structure]].<ref>{{harvnb|Hajnal|Kertész|1972}}, see also {{harvnb|Rubin|Rubin|1985|p=111}}.</ref> (A [[cancellation property|cancellative]] binary operation is enough; see [[Group structure and the axiom of choice]].) | |||
**Every [[free abelian group]] is [[projective module|projective]].{{sfn|Blass|1979}} | **Every [[free abelian group]] is [[projective module|projective]].{{sfn|Blass|1979}} | ||
**Baer's criterion: Every [[divisible group|divisible abelian group]] is [[injective module|injective]].{{sfn|Blass|1979}} | **Baer's criterion: Every [[divisible group|divisible abelian group]] is [[injective module|injective]].{{sfn|Blass|1979}} | ||
**Every set is a [[projective object]] in the [[ | **Every set is a [[projective object]] in the [[category of sets]].<ref>{{Cite book|title=Category theory|url=https://archive.org/details/categorytheoryse00awod|url-access=limited|last=Awodey|first=Steve|date=2010|publisher=Oxford University Press|isbn=978-0199237180|edition=2nd|location=Oxford|pages=[https://archive.org/details/categorytheoryse00awod/page/n36 20]–24|oclc=740446073}}</ref><ref>{{nlab|id=projective+object|title=projective object}}</ref> | ||
*[[Functional analysis]] | *[[Functional analysis]] | ||
**The closed unit ball of the dual of a [[normed vector space]] over the reals has an [[extreme point]]. | **The closed unit ball of the dual of a [[normed vector space]] over the reals has an [[extreme point]]. | ||
*[[Point-set topology]] | *[[Point-set topology]] | ||
**The [[product topology| | **[[Tychonoff's theorem]]: The [[product topology|product]] of any [[indexed family]] of [[Compact space|compact topological spaces]] is compact. | ||
**The [[closure (topology)|closure]] of the product of any indexed family of subsets of a topological space is equal to the product of the closures of those subsets. | |||
** | |||
*[[Mathematical logic]] | *[[Mathematical logic]] | ||
**If | **If <math>S</math> is a set of sentences of [[first-order logic]] and <math>B</math> is a consistent subset of <math>S</math>, then <math>B</math> is included in a set that is maximal among consistent subsets of <math>S</math>. The special case where <math>S</math> 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. | ||
**[[ | **[[Löwenheim–Skolem theorem]]: If a first-order theory has an infinite model, then it has an infinite model of every possible cardinality greater than or equal to the cardinality of the language of this theory. | ||
*[[Graph theory]] | *[[Graph theory]] | ||
**Every [[ | **Every connected [[graph theory|graph]] has a [[spanning tree]]; equivalently, every [[tree (graph theory)|tree]] in a connected graph can be extended to a spanning tree, while every [[spanning subgraph]] contains a spanning tree.<ref>{{cite book|title=Trees|first=Jean-Pierre|last=Serre|author-link=Jean-Pierre Serre|page=23|publisher=Springer|series=Springer Monographs in Mathematics|year=2003}}</ref><ref>{{cite book | ||
| last = Soukup | first = Lajos | | last = Soukup | first = Lajos | ||
| contribution = Infinite combinatorics: from finite to infinite | | contribution = Infinite combinatorics: from finite to infinite | ||
| Line 201: | Line 209: | ||
| year = 2008| citeseerx = 10.1.1.222.5699 | | year = 2008| citeseerx = 10.1.1.222.5699 | ||
| isbn = 978-3-540-77199-9 | | isbn = 978-3-540-77199-9 | ||
}} | }} See in particular Theorem 2.1, [https://books.google.com/books?id=kIKW18ENfUMC&pg=PA192 pp. 192–193].</ref> | ||
===Category theory=== | ===Category theory=== | ||
| Line 207: | Line 215: | ||
Examples of category-theoretic statements which require choice include: | Examples of category-theoretic statements which require choice include: | ||
*Every | *Every [[small category]] has a [[skeleton (category theory)|skeleton]]. | ||
*If two small categories are weakly equivalent, then they are [[equivalence of categories|equivalent]]. | *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 | *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== | ==Weaker forms== | ||
There are several weaker statements that are | There are several weaker statements unprovable in ZF that are logically implied by the axiom of choice (AC) within ZF but are not equivalent to AC. 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 family 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 subsets of real numbers, that are disprovable from the full axiom of choice. | ||
Given an ordinal parameter α ≥ ω+2 & | Given an ordinal parameter α ≥ ω+2 – for every set ''S'' with rank less than α, ''S'' is well-orderable. Given an ordinal parameter α ≥ 1 – for every set ''S'' with [[Hartogs number]] less than ω<sub>α</sub>, ''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 the [[Boolean prime ideal theorem]] and the [[Uniformization (set theory)|axiom of uniformization]]. | 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 [[Alfred Tarski|Tarski]]'s 1930 [[ultrafilter lemma]]: every [[Filter on a set|filter]] is a subset of some [[Ultrafilter on a set|ultrafilter]]. | ||
===Results requiring AC (or weaker forms) but weaker than it===<!-- This section is linked from [[Basis (linear algebra)]] --> | ===Results requiring AC (or weaker forms) but weaker than it===<!-- This section is linked from [[Basis (linear algebra)]] --> | ||
| Line 222: | Line 230: | ||
*[[Set theory]] | *[[Set theory]] | ||
**The [[ | **[[Axiom of countable choice]]: The Cartesian product of any sequence (i.e., countable [[indexed family]]) of nonempty sets is nonempty. (This is just the axiom of choice with the indexing set restricted to countable size.) | ||
**The [[union (set theory)|union]] of any countable family of [[countable sets]] is countable (this | **[[Axiom of dependent choice]]: If <math>R </math> is any relation on a set <math>S </math> with the property that for every <math>x \in S </math>, there is a <math>y \in S </math> with <math>x R y </math>, then, for every <math>x\in S</math>, there exists a sequence <math>\left(x_n\right)_{n \in \mathbb{N}}</math> in <math>S</math> starting at <math>x</math> and satisfying <math>x_n R x_{n+1} </math> for all <math>n \in \mathbb{N}</math>. (In ZF, this statement logically implies the [[axiom of countable choice]], and is strictly stronger.) | ||
** | **Axiom of choice for finite sets: The Cartesian product of any indexed family of non-empty {{em|finite}} sets is nonempty. (Note that here, it is each ''member'' of the indexed family that is restricted in size, not the ''indexing set'', in contrast with [[axiom of countable choice|countable choice]].) | ||
**Ultrafilter lemma: Every [[filter (mathematics)|filter]] on a set <math>S</math> can be extended to an [[ultrafilter]] on <math>S</math>. (In ZF, this statement logically implies the Axiom of choice for finite sets (above)<ref name="Muger2020">{{cite book|last=Muger|first= Michael|title=Topology for the Working Mathematician|year=2020}}</ref>.) | |||
**The [[union (set theory)|union]] of any countable family of [[countable sets]] is countable. (In ZF, this statement is logically implied by the [[axiom of countable choice]].) | |||
**Every [[infinite set|infinite]] set has a countable-infinite subset, i.e., has [[cardinal number|cardinality]] greater than or equal to <math>\aleph_0</math>. (In ZF, this statement is logically implied by the [[axiom of countable choice]] but is not equivalent; see [[Dedekind infinite]].)<ref>It is shown by {{harvnb|Jech|2008|pp=119–131}}, that the axiom of countable choice implies the equivalence of infinite and Dedekind-infinite sets, but that the equivalence of infinite and Dedekind-infinite sets does not imply the axiom of countable choice in ZF.</ref> | |||
**Eight definitions of a [[finite set#Other concepts of finiteness|finite set]] are equivalent.<ref>It was shown by {{harvnb|Lévy|1958}} and others using Mostowski models that eight definitions of a finite set are independent in ZF without AC, although they are equivalent when AC is assumed. The definitions are I-finite, Ia-finite, II-finite, III-finite, IV-finite, V-finite, VI-finite and VII-finite. I-finiteness is the same as normal finiteness. IV-finiteness is the same as Dedekind-finiteness.</ref> | **Eight definitions of a [[finite set#Other concepts of finiteness|finite set]] are equivalent.<ref>It was shown by {{harvnb|Lévy|1958}} and others using Mostowski models that eight definitions of a finite set are independent in ZF without AC, although they are equivalent when AC is assumed. The definitions are I-finite, Ia-finite, II-finite, III-finite, IV-finite, V-finite, VI-finite and VII-finite. I-finiteness is the same as normal finiteness. IV-finiteness is the same as Dedekind-finiteness.</ref> | ||
**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]]. | **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]]. | ||
* Every infinite [[cardinal number|cardinal]] | ** Every infinite [[cardinal number|cardinal]] <math>\kappa</math> satisfies <math>2\kappa=\kappa</math>.<ref>{{cite journal|last=Sageev|first=Gershon|title=An independence result concerning the axiom of choice|journal=Annals of Mathematical Logic|volume=8|issue=1–2|date=March 1975|pages=1–184|doi=10.1016/0003-4843(75)90002-9}}</ref> | ||
*[[Measure theory]] | *[[Measure theory]] | ||
**The [[Vitali set|Vitali theorem]] | **The [[Vitali set|Vitali theorem]]: There exist subsets of <math>\mathbb{R}^n</math> (for any <math>n>0</math>) that are not [[Lebesgue measurable]]; i.e., the set of all subsets of <math>\mathbb{R}^n</math> does not form a [[measure space]] of <math>\mathbb{R}^n</math> under the standard (Lebesgue) outer-measure. | ||
**There exist Lebesgue-measurable subsets of | **There exist Lebesgue-measurable subsets of <math>\mathbb{R}^n</math> that are not [[Borel set]]s; i.e., the Borel <math>\sigma</math>-algebra on <math>\mathbb{R}^n</math> is ''strictly'' contained in the Lebesgue-measure <math>\sigma</math>-algebra on <math>\mathbb{R}^n</math>. | ||
**The [[Hausdorff paradox]]. | **The [[Hausdorff paradox]]. | ||
**The [[Banach–Tarski paradox]]. | **The [[Banach–Tarski paradox]]. | ||
*[[ | *[[Abstract algebra]] | ||
**Every [[field (mathematics)|field]] has an [[algebraic closure]]. | **Every [[field (mathematics)|field]] has an [[algebraic closure]]. | ||
**Every [[field extension]] has a [[transcendence basis]]. | **Every [[field extension]] has a [[transcendence basis]]. | ||
**Every infinite-dimensional [[vector space]] contains an infinite linearly independent subset (this | **Every infinite-dimensional [[vector space]] contains an infinite linearly independent subset. (In ZF, this statement is logically implied by the [[axiom of countable choice]].) | ||
**[[Stone's representation theorem for Boolean algebras]] needs the [[Boolean prime ideal theorem]]. | **[[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 [[Nielsen–Schreier theorem]], that every subgroup of a free group is free. | ||
**The additive groups of '''[[real numbers|R]]''' and '''[[complex number|C]]''' are isomorphic.<ref>{{cite web|url=http://www.cs.nyu.edu/pipermail/fom/2006-February/009959.html|title=[FOM] Are (C,+) and (R,+) isomorphic|date=21 February 2006 }}</ref><ref>{{cite journal|title=A consequence of the axiom of choice|first=C. J.|last=Ash|journal=Journal of the Australian Mathematical Society|year=1975 |volume=19 |issue=3 |pages=306–308 |doi=10.1017/S1446788700031505 |s2cid=122334025 |doi-access=free}}</ref> | **The additive groups of '''[[real numbers|R]]''' and '''[[complex number|C]]''' are isomorphic.<ref>{{cite web|url=http://www.cs.nyu.edu/pipermail/fom/2006-February/009959.html|title=[FOM] Are (C,+) and (R,+) isomorphic|date=21 February 2006 }}</ref><ref>{{cite journal|title=A consequence of the axiom of choice|first=C. J.|last=Ash|journal=Journal of the Australian Mathematical Society|year=1975 |volume=19 |issue=3 |pages=306–308 |doi=10.1017/S1446788700031505 |s2cid=122334025 |doi-access=free}}</ref> | ||
*[[Metric spaces]] | |||
** In any metric space <math>X</math>, the topological and sequential definitions of an [[accumulation point]] of a subset <math>S</math> are equivalent. (In the topological definition, <math>x</math> is an accumulation point of <math>S</math> iff every neighborhood of <math>x</math> in <math>X</math> intersects <math>S-\{x\}</math>, while in the sequential definition, <math>x</math> is an accumulation point of <math>S</math> iff there exists a sequence in <math>S-\{x\}</math> that converges to <math>x</math> in <math>X</math>.) This equivalence as well as the two below equivalences require the [[axiom of countable choice]], but not the full axiom of choice. | |||
** For functions between metric spaces, the topological and sequential definitions of [[continuous function|continuity]] are equivalent. (In the topological definition, a function <math>f:X \to Y</math> is continuous at <math>x</math> iff for every neighborhood <math>V</math> of <math>f(x)</math> in <math>Y</math>, there is a neighborhood <math>U</math> of <math>x</math> in <math>X</math> such that <math>f(U)\subseteq V</math>. In the sequential definition, a function <math>f:X \to Y</math> is continuous at <math>x</math> iff for every sequence <math>\{x_n\}_{n\ge 1}</math> in <math>X</math> converging to <math>x</math>, the sequence <math>\{f(x_n)\}_{n\ge 1}</math> converges to <math>f(x)</math> in <math>Y</math>.) | |||
** For metric spaces, the topological and sequential definitions of [[compactness]] are equivalent. (In the topological definition, <math>X</math> is compact iff every collection of open subsets of <math>X</math> that covers <math>X</math> has a finite subcollection which also covers <math>X</math>. In the sequential definition, <math>X</math> is compact iff every sequence in <math>X</math> has a subsequence that converges in <math>X</math>.) | |||
*[[Functional analysis]] | *[[Functional analysis]] | ||
**The [[Hahn–Banach theorem]] in [[functional analysis]], allowing the extension of [[linear map|linear functionals]]. | **The [[Hahn–Banach theorem]] in [[functional analysis]], allowing the extension of [[linear map|linear functionals]]. | ||
| Line 249: | Line 264: | ||
**A uniform space is compact if and only if it is complete and totally bounded. | **A uniform space is compact if and only if it is complete and totally bounded. | ||
**Every [[Tychonoff space]] has a [[Stone–Čech compactification]]. | **Every [[Tychonoff space]] has a [[Stone–Čech compactification]]. | ||
**[[Urysohn's Lemma]]: For any two disjoint closed subsets <math>A</math> and <math>B</math> of a [[normal space (topology)|normal space]] <math>X</math>, and any compact interval <math>[a,b]</math> of <math>\mathbb{R}</math>, there exists a continuous map <math>f:X\to [a,b]</math> such that <math>f(A)=\{a\}</math> and <math>f(B)=\{b\}</math>. (In ZF, this statement is logically implied by the [[axiom of dependent choice]], but not by the [[axiom of countable choice]].) | |||
**[[Tietze extension theorem]]: For any closed subspace <math>A</math> of a normal space <math>X</math>, and any closed or open interval <math>I</math> of <math>\mathbb{R}</math>, and any continuous map <math>f:A\to I</math>, there exists a continuous map from <math>X</math> to <math>I</math> that extends <math>f</math>. (In ZF, this statement is logically equivalent to Urysohn's lemma.) | |||
**Existence of [[partition of unity|partitions of unity]]: For any [[paracompactness|paracompact]] [[Hausdorff space|Hausdorff]] space <math>X</math> (in particular, any manifold), and any indexed open cover <math>(U_i)_{i\in I}</math> of <math>X</math>, there exists a partition of unity of <math>X</math> subordinate to <math>(U_i)_{i\in I}</math>. | |||
*[[Mathematical logic]] | *[[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. | **[[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. | ||
**The [[compactness theorem]]: If <math>\Sigma</math> is a set of [[First-order predicate calculus|first-order]] (or alternatively, [[Propositional calculus|zero-order]]) [[Sentence (mathematical logic)|sentences]] such that every [[Finite set|finite]] subset of <math>\Sigma</math> has a [[Model (model theory)|model]], then <math>\Sigma</math> has a model.{{sfn|Schechter|1996|pp= | **The [[compactness theorem]]: If <math>\Sigma</math> is a set of [[First-order predicate calculus|first-order]] (or alternatively, [[Propositional calculus|zero-order]]) [[Sentence (mathematical logic)|sentences]] such that every [[Finite set|finite]] subset of <math>\Sigma</math> has a [[Model (model theory)|model]], then <math>\Sigma</math> has a model.{{sfn|Schechter|1996|pp=391–392}} | ||
===Possibly equivalent implications of AC=== | ===Possibly equivalent implications of AC=== | ||
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 | {{unsolved|mathematics|Does the partition principle imply the axiom of choice?}} | ||
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,<ref>{{cite journal | |||
| last1 = Banaschewski | first1 = Bernhard | |||
| last2 = Moore | first2 = Gregory H. | |||
| doi = 10.1305/ndjfl/1093635502 | |||
| issue = 3 | |||
| journal = Notre Dame Journal of Formal Logic | |||
| mr = 1072073 | |||
| pages = 375–381 | |||
| title = The dual Cantor-Bernstein theorem and the partition principle | |||
| volume = 31 | |||
| year = 1990}}</ref><ref>{{cite journal | |||
| last = Higasikawa | first = Masasi | |||
| doi = 10.1305/ndjfl/1040149358 | |||
| issue = 3 | |||
| journal = Notre Dame Journal of Formal Logic | |||
| mr = 1351415 | |||
| pages = 425–434 | |||
| title = Partition principles and infinite sums of cardinal numbers | |||
| volume = 36 | |||
| year = 1995}}</ref><ref>{{cite journal | |||
| last = Da Silva | first = Samuel G. | |||
| doi = 10.1093/jigpal/jzaa023 | |||
| issue = 5 | |||
| journal = Logic Journal of the IGPL | |||
| mr = 4316568 | |||
| pages = 783–797 | |||
| title = The axiom of choice and the partition principle from Dialectica categories | |||
| volume = 29 | |||
| year = 2021}}</ref> and the equivalences of the other statements are similarly hard old open problems. In every ''known'' model of ZF where choice fails, these statements fail too, but it is unknown whether they can hold without choice. | |||
*[[Set theory]] | *[[Set theory]] | ||
**Partition principle: if | **Partition principle: Given two sets ''A'' and ''B'', if a [[Surjective function|surjection]] exists from ''A'' to ''B'', then an [[Injective function|injection]] exists from ''B'' to ''A''. Equivalently, every [[Partition of a set|partition]] ''P'' of a set ''S'' is less than or equal to ''S'' in size. | ||
**Converse [[Schröder–Bernstein theorem]]: | **Given any two sets ''A'' and ''B'' where ''B'' is nonempty, either an [[Injective function|injection]] or a [[Surjective function|surjection]] (or both) exists from ''A'' to ''B''. | ||
**Weak partition principle: if | **Given any two nonempty sets, a [[surjective function|surjection]] exists from (at least) one of the sets to the other. | ||
**Converse [[Schröder–Bernstein theorem]]: If two sets have surjections to each other, then they have the same [[cardinality]]. | |||
**Weak partition principle: Given two sets ''A'' and ''B'', if both an [[Injective function|injection]] and a [[Surjective function|surjection]] exists from ''A'' to ''B'', then ''A'' and ''B'' have the same cardinality. Equivalently, a partition of a set ''S'' cannot be strictly larger than ''S''. If WPP holds, this already implies the existence of a non-measurable set. Each of the previous three statements is implied by the preceding one, but it is unknown if any of these implications can be reversed. | |||
**There is no infinite decreasing sequence of cardinals. The equivalence was conjectured by Schoenflies in 1905. | **There is no infinite decreasing sequence of cardinals. The equivalence was conjectured by Schoenflies in 1905. | ||
*[[Abstract algebra]] | *[[Abstract algebra]] | ||
| Line 279: | Line 328: | ||
*The real numbers are a countable union of countable sets.<ref>{{harvnb|Jech|2008|pp=142–144}}, Theorem 10.6 with proof.</ref> This does not imply that the real numbers are countable: As pointed out above, to show that a countable union of countable sets is itself countable requires the [[Axiom of countable choice]]. | *The real numbers are a countable union of countable sets.<ref>{{harvnb|Jech|2008|pp=142–144}}, Theorem 10.6 with proof.</ref> This does not imply that the real numbers are countable: As pointed out above, to show that a countable union of countable sets is itself countable requires the [[Axiom of countable choice]]. | ||
*There is a field with no algebraic closure. | *There is a field with no algebraic closure. | ||
*There is a field with two non-isomorphic algebraic closures. | |||
*In all models of ZF¬C there is a vector space with no basis. | *In all models of ZF¬C there is a vector space with no basis. | ||
*There is a vector space with two bases of different cardinalities. | *There is a vector space with two bases of different cardinalities. | ||
| Line 293: | Line 343: | ||
In [[type theory]], a different kind of statement is known as the axiom of choice. This form begins with two types, σ and τ, and a relation ''R'' between objects of type σ and objects of type τ. The axiom of choice states that if for each ''x'' of type σ there exists a ''y'' of type τ such that ''R''(''x'',''y''), then there is a function ''f'' from objects of type σ to objects of type τ such that ''R''(''x'',''f''(''x'')) holds for all ''x'' of type σ: | In [[type theory]], a different kind of statement is known as the axiom of choice. This form begins with two types, σ and τ, and a relation ''R'' between objects of type σ and objects of type τ. The axiom of choice states that if for each ''x'' of type σ there exists a ''y'' of type τ such that ''R''(''x'',''y''), then there is a function ''f'' from objects of type σ to objects of type τ such that ''R''(''x'',''f''(''x'')) holds for all ''x'' of type σ: | ||
<math display="block"> | |||
(\forall x^\sigma)(\exists y^\tau) R(x,y) \to (\exists f^{\sigma \to \tau})(\forall x^\sigma) R(x,f(x)). | (\forall x^\sigma)(\exists y^\tau) R(x,y) \to (\exists f^{\sigma \to \tau})(\forall x^\sigma) R(x,f(x)). | ||
</math> | </math> | ||
Unlike in set theory, the axiom of choice in type theory is typically stated as an [[axiom scheme]], in which ''R'' varies over all formulas or over all formulas of a particular logical form. | Unlike in set theory, the axiom of choice in type theory is typically stated as an [[axiom scheme]], in which ''R'' varies over all formulas or over all formulas of a particular logical form. | ||
| Line 339: | Line 391: | ||
| volume = 19 | | volume = 19 | ||
| year = 1972 | | year = 1972 | ||
| issue = 1–4 | |||
| pages = 339–340 | | pages = 339–340 | ||
}} | | doi = 10.5486/PMD.1972.19.1-4.37 | ||
}} | |||
* {{cite book | last=Halmos | first=Paul R. | author-link=Paul Halmos | title=Naive Set Theory | series=The University Series in Undergraduate Mathematics | publisher=van Nostrand Company |location=Princeton, NJ| year=1960 | zbl=0087.04403| title-link=Naive Set Theory (book) }} | * {{cite book | last=Halmos | first=Paul R. | author-link=Paul Halmos | title=Naive Set Theory | series=The University Series in Undergraduate Mathematics | publisher=van Nostrand Company |location=Princeton, NJ| year=1960 | zbl=0087.04403| title-link=Naive Set Theory (book) }} | ||
* {{cite book |last=Herrlich |first=Horst | author-link=Horst Herrlich |title=Axiom of Choice |publisher=[[Springer Science+Business Media|Springer-Verlag]] |location=Berlin |year=2006 |series=Lecture Notes in Math. 1876 |isbn=978-3-540-30989-5}} | * {{cite book |last=Herrlich |first=Horst | author-link=Horst Herrlich |title=Axiom of Choice |publisher=[[Springer Science+Business Media|Springer-Verlag]] |location=Berlin |year=2006 |series=Lecture Notes in Math. 1876 |isbn=978-3-540-30989-5}} | ||
| Line 363: | Line 417: | ||
| editor4-last = Stoltenberg-Hansen | | editor4-last = Stoltenberg-Hansen | ||
| year = 2008 | | year = 2008 | ||
| isbn = 1-4020-8925- | | publisher = Springer | ||
| isbn = 978-1-4020-8925-1 | |||
}} | }} | ||
* {{cite book |last=Mendelson|first=Elliott|author-link=Elliott Mendelson|title=Introduction to Mathematical Logic|year=1964|publisher=Van Nostrand Reinhold|location=New York}} | * {{cite book |last=Mendelson|first=Elliott|author-link=Elliott Mendelson|title=Introduction to Mathematical Logic|year=1964|publisher=Van Nostrand Reinhold|location=New York}} | ||
| Line 386: | Line 441: | ||
| volume = 65 | | volume = 65 | ||
| year = 1908 | | year = 1908 | ||
| issue = 2 | |||
| pages = 261–281 | | pages = 261–281 | ||
| doi = 10.1007/BF01449999 | |||
| url = https://gdz.sub.uni-goettingen.de/id/PPN235181684_0065?tify=%7B%22view%22:%22info%22,%22pages%22:%5B271%5D%7D | | url = https://gdz.sub.uni-goettingen.de/id/PPN235181684_0065?tify=%7B%22view%22:%22info%22,%22pages%22:%5B271%5D%7D | ||
| format = PDF | | format = PDF | ||
Latest revision as of 19:16, 28 May 2026
In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of non-empty sets, 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 set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} and every Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} -indexed family Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (S_i)_{i \in I}} of nonempty sets, there exists an Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} -indexed set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x_i)_{i \in I}} of elements of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cup_{i\in I}S_i} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_i \in S_i} for every Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.[1]
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 (in which induction can be applied), 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 Template:Brace}, the set containing each smallest element is {4, 10, 1}. In this case, "select the smallest number" is a choice function. Even if infinitely many sets are collected from the natural numbers, it will always be possible to form a choice function from choosing the smallest element from each set to produce a set; the axiom of choice is not needed here. On the other hand, for the collection of all non-empty subsets of the real numbers, there is no known canonical rule by which one can choose one element from each of these subsets. In that case, the axiom of choice must be invoked to construct the desired choice function.
Bertrand Russell coined an analogy: for any (even infinite) collection of unordered 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 without using the axiom of choice. However, for an infinite collection of unordered pairs of socks (assumed to have no distinguishing features such as being a left sock rather than a right sock), there is no natural (i.e., canonical) way of choosing one sock from each pair, so one must appeal to the axiom of choice to construct the desired choice function.[2]
Although originally controversial, the axiom of choice is now used without reservation by most mathematicians,[3] and is included in the standard form of axiomatic 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 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. While some varieties of constructive mathematics avoid the axiom of choice, others embrace it.
Statement
A choice function (also called selector or selection) is a function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} , defined on a collection Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} of nonempty sets, such that for every set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(A)} is an element of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} . With this concept, the axiom can be stated: Template:Math theorem
Formally, this may be expressed as follows:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall X \left[ \varnothing \in X \lor \exist f \left[ \mathrm{dom} \ f = X \land \forall A \in X \left[ f\left(A\right) \in A \right] \right] \right].}
Each choice function on a family Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} of nonempty sets is an element of the Cartesian product of the sets in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} , and vice versa. Therefore an equivalent form of the axiom of choice is:
The Cartesian product of any collection of nonempty sets is nonempty.
This form implies a more general form where the Cartesian product is of a general indexed family of sets (which may contain duplicates), since one can always select the same element from duplicate factors.
Nomenclature
In this article and other discussions of the axiom of choice the following abbreviations are common:
- AC – the axiom of choice. More rarely, AoC is used.[4]
- ZF – Zermelo–Fraenkel set theory omitting the axiom of choice.
- ZFC – 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X}
, if the empty set is not an element of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X}
and the elements of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X}
are pairwise disjoint, then there exists a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C}
such that its intersection with any of the elements of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X}
contains exactly one element.[5]
This can be formalized in first-order logic as:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{align} \forall x (& \\ &\exists e (e \in x \and \lnot\exists y (y \in e)) \or \\ &\exists a \, \exists b \, \exists c \, (a \in x \and b \in x \and c \in a \and c \in b \and \lnot(a = b)) \or \\ &\exists c \, \forall e \, (e \in x \implies \exists a \, (a \in e \and a \in c \and \forall b \, ((b \in e \and b \in c) \implies a = b)))) \end{align} }
Note that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P \or Q \or R} is logically equivalent to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\lnot P \and \lnot Q) \implies R} . In English, this first-order sentence reads:
Given any set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X}
,
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X}
contains the empty set as an element or
the elements of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X}
are not pairwise disjoint or
there exists a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C}
such that its intersection with any of the elements of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X}
contains exactly one element.
This guarantees for any partition of a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} the existence of a subset Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C} of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} containing exactly one element from each part of the partition.
Another equivalent axiom only considers collections Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} that are essentially powersets of other sets:
For any set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A}
, the power set of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A}
(with the empty set removed) has a choice function.
Authors who use this formulation often speak of the choice function on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , but this is a slightly different notion of choice function. Its domain is the power set of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} (with the empty set removed), and so makes sense for any set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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.[6]
which is equivalent to
For any set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A}
there is a function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f:\mathcal P(A)\setminus\{ \emptyset \} \to A }
such that for any non-empty subset Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B}
of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A}
, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(B)}
lies in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B}
.
The negation of the axiom can thus be expressed as:
There is a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A}
such that for all functions Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f}
(on the set of non-empty subsets of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A}
), there is a subset Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B}
such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(B)}
does not lie in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B}
.
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" to define a function F. In general, it is impossible to prove that F exists without the axiom of choice, but this seems to have gone unnoticed until Zermelo.
Examples
Cases where the axiom of choice is not needed
The existence of a choice function for a finite collection of nonempty sets can be proved by the principle of finite induction, without appealing to the axiom of choice.[7] The proof uses the fact that, given a single nonempty set Template:Tmath, first-order logic allows choosing some concrete Template:Tmath. However, since a proof in first-order logic must be finite, one cannot make an infinite number of choices with first-order logic alone.
Another case where the axiom of choice is not needed is when there exists an explicit rule that gives a canonical choice function. For example, if each member of the collection Template:Tmath is a nonempty subset of the natural numbers, then one such explicit rule is to choose the smallest element of each Template:Tmath. The canonical choice function that maps each Template:Tmath to its smallest element can again be constructed in ZF without the axiom of choice.
In general, if the union of all sets in Template:Tmath can be well-ordered, then a choice function for Template:Tmath can be constructed without using the axiom of choice. Note that it does not suffice that each Template:Tmath can be well-ordered, since the axiom of choice may be needed to choose a canonical well-ordering for each Template:Tmath anyway.
Real numbers
As an example where the axiom of choice is required, let Template:Tmath be set of all non-empty subsets of the real numbers. Choosing the least element from each set no longer works, because some subsets of the real numbers do not have least elements. For example, the open interval Template:Tmath does not have a least element: if Template:Tmath is in Template:Tmath, then so is Template:Tmath, and Template:Tmath is always strictly smaller than Template:Tmath. This strategy fails here because the natural order of real numbers is not a well-order.
If there exists a different ordering of the real numbers which is a well-ordering, then applying the least-element strategy with respect to that ordering would give a choice function for Template:Tmath. Conversely, if there exists a choice function for Template:Tmath, then the proof of the well-ordering theorem would show that a well-ordering of the real numbers does exist.
Constructing a non-measurable set
Let Template:Tmath be the unit circle, and Template:Tmath be the group consisting of all rational rotations (i.e., rotations by angles which are rational multiples of Template:Tmath). Since Template:Tmath is countable while Template:Tmath is uncountable, Template:Tmath must break up into uncountably many orbits under the action of Template:Tmath.
Using the axiom of choice, we could pick a single point from each orbit, obtaining an uncountable subset Template:Tmath of Template:Tmath with the property that all of its translates by Template:Tmath are disjoint from Template:Tmath. The set of those translates partitions the circle into a countable collection of pairwise disjoint sets, which are all pairwise congruent. The set Template:Tmath will be non-measurable for any rotation-invariant countably additive measure on Template:Tmath: if Template:Tmath has zero measure, countable additivity would imply that the whole circle has zero measure. If Template:Tmath has positive measure, countable additivity would show that the circle has infinite measure.
Applying a similar construction to the three-dimensional ball can result in a set that is non-measurable even for any rotation-invariant finitely additive measure, as shown by the Banach–Tarski paradox.
Criticism and acceptance
A proof requiring the axiom of choice may establish the existence of an object without canonically 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 individual well-ordering of the reals is definable. Similarly, although a subset of the real numbers that is not Lebesgue measurable can be proved to exist using the axiom of choice, it is consistent that no such set is definable.[8]
The axiom of choice asserts the existence of these intangibles (objects that are proved to exist, but which cannot be constructed in any canonical way), which may conflict with some philosophical principles.[9] Because there is no 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 objects that may seem counterintuitive.[10] One example is the Banach–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, are non-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) is 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 that requires the axiom of choice to be true.
Theorems of ZF hold true in any model 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.
In constructive mathematics
As discussed above, in the classical theory of ZFC, the axiom of choice enables nonconstructive proofs in which the existence of a type of object is proved without an explicit canonical construction of an instance of this type. In fact, in set theory and topos theory, Diaconescu's theorem shows that the axiom of choice implies the law of excluded middle. The principle is thus not available in constructive set theory, where non-classical logic is employed.
The situation is different when the principle is formulated in Martin-Löf type theory. There 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.[11] 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.[12] 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 the axiom of countable choice or the axiom of dependent choice, which do not imply the law of the excluded middle. Errett Bishop, who is notable for developing a framework for constructive 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.[13]
Although the axiom of countable choice in particular is commonly used in constructive mathematics, its use has also been questioned.[14]
Independence
It has been known since as early as 1922 that the axiom of choice may fail in a variant of ZF with urelements, through the technique of permutation models introduced by Abraham Fraenkel[15] and developed further by Andrzej Mostowski.[16] The basic technique can be illustrated as follows: Let xn and yn be distinct urelements for n=1, 2, 3..., and build a model where each set is symmetric under the interchange xn ↔ yn for all but a finite number of n. Then the set X = {{x1, y1}, {x2, y2}, {x3, y3}, ...} can be in the model but sets such as {x1, x2, x3, ...} cannot, and thus X cannot have a choice function.
In 1938,[17] 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) that satisfies ZFC, thus showing that ZFC is consistent if ZF itself is consistent. In 1963, Paul Cohen employed the technique of forcing, 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 a symmetric model, which is similar to permutation models, but uses "generic" subsets of the natural numbers (justified by forcing) in place of urelements.[18]
Together these results establish that the axiom of choice is 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 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 nontrivial unital ring has a maximal ideal, every vector space has a basis, every connected graph has a spanning tree, and every product of compact 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 of Peano arithmetic, are provable in ZF if and only if they are provable in ZFC.[19] Statements in this class include the statement that P = NP, the Riemann 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, the 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 and the generalized continuum hypothesis each imply the axiom of choice and are strictly stronger than it. In class theories such as Von Neumann–Bernays–Gödel set theory and Morse–Kelley set theory, there is an axiom called the axiom 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 the axiom of limitation of size. Tarski's axiom, which is used in Tarski–Grothendieck set theory and states (in the vernacular) that every set belongs to some Grothendieck universe, is stronger than the axiom of choice.
Equivalents
There are important statements that, assuming the axioms of ZF but neither AC nor ¬AC, are equivalent to the axiom of choice (that is, their truth values in ZF, while undecidable, are the same as that of AC).[20] 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
- Trichotomy: The cardinalities of any two sets are comparable with each other. That is, given any two sets, an injection exists from (at least) one of the sets to the other.
- Tarski's theorem about choice: For every infinite set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , the sets Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A\times A} have the same cardinality; i.e., there exists a bijection between them.
- Every surjection Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f:S\to T} has a right inverse; i.e., there exists a function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g:T\to S} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\circ g = \mathrm{id}_T} .
- For every disjoint collection Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{C}} of nonempty sets, there exists a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle C\subseteq\cup_{S \in \mathcal{C}}(S)} that intersects each member of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{C}} in exactly one element. That is, every partition of a set has a transversal.[21]
- If a relation Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R} from a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} to a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y} has the property that for every Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in X} , there is a Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y \in Y} with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x R y} , then there exists a function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f:X\to Y} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x R f(x)} for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\in X} .
- The Cartesian product of any indexed family of nonempty sets is nonempty. That is, for any set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} , and any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} -indexed family Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (S_i)_{i\in I}} of nonempty sets, there exists an Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} -indexed set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (s_i)_{i\in I}} of elements in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cup_{i\in I}(S_i)} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s_i\in S_i} for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i \in I} .
- In any collection Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} of nonempty sets, there exists a disjoint subcollection Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{C}} of sets whose union Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cup_{S\in\mathcal{C}}(S)} intersects all the members of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} . (Note that such a disjoint subcollection is precisely one that is maximal with respect to set inclusion.)
- For any set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} , there exists a maximal (under set inclusion) collection Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} of subsets of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} for which every finite subcollection Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{C}} of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} has a nonempty intersection Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cap_{S\in\mathcal{C}}(S)} . (This statement is key to a standard proof of Tychonoff's theorem.)
- Well-ordering theorem: Every set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} has a well-ordering (i.e., a total ordering in which every nonempty subset of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} has a minimum element). Consequently, every cardinal has an initial ordinal.
- For every ordinal Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} , the powerset (i.e., the set of all subsets) of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} has a well-ordering.
- Hausdorff maximal principle: Every partially ordered set has a maximal chain (with respect to inclusion). Equivalently, in a partially ordered set, every chain can be extended to a maximal chain.
- Antichain principle: Every partially ordered set has a maximal antichain (with respect to inclusion). Equivalently, in any partially ordered set, every antichain can be extended to a maximal antichain.
- Zorn's lemma: If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A,<)} is any partially ordered set in which every chain has an upper bound in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A,<)} has at least one maximal element.
- Kuratowski's lemma: If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} is any family of sets with the property that for any subfamily Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{C}} of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} totally ordered by set inclusion, the union Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \cup_{A\in\mathcal{C}}(A)} is an element of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} has at least one element maximal with respect to inclusion.
- Tukey's lemma: If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} is any family of subsets of a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} with the property that a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B\subseteq X} is an element of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} iff every finite subset of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} is an element of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{A}} has at least one element maximal with respect to inclusion.
- König's theorem: Informally, the sum of a sequence of cardinals is strictly less than the product of a sequence of larger cardinals. (The reason for the term "informally" is that the sum or product of a "sequence" of cardinals cannot itself be defined without some aspect of the axiom of choice.)
- Abstract algebra
- Every vector space has a basis; equivalently, every linearly independent subset of a vector space can be extended to a basis, while every spanning subset contains a basis. In the language of module theory, all vector spaces are free modules.[22]Template:Verification needed
- Krull's theorem: Every nontrivial unital ring contains a maximal ideal; equivalently, every proper ideal of a unital ring can be extended to a maximal ideal.
- For every non-empty set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} there is a binary operation defined on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} that gives it a group structure.[23] (A cancellative binary operation is enough; see Group structure and the axiom of choice.)
- Every free abelian group is projective.[24]
- Baer's criterion: Every divisible abelian group is injective.[24]
- Every set is a projective object in the category of sets.[25][26]
- 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: The product of any indexed family of compact topological spaces is compact.
- The closure of the product of any indexed family of subsets of a topological space is equal to the product of the closures of those subsets.
- Mathematical logic
- If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} is a set of sentences of first-order logic and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} is a consistent subset of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} is included in a set that is maximal among consistent subsets of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} . The special case where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} is the set of all first-order sentences in a given signature is weaker, equivalent to the Boolean prime ideal theorem; see the section "Weaker forms" below.
- Löwenheim–Skolem theorem: If a first-order theory has an infinite model, then it has an infinite model of every possible cardinality greater than or equal to the cardinality of the language of this theory.
- Graph theory
- Every connected graph has a spanning tree; equivalently, every tree in a connected graph can be extended to a spanning tree, while every spanning subgraph contains a spanning tree.[27][28]
Category theory
Several results in category 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 a small category), then there is no 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 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).
Weaker forms
There are several weaker statements unprovable in ZF that are logically implied by the axiom of choice (AC) within ZF but are not equivalent to AC. One example is the axiom of dependent choice (DC). A still weaker example is the axiom of countable choice (ACω or CC), which states that a choice function exists for any countable family 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 subsets of real numbers, that are disprovable from the full axiom of choice.
Given an ordinal parameter α ≥ ω+2 – for every set S with rank less than α, S is well-orderable. Given an ordinal parameter α ≥ 1 – for every set S with Hartogs 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 the Boolean prime ideal theorem and the axiom of uniformization. The former is equivalent in ZF to Tarski's 1930 ultrafilter lemma: every filter is a subset of some ultrafilter.
Results requiring AC (or weaker forms) but weaker than it
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.
- Set theory
- Axiom of countable choice: The Cartesian product of any sequence (i.e., countable indexed family) of nonempty sets is nonempty. (This is just the axiom of choice with the indexing set restricted to countable size.)
- Axiom of dependent choice: If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R } is any relation on a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S } with the property that for every Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x \in S } , there is a Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y \in S } with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x R y } , then, for every Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x\in S} , there exists a sequence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left(x_n\right)_{n \in \mathbb{N}}} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} starting at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} and satisfying Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_n R x_{n+1} } for all Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \in \mathbb{N}} . (In ZF, this statement logically implies the axiom of countable choice, and is strictly stronger.)
- Axiom of choice for finite sets: The Cartesian product of any indexed family of non-empty finite sets is nonempty. (Note that here, it is each member of the indexed family that is restricted in size, not the indexing set, in contrast with countable choice.)
- Ultrafilter lemma: Every filter on a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} can be extended to an ultrafilter on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} . (In ZF, this statement logically implies the Axiom of choice for finite sets (above)[29].)
- The union of any countable family of countable sets is countable. (In ZF, this statement is logically implied by the axiom of countable choice.)
- Every infinite set has a countable-infinite subset, i.e., has cardinality greater than or equal to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \aleph_0} . (In ZF, this statement is logically implied by the axiom of countable choice but is not equivalent; see Dedekind infinite.)[30]
- Eight definitions of a finite set are equivalent.[31]
- Every infinite game Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_S} in which Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} is a Borel subset of Baire space is determined.
- Every infinite cardinal Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \kappa} satisfies Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\kappa=\kappa} .[32]
- Measure theory
- The Vitali theorem: There exist subsets of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}^n} (for any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n>0} ) that are not Lebesgue measurable; i.e., the set of all subsets of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}^n} does not form a measure space of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}^n} under the standard (Lebesgue) outer-measure.
- There exist Lebesgue-measurable subsets of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}^n} that are not Borel sets; i.e., the Borel Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma} -algebra on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}^n} is strictly contained in the Lebesgue-measure Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma} -algebra on Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}^n} .
- The Hausdorff paradox.
- The Banach–Tarski paradox.
- Abstract algebra
- Every field has an algebraic closure.
- Every field extension has a transcendence basis.
- Every infinite-dimensional vector space contains an infinite linearly independent subset. (In ZF, this statement is logically implied by the axiom of countable choice.)
- 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.[33][34]
- Metric spaces
- In any metric space Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} , the topological and sequential definitions of an accumulation point of a subset Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} are equivalent. (In the topological definition, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} is an accumulation point of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} iff every neighborhood of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} intersects Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S-\{x\}} , while in the sequential definition, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} is an accumulation point of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} iff there exists a sequence in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S-\{x\}} that converges to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} .) This equivalence as well as the two below equivalences require the axiom of countable choice, but not the full axiom of choice.
- For functions between metric spaces, the topological and sequential definitions of continuity are equivalent. (In the topological definition, a function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f:X \to Y} is continuous at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} iff for every neighborhood Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y} , there is a neighborhood Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle U} of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(U)\subseteq V} . In the sequential definition, a function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f:X \to Y} is continuous at Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} iff for every sequence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{x_n\}_{n\ge 1}} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} converging to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} , the sequence Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{f(x_n)\}_{n\ge 1}} converges to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y} .)
- For metric spaces, the topological and sequential definitions of compactness are equivalent. (In the topological definition, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} is compact iff every collection of open subsets of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} that covers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} has a finite subcollection which also covers Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} . In the sequential definition, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} is compact iff every sequence in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} has a subsequence that converges in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} .)
- 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.
- Urysohn's Lemma: For any two disjoint closed subsets Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B} of a normal space Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} , and any compact interval Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [a,b]} of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}} , there exists a continuous map Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f:X\to [a,b]} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(A)=\{a\}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(B)=\{b\}} . (In ZF, this statement is logically implied by the axiom of dependent choice, but not by the axiom of countable choice.)
- Tietze extension theorem: For any closed subspace Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} of a normal space Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} , and any closed or open interval Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}} , and any continuous map Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f:A\to I} , there exists a continuous map from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I} that extends Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f} . (In ZF, this statement is logically equivalent to Urysohn's lemma.)
- Existence of partitions of unity: For any paracompact Hausdorff space Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} (in particular, any manifold), and any indexed open cover Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (U_i)_{i\in I}} of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} , there exists a partition of unity of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} subordinate to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (U_i)_{i\in I}} .
- 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.
- The compactness theorem: If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma} is a set of first-order (or alternatively, zero-order) sentences such that every finite subset of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma} has a model, then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Sigma} has a model.[35]
Possibly equivalent implications of AC
Template:Unsolved 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,[36][37][38] and the equivalences of the other statements are similarly hard old open problems. In every known model of ZF where choice fails, these statements fail too, but it is unknown whether they can hold without choice.
- Set theory
- Partition principle: Given two sets A and B, if a surjection exists from A to B, then an injection exists from B to A. Equivalently, every partition P of a set S is less than or equal to S in size.
- Given any two sets A and B where B is nonempty, either an injection or a surjection (or both) exists from A to B.
- Given any two nonempty sets, a surjection exists from (at least) one of the sets to the other.
- Converse Schröder–Bernstein theorem: If two sets have surjections to each other, then they have the same cardinality.
- Weak partition principle: Given two sets A and B, if both an injection and a surjection exists from A to B, then A and B have the same cardinality. Equivalently, a partition of a set S cannot be strictly larger than S. If WPP holds, this already implies the existence of a non-measurable set. Each of the previous three statements is implied by the preceding one, but it is unknown if any of these implications can be reversed.
- There is no infinite decreasing sequence of cardinals. The equivalence was conjectured by Schoenflies in 1905.
- Abstract algebra
- Hahn embedding theorem: Every ordered abelian group G order-embeds as a subgroup of the additive group Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{R}^\Omega} endowed with a lexicographical order, where Ω is the set of Archimedean equivalence classes of G. This equivalence was conjectured by Hahn in 1907.
Stronger forms of the negation of AC
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. Strengthened negations may be compatible with weakened forms of AC. For example, ZF + DC[39] + BP is consistent, if ZF is.
It is also consistent with ZF + DC that every set of reals is Lebesgue measurable, but 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).
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.[40]
Statements implying the negation of AC
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.
- The negation of the weak partition principle: There is a set that can be partitioned into strictly more equivalence classes than the original set has elements, and a function whose domain is strictly smaller than its range. In fact, this is the case in all known models.
- There is a function f from the real numbers to the real numbers such that f is not continuous at a, but f is sequentially continuous at a, i.e., for any sequence {xn} converging to a, limn f(xn)=f(a).
- There is an infinite set of real numbers without a countably infinite subset.
- The real numbers are a countable union of countable sets.[41] This does not imply that the real numbers are countable: As pointed out above, to show that a countable union of countable sets is itself countable requires the Axiom of countable choice.
- There is a field with no algebraic closure.
- There is a field with two non-isomorphic algebraic closures.
- In all models of ZF¬C there is a vector space with no basis.
- There is a vector space with two bases of different cardinalities.
- There is a free complete Boolean algebra on countably many generators.[42]
- There is a set that cannot be linearly ordered.
- There exists a model of ZF¬C in which every set in Rn 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.
For proofs, see Jech (2008).
Additionally, by imposing definability conditions on sets (in the sense of descriptive set theory) one can often prove restricted versions of the axiom of choice from axioms incompatible with general choice. This appears, for example, in the Moschovakis coding lemma.
Axiom of choice in type theory
In type theory, a different kind of statement is known as the axiom of choice. This form begins with two types, σ and τ, and a relation R between objects of type σ and objects of type τ. The axiom of choice states that if for each x of type σ there exists a y of type τ such that R(x,y), then there is a function f from objects of type σ to objects of type τ such that R(x,f(x)) holds for all x of type σ:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\forall x^\sigma)(\exists y^\tau) R(x,y) \to (\exists f^{\sigma \to \tau})(\forall x^\sigma) R(x,f(x)). }
Unlike in set theory, the axiom of choice in type theory is typically stated as an axiom scheme, in which R varies over all formulas or over all formulas of a particular logical form.
Notes
- ↑ Zermelo 1904.
- ↑ Jech 1977, p. 351.
- ↑ Jech 1977, p. 348 ff; Mac Lane 1986, pp. 366–367; Martin-Löf 2008, p. 210. According to Mendelson 1964, p. 201: "The status of the Axiom of Choice has become less controversial in recent years. To most mathematicians it seems quite plausible and it has so many important applications in practically all branches of mathematics that not to accept it would seem to be a wilful hobbling of the practicing mathematician."
- ↑ Rosenberg 2021.
- ↑ Herrlich 2006, p. 9. According to Suppes 1972, p. 243, this was the formulation of the axiom of choice which was originally given by Zermelo 1904. See also Halmos 1960, p. 60 for this formulation.
- ↑ Suppes 1972, p. 240.
- ↑ Tourlakis 2003, pp. 209–210, 215–216.
- ↑ Fraenkel, Bar-Hillel & Lévy 1973, pp. 69–70.
- ↑ Rosenbloom 2005, p. 147.
- ↑ Dawson 2006: "The axiom of choice, though it had been employed unconsciously in many arguments in analysis, became controversial once made explicit, not only because of its non-constructive character, but because it implied such extremely unintuitive consequences as the Banach–Tarski paradox."
- ↑ Per Martin-Löf, Intuitionistic type theory, 1980. Anne Sjerp Troelstra, Metamathematical investigation of intuitionistic arithmetic and analysis, Springer, 1973.
- ↑ Martin-Löf, Per (2006). "100 Years of Zermelo's Axiom of Choice: What was the Problem with It?". The Computer Journal. 49 (3): 345–350. Bibcode:1980CompJ..23..262L. doi:10.1093/comjnl/bxh162.
- ↑ Errett Bishop and Douglas S. Bridges, Constructive analysis, Springer-Verlag, 1985.
- ↑ 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.
- ↑ Fraenkel 1922.
- ↑ Mostowski 1938.
- ↑ Gödel, Kurt (9 November 1938). "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis". Proceedings of the National Academy of Sciences of the United States of America. 24 (12): 556–557. Bibcode:1938PNAS...24..556G. doi:10.1073/pnas.24.12.556. PMC 1077160. PMID 16577857.
- ↑ Cohen, Paul (2019). "The Independence of the Axiom of Choice" (PDF). Stanford University Libraries. Archived (PDF) from the original on 9 October 2022. Retrieved 22 March 2019.
- ↑ This is because arithmetical statements are absolute to the constructible universe L. Shoenfield's absoluteness theorem gives a more general result.
- ↑ See Moore 2013, pp. 330–334, for a structured list of 74 equivalents. See Howard & Rubin 1998, pp. 11–16, for 86 equivalents with source references.
- ↑ John, Bell (10 December 2021). "The Axiom of Choice". Stanford Encyclopedia of Philosophy. Retrieved 2 December 2024.
Let us call Zermelo's 1908 formulation the combinatorial axiom of choice: CAC: Any collection of mutually disjoint nonempty sets has a transversal.
- ↑ Blass, Andreas (1984) [1983]. "Existence of bases implies the axiom of choice". Written at Providence, Rhode Island. Axiomatic set theory. Contemporary Mathematics. 31. Boulder, Colorado: American Mathematical Society. pp. 31–33. doi:10.1090/conm/031/763890. ISBN 978-0-8218-5026-8. MR 0763890.
- ↑ Hajnal & Kertész 1972, see also Rubin & Rubin 1985, p. 111.
- ↑ 24.0 24.1 Blass 1979.
- ↑ Awodey, Steve (2010). Category theory (2nd ed.). Oxford: Oxford University Press. pp. 20–24. ISBN 978-0199237180. OCLC 740446073.
- ↑ Template:Nlab
- ↑ Serre, Jean-Pierre (2003). Trees. Springer Monographs in Mathematics. Springer. p. 23.
- ↑ Soukup, Lajos (2008). "Infinite combinatorics: from finite to infinite". Horizons of combinatorics. Bolyai Society Mathematical Studies. 17. Berlin: Springer. pp. 189–213. CiteSeerX 10.1.1.222.5699. doi:10.1007/978-3-540-77200-2_10. ISBN 978-3-540-77199-9. MR 2432534. See in particular Theorem 2.1, pp. 192–193.
- ↑ Muger, Michael (2020). Topology for the Working Mathematician.
- ↑ It is shown by Jech 2008, pp. 119–131, that the axiom of countable choice implies the equivalence of infinite and Dedekind-infinite sets, but that the equivalence of infinite and Dedekind-infinite sets does not imply the axiom of countable choice in ZF.
- ↑ It was shown by Lévy 1958 and others using Mostowski models that eight definitions of a finite set are independent in ZF without AC, although they are equivalent when AC is assumed. The definitions are I-finite, Ia-finite, II-finite, III-finite, IV-finite, V-finite, VI-finite and VII-finite. I-finiteness is the same as normal finiteness. IV-finiteness is the same as Dedekind-finiteness.
- ↑ Sageev, Gershon (March 1975). "An independence result concerning the axiom of choice". Annals of Mathematical Logic. 8 (1–2): 1–184. doi:10.1016/0003-4843(75)90002-9.
- ↑ "[FOM] Are (C,+) and (R,+) isomorphic". 21 February 2006.
- ↑ Ash, C. J. (1975). "A consequence of the axiom of choice". Journal of the Australian Mathematical Society. 19 (3): 306–308. doi:10.1017/S1446788700031505. S2CID 122334025.
- ↑ Schechter 1996, pp. 391–392.
- ↑ Banaschewski, Bernhard; Moore, Gregory H. (1990). "The dual Cantor-Bernstein theorem and the partition principle". Notre Dame Journal of Formal Logic. 31 (3): 375–381. doi:10.1305/ndjfl/1093635502. MR 1072073.
- ↑ Higasikawa, Masasi (1995). "Partition principles and infinite sums of cardinal numbers". Notre Dame Journal of Formal Logic. 36 (3): 425–434. doi:10.1305/ndjfl/1040149358. MR 1351415.
- ↑ Da Silva, Samuel G. (2021). "The axiom of choice and the partition principle from Dialectica categories". Logic Journal of the IGPL. 29 (5): 783–797. doi:10.1093/jigpal/jzaa023. MR 4316568.
- ↑ Axiom of dependent choice
- ↑ "Quine's New Foundations". Stanford Encyclopedia of Philosophy. Retrieved 10 November 2017.
- ↑ Jech 2008, pp. 142–144, Theorem 10.6 with proof.
- ↑ Stavi, Jonathan (1974). "A model of ZF with an infinite free complete Boolean algebra". Israel Journal of Mathematics. 20 (2): 149–163. doi:10.1007/BF02757883. S2CID 119543439.
References
- Blass, Andreas (1979). "Injectivity, Projectivity and the Axiom of Choice". Transactions of the American Mathematical Society. 255: 31–59. doi:10.2307/1998165. JSTOR 1998165.
- Dawson, J. W. (August 2006). "Shaken Foundations or Groundbreaking Realignment? A Centennial Assessment of Kurt Gödel's Impact on Logic, Mathematics, and Computer Science". Proceedings of the 21st Annual IEEE Symposium on Logic in Computer Science (LICS 2006). pp. 339–341. doi:10.1109/LICS.2006.47. ISBN 978-0-7695-2631-7. S2CID 15526447.
- Fraenkel, Abraham (1922), "Der Begriff "definit" und die Unabhängigkeit des Auswahlaxioms", Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften: 253–257, JFM 48.0199.02
- Fraenkel, Abraham A.; Bar-Hillel, Yehoshua; Lévy, Azriel (1973). Foundations of set theory (2nd ed.). Amsterdam-London: North-Holland Publishing Co. pp. 69–70. ISBN 9780080887050. MR 0345816.
- Hajnal, A.; Kertész, A. (1972). "Some new algebraic equivalents of the axiom of choice". Publ. Math. Debrecen. 19 (1–4): 339–340. doi:10.5486/PMD.1972.19.1-4.37.
- Halmos, Paul R. (1960). Naive Set Theory. The University Series in Undergraduate Mathematics. Princeton, NJ: van Nostrand Company. Zbl 0087.04403.
- Herrlich, Horst (2006). Axiom of Choice. Lecture Notes in Math. 1876. Berlin: Springer-Verlag. ISBN 978-3-540-30989-5.
- Howard, Paul; Rubin, Jean E. (1998), Consequences of the axiom of choice, Mathematical Surveys and Monographs, 59, Providence, Rhode Island: American Mathematical Society, ISBN 9780821809778
- Jech, Thomas (2008) [1973]. The axiom of choice. Mineola, New York: Dover Publications. ISBN 978-0-486-46624-8.
- Jech, Thomas (1977). "About the Axiom of Choice". In John Barwise (ed.). Handbook of Mathematical Logic.
- Lévy, Azriel (1958). "The independence of various definitions of finiteness" (PDF). Fundamenta Mathematicae. 46: 1–13. doi:10.4064/fm-46-1-1-13. Archived (PDF) from the original on 9 October 2022.
- Mac Lane, Saunders (1986). Mathematics, Form and Function. Springer-Verlag. ISBN 0-387-96217-4.
- Martin-Löf, Per (2008). "100 years of Zermelo's axiom of choice: What was the problem with it?". In Lindström, Sten; Palmgren, Erik; Segerberg, Krister; Stoltenberg-Hansen, Viggo (eds.). Logicism, Intuitionism, and Formalism: What Has Become of Them?. Springer. ISBN 978-1-4020-8925-1.
- Mendelson, Elliott (1964). Introduction to Mathematical Logic. New York: Van Nostrand Reinhold.
- Moore, Gregory H. (1982). Zermelo's axiom of choice, Its origins, development and influence. Springer. ISBN 978-0-387-90670-6., available as a Dover Publications reprint, 2013, ISBN 0-486-48841-1.
- Mostowski, Andrzej (1938), "Über den Begriff einer Endlichen Menge", Comptes Rendus des Séances de la Société des Sciences et des Lettres de Varsovie, Classe III, 31 (8): 13–20
- Moore, Gregory H (2013) [1982]. Zermelo's axiom of choice: Its origins, development & influence. Mineola, New York: Dover Publications. ISBN 978-0-486-48841-7.
- Rosenberg, Steven (21 December 2021). An Invitation to Abstract Algebra. CRC Press. ISBN 9781000516333.
- Rosenbloom, Paul C. (2005). The Elements of Mathematical Logic. Courier Dover Publications. ISBN 9780486446172.
- Rubin, Herman; Rubin, Jean E. (April 1970) [1963]. Equivalents of the Axiom of Choice (2nd print ed.). North Holland / Elsevier. ISBN 9780720422252.
- Rubin, Herman; Rubin, Jean E. (July 1985). Equivalents of the Axiom of Choice II. North Holland / Elsevier. ISBN 0-444-87708-8.
- Russell, Bertrand (1993) [1919]. Introduction to mathematical philosophy. New York: Dover Publications. ISBN 978-0-486-27724-0.
- Template:Schechter Handbook of Analysis and Its Foundations
- Suppes, Patrick (1972) [1960]. Axiomatic set theory. Mineola, New York: Dover. ISBN 978-0-486-61630-8.
- Tourlakis, George (2003). Lectures in Logic and Set Theory. Vol. II: Set Theory. Cambridge University Press. ISBN 0-511-06659-7.
- Zermelo, Ernst (1904). "Beweis, dass jede Menge wohlgeordnet werden kann" (reprint). Mathematische Annalen. 59 (4): 514–16. doi:10.1007/BF01445300. S2CID 124189935.
- Zermelo, Ernst (1908). "Untersuchungen über die Grundlagen der Mengenlehre I" (PDF). Mathematische Annalen. 65 (2): 261–281. doi:10.1007/BF01449999. Retrieved 15 May 2025.
- 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.
- 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
External links
| File:Wikiquote-logo.svg | Wikiquote has quotations related to: Axiom of choice |
- Axiom of Choice entry in the Springer Encyclopedia of Mathematics.
- Axiom of Choice and Its Equivalents entry 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 Archived 15 May 2021 at the Wayback Machine, based on the book by Paul Howard Archived 26 February 2021 at the Wayback Machine and Jean Rubin.
- Template:SEP.