Axiom of choice

A choice function (also called selector or selection) is a function f, defined on a collection X of nonempty sets, such that for every set A in X, f(A) is an element of A. With this concept, the axiom can be stated:

Formally, this may be expressed as follows:

${\displaystyle \forall X\left[\varnothing \notin X\implies \exists f\colon X\rightarrow \bigcup X\quad \forall A\in X\,(f(A)\in A)\right]\,.}$

Thus, the negation of the axiom of choice states that there exists a collection of nonempty sets that has no choice function. (${\displaystyle p\rightarrow q\Longleftrightarrow \lnot [p\land (\lnot q)]}$, so ${\displaystyle \lnot (p\rightarrow q)\Longleftrightarrow p\land (\lnot q)}$ where ${\displaystyle \lnot }$ is negation.)

Each choice function on a collection X of nonempty sets is an element of the Cartesian product of the sets in X. This is not the most general situation of a Cartesian product of a family of sets, where a given set can occur more than once as a factor; however, one can focus on elements of such a product that select the same element every time a given set appears as factor, and such elements correspond to an element of the Cartesian product of all distinct sets in the family. The axiom of choice asserts the existence of such elements; it is therefore equivalent to:

Given any family of nonempty sets, their Cartesian product is a nonempty set.

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.

The nature of the individual nonempty sets in the collection may make it possible to avoid the axiom of choice even for certain infinite collections. For example, suppose that each member of the collection X is a nonempty subset of the natural numbers. Every such subset has a smallest element, so to specify our choice function we can simply say that it maps each set to the least element of that set. This gives us a definite choice of an element from each set, and makes it unnecessary to add the axiom of choice to our axioms of set theory.

The difficulty appears when there is no natural choice of elements from each set. If we cannot make explicit choices, how do we know that our selection forms a legitimate set (as defined by the other ZF axioms of set theory)? For example, suppose that X is the set of all non-empty subsets of the real numbers. First we might try to proceed as if X were finite. If we try to choose an element from each set, then, because X is infinite, our choice procedure will never come to an end, and consequently, we shall never be able to produce a choice function for all of X. Next we might try specifying the least element from each set. But some subsets of the real numbers do not have least elements. For example, the open interval (0,1) does not have a least element: if x is in (0,1), then so is x/2, and x/2 is always strictly smaller than x. So this attempt also fails.

Additionally, consider for instance the unit circle S, and the action on S by a group G consisting of all rational rotations. Namely, these are rotations by angles which are rational multiples of π. Here G is countable while S is uncountable. Hence S breaks up into uncountably many orbits under G. Using the axiom of choice, we could pick a single point from each orbit, obtaining an uncountable subset X of S with the property that all of its translates by G are disjoint from X. The set of those translates partitions the circle into a countable collection of disjoint sets, which are all pairwise congruent. Since X is not measurable for any rotation-invariant countably additive finite measure on S, finding an algorithm to form a set from selecting a point in each orbit requires that one add the axiom of choice to our axioms of set theory. See non-measurable set for more details.

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

A proof requiring the axiom of choice may establish the existence of an object without explicitly defining the object in the language of set theory. For example, while the axiom of choice implies that there is a well-ordering of the real numbers, there are models of set theory with the axiom of choice in which no well-ordering of the reals is definable. Similarly, although a subset of the real numbers that is not Lebesgue measurable can be proved to exist using the axiom of choice, it is consistent that no such set is definable.[7]

The axiom of choice proves the existence of these intangibles (objects that are proved to exist, but which cannot be explicitly constructed), which may conflict with some philosophical principles.[8] 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.[9] 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 facts, most mathematicians accept the axiom of choice as a valid principle for proving new results in mathematics. The debate is interesting enough, however, that it is considered of note when a theorem in ZFC (ZF plus AC) is logically equivalent (with just the ZF axioms) to the axiom of choice, and mathematicians look for results that require the axiom of choice to be false, though this type of deduction is less common than the type which requires the axiom of choice to be true.

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

As discussed above, in ZFC, the axiom of choice is able to provide "nonconstructive proofs" in which the existence of an object is proved although no explicit example is constructed. ZFC, however, is still formalized in classical logic. The axiom of choice has also been thoroughly studied in the context of constructive mathematics, where non-classical logic is employed. The status of the axiom of choice varies between different varieties of constructive mathematics.

In Martin-Löf type theory and higher-order Heyting arithmetic, the appropriate statement of the axiom of choice is (depending on approach) included as an axiom or provable as a theorem.[10] Errett Bishop argued that the axiom of choice was constructively acceptable, saying

