TheInfoList

OR: In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the axiom of choice, or AC, is an
axiom An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word (), meaning 'that which is thought worthy or ...
of
set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
equivalent to the statement that ''a
Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\tim ...
of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection of sets, each containing at least one element, it is possible to construct a new set by arbitrarily choosing one element from each set, even if the collection is infinite. Formally, it states that for every indexed family $\left(S_i\right)_$ of nonempty sets, there exists an indexed set $\left(x_i\right)_$ such that $x_i \in S_i$ for every $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. In many cases, a set arising from choosing elements arbitrarily can be made without invoking the axiom of choice; this is, in particular, the case if the number of sets from which to choose the elements is finite, or if a canonical rule on how to choose the elements is available – some distinguishing property that happens to hold for exactly one element in each set. An illustrative example is sets picked from the natural numbers. From such sets, one may always select the smallest number, e.g. given the sets the set containing each smallest element is . In this case, "select the smallest number" is a choice function. Even if infinitely many sets were collected from the natural numbers, it will always be possible to choose the smallest element from each set to produce a set. That is, the choice function provides the set of chosen elements. However, no definite choice function is known for the collection of all non-empty subsets of the real numbers (if there are non-constructible reals). In that case, the axiom of choice must be invoked.
Bertrand Russell Bertrand Arthur William Russell, 3rd Earl Russell, (18 May 1872 – 2 February 1970) was a British mathematician, philosopher, logician, and public intellectual. He had a considerable influence on mathematics, logic, set theory, linguistics, ar ...
coined an analogy: for any (even infinite) collection of pairs of shoes, one can pick out the left shoe from each pair to obtain an appropriate collection (i.e. set) of shoes; this makes it possible to define a choice function directly. For an ''infinite'' collection of pairs of socks (assumed to have no distinguishing features), there is no obvious way to make a function that forms a set out of selecting one sock from each pair, without invoking the axiom of choice. Although originally controversial, the axiom of choice is now used without reservation by most mathematicians, and it is included in the standard form of axiomatic set theory, Zermelo–Fraenkel set theory with the axiom of choice ( ZFC). One motivation for this use is that a number of generally accepted mathematical results, such as Tychonoff's theorem, require the axiom of choice for their proofs. Contemporary set theorists also study axioms that are not compatible with the axiom of choice, such as the axiom of determinacy. The axiom of choice is avoided in some varieties of constructive mathematics, although there are varieties of constructive mathematics in which the axiom of choice is embraced.

# Statement