A choice function exists in constructive mathematics, because a choice is implied by the very meaning of existence.[11]

In constructive set theory, however, Diaconescu's theorem shows that the axiom of choice implies the law of excluded middle (unlike in Martin-Löf type theory, where it does not). Thus the axiom of choice is not generally available in constructive set theory. A cause for this difference is that the axiom of choice in type theory does not have the extensionality properties that the axiom of choice in constructive set theory does.[12]

Some results in constructive set theory use the axiom of countable choice or the axiom of dependent choice, which do not imply the law of the excluded middle in constructive set theory. Although the axiom of countable choice in particular is commonly used in constructive mathematics, its use has also been questioned.[13]

In 1938,[14] Kurt Gödel showed that the negation of the axiom of choice is not a theorem of ZF by constructing an inner model (the constructible universe) which satisfies ZFC and thus showing that ZFC is consistent 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 which satisfies ZF¬C (ZF with the negation of AC added as axiom) and thus showing that ZF¬C is consistent.[15]

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. The decision must be made on other grounds.

One argument given in favor of using the axiom of choice is that it is convenient to use it because it allows one to prove some simplifying propositions that otherwise could not be proved. Many theorems which are provable using choice are of an elegant general character: the cardinalities of any two sets are comparable, every nontrivial ring with unity 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. Without the axiom of choice, these theorems may not hold for mathematical objects of large cardinality.

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

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

The axiom of constructibility and the generalized continuum hypothesis each imply the axiom of choice and so 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.

There are important statements that, assuming the axioms of ZF but neither AC nor ¬AC, are equivalent to the axiom of choice.[17] 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
  • Tarski's theorem about choice: For every infinite set A, there is a bijective map between the sets A and A×A.
  • Trichotomy: If two sets are given, then either they have the same cardinality, or one has a smaller cardinality than the other.
  • Given two non-empty sets, one has a surjection to the other.
  • Every surjective function has a right inverse.
  • The Cartesian product of any family of nonempty sets is nonempty. In other words, every family of nonempty sets has a choice function (i.e. a function which maps each of the nonempty sets to one of its elements).
  • König's theorem: Colloquially, the sum of a sequence of cardinals is strictly less than the product of a sequence of larger cardinals. (The reason for the term "colloquially" is that the sum or product of a "sequence" of cardinals cannot itself be defined without some aspect of the axiom of choice.)
  • Well-ordering theorem: Every set can be well-ordered. Consequently, every cardinal has an initial ordinal.
  • Every element of a partially ordered set S is the minimal element of a well-ordered subset having no strict upper bound in S.
  • Zorn's lemma: Every non-empty partially ordered set in which every chain (i.e., totally ordered subset) has an upper bound contains at least one maximal element.
  • Hausdorff maximal principle: Every partially ordered set has a maximal chain. Equivalently, in any partially ordered set, every chain can be extended to a maximal chain.
  • Tukey's lemma: Every non-empty collection of finite character has a maximal element with respect to inclusion.
  • Antichain principle: Every partially ordered set has a maximal antichain. Equivalently, in any partially ordered set, every antichain can be extended to a maximal antichain.
• Abstract algebra
  • Every vector space has a basis (i.e., a linearly independent spanning subset). In other words, vector spaces are equivalent to free modules.[18]
  • Krull's theorem: Every unital ring (other than the trivial ring) contains a maximal ideal. Equivalently, in any nontrivial unital ring, every ideal can be extended to a maximal ideal.
  • For every non-empty set S there is a binary operation defined on S that gives it a group structure.[19] (A cancellative binary operation is enough, see group structure and the axiom of choice.)
  • Every free abelian group is projective.[20]
  • Baer's criterion: Every divisible abelian group is injective.[20]
  • Every set is a projective object in the category Set of sets.[21][22]
• Functional analysis
  • The closed unit ball of the dual of a normed vector space over the reals has an extreme point.
• Point-set topology
  • The Cartesian product of any family of connected topological spaces is connected.
  • Tychonoff's theorem: The Cartesian product of any family of compact topological spaces is compact.
  • In the product topology, the closure of a product of subsets is equal to the product of the closures.
• Mathematical logic
  • If S is a set of sentences of first-order logic and B is a consistent subset of S, then B is included in a set that is maximal among consistent subsets of S. The special case where S is the set of all first-order sentences in a given signature is weaker, equivalent to the Boolean prime ideal theorem; see the section "Weaker forms" below.