A choice function (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: : Thus, the
negation In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and fals ...
of the axiom of choice states that there exists a collection of nonempty sets that has no choice function. (
Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\tim ...
of the sets in ''X''. This is not the most general situation of a Cartesian product of a
family Family (from la, familia) is a Social group, group of people related either by consanguinity (by recognized birth) or Affinity (law), affinity (by marriage or other relationship). The purpose of the family is to maintain the well-being of its ...
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.

## Nomenclature ZF, AC, and ZFC

In this article and other discussions of the Axiom of Choice the following abbreviations are common: *AC – the Axiom of Choice. *ZF –
Zermelo–Fraenkel set theory In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such ...
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 ''X'' of
pairwise disjoint In mathematics, two sets are said to be disjoint sets if they have no element in common. Equivalently, two disjoint sets are sets whose intersection is the empty set.. For example, and are ''disjoint sets,'' while and are not disjoint. A c ...
non-empty sets, there exists at least one set ''C'' that contains exactly one element in common with each of the sets in ''X''. This guarantees for any
partition of a set In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset. Every equivalence relation on a set defines a partition of this set, and every part ...
''X'' the existence of a subset ''C'' of ''X'' containing exactly one element from each part of the partition. Another equivalent axiom only considers collections ''X'' that are essentially powersets of other sets: :For any set A, the
power set In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is pos ...
of A (with the empty set removed) has a choice function. Authors who use this formulation often speak of the ''choice function on A'', but this is a slightly different notion of choice function. Its domain is the power set of ''A'' (with the empty set removed), and so makes sense for any set ''A'', whereas with the definition used elsewhere in this article, the domain of a choice function on a ''collection of sets'' is that collection, and so only makes sense for sets of sets. With this alternate notion of choice function, the axiom of choice can be compactly stated as :Every set has a choice function. which is equivalent to :For any set A there is a function ''f'' such that for any non-empty subset B of ''A'', ''f''(''B'') lies in ''B''. The negation of the axiom can thus be expressed as: :There is a set ''A'' such that for all functions ''f'' (on the set of non-empty subsets of ''A''), there is a ''B'' such that ''f''(''B'') does not lie in ''B''.

## Restriction to finite sets

The usual statement of the axiom of choice does not specify whether the collection of nonempty sets is finite or infinite, and thus implies that every finite collection of nonempty sets has a choice function. However, that particular case is a theorem of the Zermelo–Fraenkel set theory without the axiom of choice (ZF); it is easily proved by the principle of finite induction. In the even simpler case of a collection of ''one'' set, a choice function just corresponds to an element, so this instance of the axiom of choice says that every nonempty set has an element; this holds trivially. The axiom of choice can be seen as asserting the generalization of this property, already evident for finite collections, to arbitrary collections.

# Usage

Until the late 19th century, the axiom of choice was often used implicitly, although it had not yet been formally stated. For example, after having established that the set ''X'' contains only non-empty sets, a mathematician might have said "let ''F''(''s'') be one of the members of ''s'' for all ''s'' in ''X''" 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 Ernst Friedrich Ferdinand Zermelo (, ; 27 July 187121 May 1953) was a German logician and mathematician, whose work has major implications for the foundations of mathematics. He is known for his role in developing Zermelo–Fraenkel axiomatic ...
.

# Examples

The nature of the individual nonempty sets in the collection may make it possible to avoid the axiom of choice even for certain infinite collections. For example, suppose that each member of the collection ''X'' is a nonempty subset of the natural numbers. Every such subset has a smallest element, so to specify our choice function we can simply say that it maps each set to the least element of that set. This gives us a definite choice of an element from each set, and makes it unnecessary to 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 number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s. First we might try to proceed as if ''X'' were finite. If we try to choose an element from each set, then, because ''X'' is infinite, our choice procedure will never come to an end, and consequently, we 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 In mathematics, a non-measurable set is a set which cannot be assigned a meaningful "volume". The mathematical existence of such sets is construed to provide information about the notions of length, area and volume in formal set theory. In Zer ...
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.

# Criticism and acceptance

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 In measure theory, a branch of mathematics, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of ''n''-dimensional Euclidean space. For ''n'' = 1, 2, or 3, it coincides wi ...
can be proved to exist using the axiom of choice, it is
consistent In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent ...
that no such set is definable. 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. Because there is no
canonical The adjective canonical is applied in many contexts to mean "according to the canon" the standard, rule or primary source that is accepted as authoritative for the body of knowledge or literature in that context. In mathematics, "canonical example ...
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 Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cate ...
). 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. One example is the
Banach–Tarski paradox The Banach–Tarski paradox is a theorem in set-theoretic geometry, which states the following: Given a solid ball in three-dimensional space, there exists a decomposition of the ball into a finite number of disjoint subsets, which can then be ...
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 In mathematics, a non-measurable set is a set which cannot be assigned a meaningful "volume". The mathematical existence of such sets is construed to provide information about the notions of length, area and volume in formal set theory. In Zer ...
s. Despite these seemingly
paradox A paradox is a logically self-contradictory statement or a statement that runs contrary to one's expectation. It is a statement that, despite apparently valid reasoning from true premises, leads to a seemingly self-contradictory or a logically u ...
ical 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.

# In constructive mathematics

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. Errett Bishop argued that the axiom of choice was constructively acceptable, saying In
constructive set theory Constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory. The same first-order language with "=" and "\in" of classical set theory is usually used, so this is not to be confused with a co ...
, however,
Diaconescu's theorem In mathematical logic, Diaconescu's theorem, or the Goodman–Myhill theorem, states that the full axiom of choice is sufficient to derive the law of the excluded middle, or restricted forms of it, in constructive set theory. It was discovered in 19 ...
shows that the axiom of choice implies the
law of excluded middle In logic, the law of excluded middle (or the principle of excluded middle) states that for every proposition, either this proposition or its negation is true. It is one of the so-called three laws of thought, along with the law of noncontra ...
(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. 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.

# Independence

In 1938, 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. 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 In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but ...
has a basis, every connected graph has a
spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
, and every
product Product may refer to: Business * Product (business), an item that serves as a solution to a specific consumer problem. * Product (project management), a deliverable or set of deliverables that contribute to a business solution Mathematics * Prod ...
of
compact space In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i ...
s 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. Statements in this class include the statement that P = NP, the
Riemann hypothesis In mathematics, the Riemann hypothesis is the conjecture that the Riemann zeta function has its zeros only at the negative even integers and complex numbers with real part . Many consider it to be the most important unsolved problem in pu ...
, 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.

# Stronger axioms

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 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. 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 is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
** 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 In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of ...
has a right inverse. **The
Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\tim ...
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 Cardinal or The Cardinal may refer to: Animals * Cardinal (bird) or Cardinalidae, a family of North and South American birds **'' Cardinalis'', genus of cardinal in the family Cardinalidae **'' Cardinalis cardinalis'', or northern 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 In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable. The size of the largest antichain in a partially ordered set is known as its wid ...
principle: Every partially ordered set has a maximal
antichain In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable. The size of the largest antichain in a partially ordered set is known as its wid ...
. Equivalently, in any partially ordered set, every antichain can be extended to a maximal antichain. *
Abstract algebra In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The ter ...
**Every
vector space In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called '' scalars''. Scalars are often real numbers, but ...
has a basis (''i.e.'', a linearly independent spanning subset). In other words, vector spaces are equivalent to free modules. ** 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 In mathematics, a binary operation or dyadic operation is a rule for combining two elements (called operands) to produce another element. More formally, a binary operation is an operation of arity two. More specifically, an internal binary o ...
defined on ''S'' that gives it a group structure. (A cancellative binary operation is enough, see group structure and the axiom of choice.) **Every
free abelian group In mathematics, a free abelian group is an abelian group with a basis. Being an abelian group means that it is a set with an addition operation that is associative, commutative, and invertible. A basis, also called an integral basis, is a subse ...
is projective. **Baer's criterion: Every divisible abelian group is
injective In mathematics, an injective function (also known as injection, or one-to-one function) is a function that maps distinct elements of its domain to distinct elements; that is, implies . (Equivalently, implies in the equivalent contrapositi ...
. **Every set is a projective object in the
category Category, plural categories, may refer to: Philosophy and general uses *Categorization, categories in cognitive science, information science and generally *Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) ...
Set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...
of sets. *
Functional analysis Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure (e.g. inner product, norm, topology, etc.) and the linear functions defined ...
**The closed unit ball of the dual of a
normed vector space In mathematics, a normed vector space or normed space is a vector space over the real or complex numbers, on which a norm is defined. A norm is the formalization and the generalization to real vector spaces of the intuitive notion of "length" ...
over the reals has an
extreme point In mathematics, an extreme point of a convex set S in a real or complex vector space is a point in S which does not lie in any open line segment joining two points of S. In linear programming problems, an extreme point is also called vertex or ...
. *
Point-set topology In mathematics, general topology is the branch of topology that deals with the basic set-theoretic definitions and constructions used in topology. It is the foundation of most other branches of topology, including differential topology, geometri ...
**The
Cartesian product In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is : A\tim ...
of any family of
connected Connected may refer to: Film and television * ''Connected'' (2008 film), a Hong Kong remake of the American movie ''Cellular'' * '' Connected: An Autoblogography About Love, Death & Technology'', a 2011 documentary film * ''Connected'' (2015 TV ...
topological space In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called point ...
s is connected. ** Tychonoff's theorem: The Cartesian product of any family of
compact Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to: * Interstate compact * Blood compact, an ancient ritual of the Philippines * Compact government, a type of colonial rule utilized in Briti ...
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 Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...
**If ''S'' is a set of sentences of
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
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 A signature (; from la, signare, "to sign") is a handwritten (and often stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. The writer of a ...
is weaker, equivalent to the
Boolean prime ideal theorem In mathematics, the Boolean prime ideal theorem states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on sets is known as the ultrafilter lemma. Other theorems are obtained by consid ...
; see the section "Weaker forms" below. *
Algebraic topology Algebraic topology is a branch of mathematics that uses tools from abstract algebra to study topological spaces. The basic goal is to find algebraic invariants that classify topological spaces up to homeomorphism, though usually most classify u ...
**Every connected graph has a
spanning tree In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not ...
. Equivalently, every nonempty graph has a spanning forest.

## Category theory

There are several results in
category theory Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cate ...
which invoke the axiom of choice for their proof. These results might be weaker than, equivalent to, or stronger than the axiom of choice, depending on the strength of the technical foundations. For example, if one defines categories in terms of sets, that is, as sets of objects and morphisms (usually called a small category), or even locally small categories, whose hom-objects are sets, then there is no category of 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 Category, plural categories, may refer to: Philosophy and general uses *Categorization, categories in cognitive science, information science and generally *Category of being * ''Categories'' (Aristotle) * Category (Kant) * Categories (Peirce) ...
has a
skeleton A skeleton is the structural frame that supports the body of an animal. There are several types of skeletons, including the exoskeleton, which is the stable outer shell of an organism, the endoskeleton, which forms the support structure inside ...
. *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 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 Analysis is the branch of mathematics dealing with continuous functions, limits, and related theories, such as differentiation, integration, measure, infinite sequences, series, and analytic functions. These theories are usually studied in ...
, 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 In mathematics, the Boolean prime ideal theorem states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on sets is known as the ultrafilter lemma. Other theorems are obtained by consid ...
and the axiom of uniformization. The former is equivalent in ZF to Tarski's 1930
ultrafilter lemma In the mathematical field of set theory, an ultrafilter is a ''maximal proper filter'': it is a filter U on a given non-empty set X which is a certain type of non-empty family of subsets of X, that is not equal to the power set \wp(X) of X (such ...
: every filter is a subset of some
ultrafilter In the mathematical field of order theory, an ultrafilter on a given partially ordered set (or "poset") P is a certain subset of P, namely a maximal filter on P; that is, a proper filter on P that cannot be enlarged to a bigger proper filter o ...
.

## 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 that it shows up. Here are some statements that require the axiom of choice in the sense that they are not provable from ZF but are provable from ZFC (ZF plus AC). Equivalently, these statements are true in all models of ZFC but false in some models of ZF. *
Set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
**The
ultrafilter lemma In the mathematical field of set theory, an ultrafilter is a ''maximal proper filter'': it is a filter U on a given non-empty set X which is a certain type of non-empty family of subsets of X, that is not equal to the power set \wp(X) of X (such ...
(with ZF) can be used to prove the Axiom of choice for finite sets: Given $I \neq \varnothing$ and a collection $\left\left(X_i\right\right)_$ of non-empty sets, their product $\prod_ X_$ is not empty. **The union of any countable family of countable sets is countable (this requires countable choice but not the full axiom of choice). **If the set ''A'' is infinite, then there exists an injection from the
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country"). Numbers used for counting are called ''cardinal n ...
s N to ''A'' (see Dedekind infinite). **Eight definitions of a
finite set In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example, :\ is a finite set with five elements. T ...
are equivalent. **Every infinite
game A game is a structured form of play, usually undertaken for entertainment or fun, and sometimes used as an educational tool. Many games are also considered to be work (such as professional players of spectator sports or games) or art (su ...
$G_S$ in which $S$ is a Borel subset of Baire space is determined. * Measure theory **The Vitali theorem on the existence of
non-measurable set In mathematics, a non-measurable set is a set which cannot be assigned a meaningful "volume". The mathematical existence of such sets is construed to provide information about the notions of length, area and volume in formal set theory. In Zer ...
s which states that there is a subset of the
real numbers In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every re ...
that is not
Lebesgue measurable In measure theory, a branch of mathematics, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of ''n''-dimensional Euclidean space. For ''n'' = 1, 2, or 3, it coincides wi ...
Banach–Tarski paradox The Banach–Tarski paradox is a theorem in set-theoretic geometry, which states the following: Given a solid ball in three-dimensional space, there exists a decomposition of the ball into a finite number of disjoint subsets, which can then be ...
. *
Algebra Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics. Elementary a ...
**Every field has an
algebraic closure In mathematics, particularly abstract algebra, an algebraic closure of a field ''K'' is an algebraic extension of ''K'' that is algebraically closed. It is one of many closures in mathematics. Using Zorn's lemmaMcCarthy (1991) p.21Kaplansky ...
. **Every
field extension In mathematics, particularly in algebra, a field extension is a pair of fields E\subseteq F, such that the operations of ''E'' are those of ''F'' restricted to ''E''. In this case, ''F'' is an extension field of ''E'' and ''E'' is a subfield of ' ...
has a transcendence basis. **Every infinite-dimensional vector field contains an infinite linearly independent subset (this requires dependent choice, but not the full axiom of choice). ** Stone's representation theorem for Boolean algebras needs the
Boolean prime ideal theorem In mathematics, the Boolean prime ideal theorem states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on sets is known as the ultrafilter lemma. Other theorems are obtained by consid ...
. **The Nielsen–Schreier theorem, that every subgroup of a free group is free. **The additive groups of R and C are isomorphic. *
Functional analysis Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure (e.g. inner product, norm, topology, etc.) and the linear functions defined ...
**The Hahn–Banach theorem in
functional analysis Functional analysis is a branch of mathematical analysis, the core of which is formed by the study of vector spaces endowed with some kind of limit-related structure (e.g. inner product, norm, topology, etc.) and the linear functions defined ...
, allowing the extension of linear functionals **The theorem that every
Hilbert space In mathematics, Hilbert spaces (named after David Hilbert) allow generalizing the methods of linear algebra and calculus from (finite-dimensional) Euclidean vector spaces to spaces that may be infinite-dimensional. Hilbert spaces arise naturally ...
has an orthonormal basis. **The
Banach–Alaoglu theorem In functional analysis and related branches of mathematics, the Banach–Alaoglu theorem (also known as Alaoglu's theorem) states that the closed unit ball of the dual space of a normed vector space is compact in the weak* topology. A common p ...
about compactness of sets of functionals. **The
Baire category theorem The Baire category theorem (BCT) is an important result in general topology and functional analysis. The theorem has two forms, each of which gives sufficient conditions for a topological space to be a Baire space (a topological space such that t ...
complete Complete may refer to: Logic * Completeness (logic) * Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable Mathematics * The completeness of the real numbers, which implies ...
metric space In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general setti ...
s, 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 In mathematics, general topology is the branch of topology that deals with the basic set-theoretic definitions and constructions used in topology. It is the foundation of most other branches of topology, including differential topology, geometri ...
**A uniform space is compact if and only if it is complete and totally bounded. **Every Tychonoff space has a Stone–Čech compactification. *
Mathematical logic Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...
** 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 In mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model. This theorem is an important tool in model theory, as it provides a useful (but generally ...
: If $\Sigma$ is a set of first-order (or alternatively, zero-order) sentences such that every finite subset of $\Sigma$ has a model, then $\Sigma$ has a model.

## Possibly equivalent implications of AC

There are several historically important set-theoretic statements implied by AC whose equivalence to AC is open. The partition principle, which was formulated before AC itself, was cited by Zermelo as a justification for believing AC. In 1906, Russell declared PP to be equivalent, but whether the partition principle implies AC is still the oldest open problem in set theory, 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 if they can hold without choice. *
Set theory Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concern ...
**Partition principle: if there is a
surjection In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of ...
from ''A'' to ''B'', there is an injection from ''B'' to ''A''. Equivalently, every partition ''P'' of a set ''S'' is less than or equal to ''S'' in size. **Converse Schröder–Bernstein theorem: if two sets have surjections to each other, they are equinumerous. **Weak partition principle: if there is a injection and a
surjection In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of ...
from ''A'' to ''B'', then ''A'' and ''B'' are equinumerous. 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 In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The ter ...
** Hahn embedding theorem: Every ordered abelian group ''G'' order-embeds as a subgroup of the additive group $\mathbb^\Omega$ endowed with a
lexicographical order In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a ...
, 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 + BP is consistent, if ZF is. It is also consistent with ZF + DC that every set of reals is
Lebesgue measurable In measure theory, a branch of mathematics, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of ''n''-dimensional Euclidean space. For ''n'' = 1, 2, or 3, it coincides wi ...
; however, this consistency result, due to Robert M. Solovay, cannot be proved in ZFC itself, but requires a mild
large cardinal In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers. Cardinals with such properties are, as the name suggests, generally very "large" (for example, bigger than the least ...
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.

# Statements consistent with 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 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 converging to ''a'', lim''n'' 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. 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 In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum (least upper bound). Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing. Every Boole ...
on countably many generators. *There is a set that cannot be linearly ordered. *There exists a model of ZF¬C in which every set in R''n'' is measurable. Thus it is possible to exclude counterintuitive results like the
Banach–Tarski paradox The Banach–Tarski paradox is a theorem in set-theoretic geometry, which states the following: Given a solid ball in three-dimensional space, there exists a decomposition of the ball into a finite number of disjoint subsets, which can then be ...
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 mathematics, the branch of real analysis studies the behavior of real numbers, sequences and series of real numbers, and real functions. Some particular properties of real-valued sequences and functions that real analysis studies include conv ...
. *In all models of ZF¬C, the generalized continuum hypothesis does not hold. For proofs, see . 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 In mathematics, logic, and computer science, a type theory is the formal presentation of a specific type system, and in general type theory is the academic study of type systems. Some type theories serve as alternatives to set theory as a founda ...
, 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 σ: :$\left(\forall x^\sigma\right)\left(\exists y^\tau\right) R\left(x,y\right) \to \left(\exists f^\right)\left(\forall x^\sigma\right) R\left(x,f\left(x\right)\right).$ 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.

# Quotations

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 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. Polish-American mathematician Jan Mycielski relates this anecdote in a 2006 article in the Notices of the AMS.. This quote comes from the famous
April Fools' Day April Fools' Day or All Fools' Day is an annual custom on 1 April consisting of practical jokes and hoaxes. Jokesters often expose their actions by shouting "April Fools!" at the recipient. Mass media can be involved in these pranks, which may ...
article in the ''computer recreations'' column of the ''
Scientific American ''Scientific American'', informally abbreviated ''SciAm'' or sometimes ''SA'', is an American popular science magazine. Many famous scientists, including Albert Einstein and Nikola Tesla, have contributed articles to it. In print since 1845, it ...
'', April 1989.

# References

* * * * * * * 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). * * , available as a
Dover Publications Dover Publications, also known as Dover Books, is an American book publisher founded in 1941 by Hayward and Blanche Cirker. It primarily reissues books that are out of print from their original publishers. These are often, but not always, books ...
reprint, 2013, . * * Herman Rubin, Jean E. Rubin: Equivalents of the axiom of choice. North Holland, 1963. Reissued by
Elsevier Elsevier () is a Dutch academic publishing company specializing in scientific, technical, and medical content. Its products include journals such as '' The Lancet'', '' Cell'', the ScienceDirect collection of electronic journals, '' Trends'', t ...
, April 1970. . *Herman Rubin, Jean E. Rubin: Equivalents of the Axiom of Choice II. North Holland/Elsevier, July 1985, . * * * *George Tourlakis, ''Lectures in Logic and Set Theory. Vol. II: Set Theory'',
Cambridge University Press Cambridge University Press is the university press of the University of Cambridge. Granted letters patent by King Henry VIII in 1534, it is the oldest university press in the world. It is also the King's Printer. Cambridge University Pres ...
, 2003. * * Ernst Zermelo, "Untersuchungen über die Grundlagen der Mengenlehre I," ''Mathematische Annalen 65'': (1908) pp. 261–81
::Translated in:
Jean van Heijenoort Jean Louis Maxime van Heijenoort (; July 23, 1912 – March 29, 1986) was a historian of mathematical logic. He was also a personal secretary to Leon Trotsky from 1932 to 1939, and an American Trotskyist until 1947. Life Van Heijenoort was born ...
, 2002. ''From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931''. New edition.
Harvard University Press Harvard University Press (HUP) is a publishing house established on January 13, 1913, as a division of Harvard University, and focused on academic publishing. It is a member of the Association of American University Presses. After the retir ...
. ::*1904. "Proof that every set can be well-ordered," 139-41. ::*1908. "Investigations in the foundations of set theory I," 199–215.