• Algebraic topology
  • Every connected graph has a spanning tree. Equivalently, every nonempty graph has a spanning forest.[23]

There are several weaker statements that are not equivalent to the axiom of choice, but are closely related. One example is the axiom of dependent choice (DC). A still weaker example is the axiom of countable choice (AC_ω or CC), which states that a choice function exists for any countable set of nonempty sets. These axioms are sufficient for many proofs in elementary mathematical analysis, and are consistent with some principles, such as the Lebesgue measurability of all sets of reals, that are disprovable from the full axiom of choice.

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.

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[30] + BP is consistent, if ZF is.

It is also consistent with ZF + DC that every set of reals is Lebesgue measurable; however, this consistency result, due to Robert M. Solovay, cannot be proved in ZFC itself, but requires a mild large cardinal assumption (the existence of an inaccessible cardinal). The much stronger axiom of determinacy, or AD, implies that every set of reals is Lebesgue measurable, has the property of Baire, and has the perfect set property (all three of these results are refuted by AC itself). ZF + DC + AD is consistent provided that a sufficiently strong large cardinal axiom is consistent (the existence of infinitely many Woodin 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 which introduced it. In the NF axiomatic system, the axiom of choice can be disproved.[31]

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 prove the negation of some standard facts. Any model of ZF¬C is also a model of ZF, so for each of the following statements, there exists a model of ZF in which that statement is true.

• There 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 {x_n} converging to a, lim_n f(x_n)=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.[32] 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.
• 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.[33]
• There is a set that cannot be linearly ordered.
• There exists a model of ZF¬C in which every set in Rⁿ 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.

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 σ:

${\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.

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

— Jerry Bona[34]

This is a joke: although the three are all mathematically equivalent, many mathematicians find the axiom of choice to be intuitive, the well-ordering principle to be counterintuitive, and Zorn's lemma to be too complex for any intuition.

The Axiom of Choice is necessary to select a set from an infinite number of pairs of socks, but not an infinite number of pairs of shoes.

— Bertrand Russell[35]

The observation here is that one can define a function to select from an infinite number of pairs of shoes, for example by choosing the left shoe from each pair. Without the axiom of choice, one cannot assert that such a function exists for pairs of socks, because left and right socks are (presumably) indistinguishable.

Tarski tried to publish his theorem [the equivalence between AC and "every infinite set A has the same cardinality as A × A", see above] in Comptes Rendus, but Fréchet and Lebesgue refused to present it. Fréchet wrote that an implication between two well known [true] propositions is not a new result, and Lebesgue wrote that an implication between two false propositions is of no interest.

Polish-American mathematician Jan Mycielski relates this anecdote in a 2006 article in the Notices of the AMS.[36]

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

— A. K. Dewdney

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

• 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. Vol. 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.
• Per Martin-Löf, "100 years of Zermelo's axiom of choice: What was the problem with it?", in Logicism, Intuitionism, and Formalism: What Has Become of Them?, Sten Lindström, Erik Palmgren, Krister Segerberg, and Viggo Stoltenberg-Hansen, editors (2008). ISBN 1-4020-8925-2
• 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.
• 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.
• Herman Rubin, Jean E. Rubin: Equivalents of the axiom of choice. North Holland, 1963. Reissued by Elsevier, April 1970. ISBN 0-7204-2225-6.
• Herman Rubin, Jean E. Rubin: Equivalents of the Axiom of Choice II. North Holland/Elsevier, July 1985, ISBN 0-444-87708-8.
• Russell, Bertrand (1993) [1919]. Introduction to mathematical philosophy. New York: Dover Publications. ISBN 978-0-486-27724-0.
• Schechter, Eric (1996). Handbook of Analysis and Its Foundations. San Diego, CA: Academic Press. ISBN 978-0-12-622760-4. OCLC 175294365.
• Suppes, Patrick (1972) [1960]. Axiomatic set theory. Mineola, New York: Dover. ISBN 978-0-486-61630-8.
• George Tourlakis, Lectures in Logic and Set Theory. Vol. II: Set Theory, Cambridge University Press, 2003. 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.
• Ernst Zermelo, "Untersuchungen über die Grundlagen der Mengenlehre I," Mathematische Annalen 65: (1908) pp. 261–81. PDF download via digizeitschriften.de

Translated in: Jean van Heijenoort, 2002. From Frege to 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.

• 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, based on the book by Paul Howard and Jean Rubin.
• "The Axiom of Choice" entry by John Lane Bell in the Stanford Encyclopedia of Philosophy.