In
mathematicsMathematics is the science and study of quantity, structure, space, and change. Mathematicians seek out patterns, formulate new conjectures, and establish truth by rigorous deduction from appropriately chosen axioms and definitions....
, the
axiom of choice, or
AC, is an
axiomIn traditional logic, an axiom or postulate is a proposition that is not proved or demonstrated but considered to be either self-evident, or subject to necessary decision...
of
set theoryThe modern study of set theory was initiated by Cantor and Dedekind in the 1870s. After the discovery of paradoxes in informal set theory, numerous axiom systems were proposed in the early twentieth century, of which the Zermelo–Fraenkel axioms, with the axiom of choice, are the best-known.The...
. Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin, even if there are
infinitelyIn set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable. Some examples are:* the set of all integers, {..., -1, 0, 1, 2, ...}, is a countably infinite set; and...
many bins and there is no "rule" for which object to pick from each. The axiom of choice is not required if the number of bins is finite or if such a selection "rule" is available.
The axiom of choice was formulated in 1904 by
Ernst ZermeloErnst Friedrich Ferdinand Zermelo was a German mathematician, whose work has major implications for the foundations of mathematics and hence on philosophy.-Life:...
. Although originally controversial, it is now used without reservation by most mathematicians. One motivation for this use is that a number of important mathematical results, such as
Tychonoff's theoremIn mathematics, Tychonoff's theorem states that the product of any collection of compact topological spaces is compact. The theorem is named after Andrey Nikolayevich Tychonoff, who proved it first in 1930 for powers of the closed unit interval and in 1935 stated the full theorem along with the...
, 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 determinacyThe axiom of determinacy is a possible axiom for set theory introduced Jan Mycielski and Hugo Steinhaus. It refers to certain two-person games of length ω with perfect information...
. Unlike the axiom of choice, these alternatives are not ordinarily proposed as axioms for mathematics, but only as principles in set theory with interesting consequences.
Statement
A
choice function- Classic definition :A choice function is a mathematical function whose domain is a collection of nonempty sets such that for every in , is an element of...
is a function
f, defined on a collection
X of nonempty sets, such that for every set
s in
X,
f(
s) is an element of
s. With this concept, the axiom can be stated:
- For any set X of nonempty sets, there exists a choice function f defined on X.
Thus the negation of the axiom of choice states that there exists a set of nonempty sets which has no choice function.
Each choice function on a collection
X of nonempty sets can be viewed as (or identified with) an element of the
Cartesian productIn mathematics, a Cartesian product is the direct product of two sets. The Cartesian product is named after René Descartes, whose formulation of analytic geometry gave rise to this concept....
of the sets in
X. This leads to an equivalent statement of the axiom of choice:
- Given any collection of nonempty sets, their Cartesian product
In mathematics, a Cartesian product is the direct product of two sets. The Cartesian product is named after René Descartes, whose formulation of analytic geometry gave rise to this concept....
is a nonempty set.
Variants
There are many other equivalent statements of the axiom of choice. These are equivalent in the sense that, in the presence of other basic axioms of set theory, they imply the axiom of choice and are implied by it.
One variation avoids the use of choice functions by, in effect, replacing each choice function with its range.
- Given any set X of pairwise disjoint non-empty sets, there exists at least one set C that contains exactly one element in common with each of the sets in X.
Another equivalent axiom only considers collections
X that are essentially powersets of other sets:
- For any set A, the power set
In mathematics, given a set S, the power set of S, written , P, ℘ or 2
S, is the set of all subsets of S. In axiomatic set theory In mathematics, given a set S, the power set (or powerset) of S, written , P(S), ℘(S) or 2
S, is the set of all subsets of S. In...
of A (with the empty set removed) has a choice function.
Authors who use this formulation often speak of the
choice function on A, but be advised that this is a slightly different notion of choice function. Its domain is the powerset of
A (with the empty set removed), and so makes sense for any set
A, whereas with the definition used elsewhere in this article, the domain of a choice function on a
collection of sets is that collection, and so only makes sense for sets of sets. With this alternate notion of choice function, the axiom of choice can be compactly stated as
- Every set has a choice function.
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 AC does not refer to any specific infinite set, and as such has a finite restriction which states that every
finite collectionIn mathematics, finite set is a set that has a finite number of elements. For example,is a finite set with five elements. The number of elements of a finite set is a natural number , and is called the cardinality of the set. A set that is not finite is called infinite...
of nonempty sets has a (finite) choice function. The finite restriction is a theorem of ZF, and is easily proved by
mathematical inductionMathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite...
. The intuitiveness of AC may be due to generalizing from this finite case.
Usage
Until the late 19th century, the axiom of choice was often used implicitly, although it had not yet been formally stated. For example, after having established that the set
X contains only non-empty sets, a mathematician might have said "let
F(s) be one of the members of
s for all
s in
X." In general, it is impossible to prove that
F exists without the axiom of choice, but this seems to have gone unnoticed until Zermelo.
Not every situation requires the axiom of choice. For finite sets
X, the axiom of choice follows from the other axioms of set theory. In that case it is equivalent to saying that if we have several (a finite number of) boxes, each containing at least one item, then we can choose exactly one item from each box. Clearly we can do this: We start at the first box, choose an item; go to the second box, choose an item; and so on. The number of boxes is finite, so eventually our choice procedure comes to an end. The result is an explicit choice function: a function that takes the first box to the first element we chose, the second box to the second element we chose, and so on. (A formal proof for all finite sets would use the principle of
mathematical inductionMathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite...
.)
For certain
infinite setIn set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable. Some examples are:* the set of all integers, {..., -1, 0, 1, 2, ...}, is a countably infinite set; and...
s
X, it is also possible to avoid the axiom of choice. For example, suppose that the elements of
X are sets of natural numbers. Every nonempty set of natural numbers 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 we can write down an explicit expression that tells us what value our choice function takes. Any time it is possible to specify such an explicit choice, the axiom of choice is unnecessary.
The difficulty appears when there is no natural choice of elements from each set. If we cannot make explicit choices, how do we know that our set exists? For example, suppose that
X is the set of all non-empty subsets of the
real numberIn mathematics, the real numbers include both rational numbers, such as 42 and −23/129, and irrational numbers, such as pi and the square root of two; or, a real number can be given by an infinite decimal representation, such as 2.4871773339..., where the digits continue in some way; or, the real...
s. First we might try to proceed as if
X were finite. If we try to choose an element from each set, then, because
X is infinite, our choice procedure will never come to an end, and consequently, we will never be able to produce a choice function for all of
X. So that won't work. Next we might try the trick of specifying the least element from each set. But some subsets of the real numbers don't 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 taking least elements doesn't work, either.
The reason that we are able to choose least elements from subsets of the natural numbers is the fact that the natural numbers come pre-equipped with a
well-orderIn mathematics, a well-order relation on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering.Equivalently, a well-ordering is a well-founded total order....
ing: Every subset of the natural numbers has a unique least element under the natural ordering. Perhaps if we were clever we 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 is true.
Nonconstructive aspects
A proof requiring the axiom of choice is, in one meaning of the word, nonconstructive: even though the proof establishes the existence of an object, it may be impossible to
defineIn mathematical logic, a definable set is an n-ary relation on the domain of a structure whose elements are precisely those elements satisfying some formula in the language of the structure...
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. As another example, a subset of the real numbers that is not
Lebesgue measurableIn mathematics, the Lebesgue measure, named after Henri Lebesgue, is the standard way of assigning a length, area or volume to subsets of Euclidean space. It is used throughout real analysis, in particular to define Lebesgue integration...
can be proven to exist using the axiom of choice, but it is consistent that no such set is definable.
The axiom of choice produces these intangibles (objects that are proven to exist by a nonconstructive proof, but cannot be explicitly constructed), which may conflict with some philosophical principles. Because there is no
canonicalCanonical is an adjective derived from canon. Canon comes from the Greek word kanon, "rule" , and is used in various meanings....
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 theoryIn mathematics, category theory deals in an abstract way with mathematical structures and relationships between them: it abstracts from sets and functions to objects linked in diagrams by morphisms or arrows....
). In
constructivismIn the philosophy of mathematics, constructivism asserts that it is necessary to find a mathematical object to prove that it exists...
, all existence proofs are required to be totally explicit. That is, one must be able to construct, in an explicit and canonical manner, anything that is proven to exist. This foundation rejects the full axiom of choice because it asserts the existence of an object without uniquely determining its structure. In fact the Diaconescu–Goodman–Myhill theorem shows how to derive the constructively unacceptable law of the excluded middle, or a restricted form of it, in
constructive set theoryConstructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory. That is, it uses the usual first-order language of classical set theory, and although of course the logic is constructive, there is no explicit use of constructive types...
from the assumption of the axiom of choice.
Another argument against the axiom of choice is that it implies the existence of counterintuitive objects. One example of this is the
Banach–Tarski paradoxThe Banach–Tarski paradox is a theorem in set theoretic geometry which states that a solid ball in 3-dimensional space can be split into a finite number of non-overlapping pieces, which can then be put back together in a different way to yield two identical copies of the original ball...
which says that it is possible to decompose ("carve up") the 3-dimensional solid unit ball into finitely many pieces and, using only rotations and translations, reassemble the pieces into two solid balls each with the same volume as the original. The pieces in this decomposition, constructed using the axiom of choice, are extremely complicated.
The majority of 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 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; this is common in constructive mathematics. Such statements will be true in any
modelIn mathematics, model theory is the study of mathematical structures such as groups, fields, graphs, or even universes of set theory, using tools from mathematical logic. A structure that gives meaning to the sentences of a formal language is called a model for the language...
of
Zermelo–Fraenkel set theoryZermelo–Fraenkel set theory with the axiom of choice, commonly abbreviated ZFC, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics...
(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, 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.
Independence
By work of
Kurt GödelKurt Gödel was an Austrian-American logician, mathematician and philosopher. One of the most significant logicians of all time, Gödel made an immense impact upon scientific and philosophical thinking in the 20th century, a time when many, such as Bertrand Russell, A. N...
and
Paul CohenPaul Joseph Cohen was an American mathematician best known for his proof of the independence of the continuum hypothesis and the axiom of choice from Zermelo–Fraenkel set theory, the most widely accepted axiomatization of set theory.- Early years :Paul J. Cohen was born in Long Branch, New Jersey...
, the axiom of choice is
logically independentIn mathematical logic, independence refers to the unprovability of a sentence from other sentences.A sentence σ is independent of a given first-order theory T if T neither proves nor refutes σ; that is, it is impossible to prove σ from T, and it is also impossible to prove from T...
of the other axioms of
Zermelo–Fraenkel set theoryZermelo–Fraenkel set theory with the axiom of choice, commonly abbreviated ZFC, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics...
(ZF). This means that neither it nor its negation can be proven to be true in ZF, if ZF is consistent. Consequently, if ZF is consistent, then ZFC is consistent and ZF¬C is also consistent. So the decision whether or not it is appropriate to make use of the axiom of choice 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: using it cannot hurt (cannot result in contradiction) and makes it possible to prove some propositions that otherwise could not be proved. Many theorems which are provable using choice are of an elegant general character: every ideal in a ring is contained in a maximal ideal, every vector space has a basis, and every product of compact spaces is compact. Without the axiom of choice, these theorems may not hold for mathematical objects of large cardinality.
The proof of the independence result also shows that a wide class of mathematical statements, including all statements that can be phrased in the language of Peano arithmetic, are provable in ZF if and only if they are provable in ZFC. Statements in this class include the statement that P = NP, the
Riemann hypothesisIn mathematics, the Riemann hypothesis, proposed by , is a conjecture about the distribution of the zeros of the Riemann zeta-function stating that all non-trivial zeros of the Riemann zeta function have real part 1/2...
, 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 ZF plus the axiom of choice (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 constructibilityThe axiom of constructibility is a possible axiom for set theory in mathematics that asserts that every set is constructible. The axiom is usually written as "V = L", where V and L denote the von Neumann universe and the constructible universe, respectively.- Implications :The axiom of...
and the generalized continuum hypothesis both imply the axiom of choice, but are strictly stronger than it.
In class theories such as
Von Neumann–Bernays–Gödel set theoryIn the foundations of mathematics, Von Neumann–Bernays–Gödel set theory is an axiomatic set theory that is a conservative extension of the canonical axiomatic set theory ZFC. A statement in the language of ZFC is provable in NBG if and only if it is provable in ZFC. The ontology of NBG includes...
and
Morse–Kelley set theoryIn the foundation of mathematics, Kelley–Morse or Morse–Kelley set theory is a first order axiomatic set theory that is closely related to Von Neumann–Bernays–Gödel set theory . MK allows the bound variables in the schematic formula appearing in the axiom schema of Class Comprehension to range...
, there is a possible axiom called the
axiom of global choiceIn class theories, the axiom of global choice is a stronger variant of the axiom of choice which applies to proper classes as well as sets.- Statement :The axiom can be expressed in various ways which are equivalent:...
which is stronger than the axiom of choice for sets because it also applies to proper classes. And the axiom of global choice follows from the
axiom of limitation of sizeIn class theories, the axiom of limitation of size says that for any class C, C is a proper class if and only if V can be mapped one-to-one into C....
.
Equivalents
There are a remarkable number of 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 lemmaZorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory that states:Every partially ordered set in which every chain has an upper bound contains at least one maximal element....
and the
well-ordering theoremIn Mathematics, the well-ordering theorem states that every set can be well-ordered. This is known as the Zermelo's theorem and is equivalent to the Axiom of Choice as a result of a theorem which states that if every set can be well ordered, then for every set there exists a choice function.Ernst...
. In fact, Zermelo initially introduced the axiom of choice in order to formalize his proof of the well-ordering principle.
- First-order logic
First-order logic is a formal logic used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, and predicate logic...
- If A is a set of sentences of first-order logic
First-order logic is a formal logic used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, and predicate logic...
and B is a consistent subset, then B is included in a maximal consistent subset of A.
- Set theory
The modern study of set theory was initiated by Cantor and Dedekind in the 1870s. After the discovery of paradoxes in informal set theory, numerous axiom systems were proposed in the early twentieth century, of which the Zermelo–Fraenkel axioms, with the axiom of choice, are the best-known.The...
- Well-ordering theorem
In Mathematics, the well-ordering theorem states that every set can be well-ordered. This is known as the Zermelo's theorem and is equivalent to the Axiom of Choice as a result of a theorem which states that if every set can be well ordered, then for every set there exists a choice function.Ernst...
: Every set can be well-ordered. Consequently, every cardinal has an initial ordinal.
- Tarski
Alfred Tarski was a Polish logician and mathematician...
's theorem: 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.
- The Cartesian product
In mathematics, a Cartesian product is the direct product of two sets. The Cartesian product is named after René Descartes, whose formulation of analytic geometry gave rise to this concept....
of any nonempty family of nonempty sets is nonempty.
- König's theorem
In set theory, König's theorem colloquially states that if the axiom of choice holds, I is a set, mi and ni are cardinal numbers for every i in I, and for every i in I thenThe sum here is the cardinality of the disjoint union of...
: Colloquially, the sum of a sequence of cardinals is strictly less than the product of a sequence of larger cardinals. (The reason for the term "colloquially", is that the sum or product of a "sequence" of cardinals cannot be defined without some aspect of the axiom of choice.)
- Every surjective function
In mathematics, a function is said to be surjective or onto if its range is equal to its codomain. A function is surjective if and only if for every y in the codomain Y there is at least one x in the domain X such that f = y...
has a right inverseA right inverse in mathematics may refer to:* A right inverse element with respect to a binary operation on a set* A right inverse function for a mapping between sets...
.
- Order theory
Order theory is a branch of mathematics that studies various kinds of binary relations that capture the intuitive notion of ordering, providing a framework for saying when one thing is "less than" or "precedes" another. This article gives a detailed introduction to the field and includes some of...
- Zorn's lemma
Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory that states:Every partially ordered set in which every chain has an upper bound contains at least one maximal element....
: Every non-empty partially ordered set in which every chain (i.e. totally ordered subset) has an upper bound contains at least one maximal element.
- Hausdorff maximal principle
In mathematics, the Hausdorff maximal principle, formulated and proved by Felix Hausdorff in 1914, is an alternate and earlier formulation of Zorn's lemma and therefore also equivalent to the axiom of choice....
: In any partially ordered set, every totally ordered subset is contained in a maximal totally ordered subset.
- Restricted Hausdorff maximal principle
In mathematics, the Hausdorff maximal principle, formulated and proved by Felix Hausdorff in 1914, is an alternate and earlier formulation of Zorn's lemma and therefore also equivalent to the axiom of choice....
: In any partially ordered set there exists a maximal totally ordered subset.
- Tukey's lemma
In mathematics, Tukey's lemma, named after John Tukey, states that every nonempty collection of finite character has a maximal element with respect to inclusion. It is equivalent to the Axiom of Choice.- References :* Brillinger, David R. "John Wilder Tukey"...
: 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 elements in the subset are incomparable. Let S be a partially ordered set...
principle: Every partially ordered set has a maximal antichainIn mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two elements in the subset are incomparable. Let S be a partially ordered set...
.
- Algebra
Algebra is the branch of mathematics concerning the study of the rules of operations and the things which can be constructed from them, including terms, polynomials, equations and algebraic structures...
- Every vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
has a basisIn linear algebra, a basis is a set of vectors that, in a linear combination, can represent every vector in a given vector space or free module, and such that no element of the set can be represented as a linear combination of the others...
.
- Every unital ring
In mathematics, a ring is an algebraic structure consisting of a set together with two binary operations , where each operation combines two elements to form a third element...
other than the trivial ring contains a maximal idealIn mathematics, more specifically in ring theory, a maximal ideal is an ideal which is maximal amongst all proper ideals. In other words, if R is a ring with a maximal ideal I, and if J is another ideal containing I as a subset, then either J = I or J = R...
.
- General topology
In mathematics, general topology or point-set topology is the branch of topology which studies properties of topological spaces and structures defined on them...
- Tychonoff's theorem
In mathematics, Tychonoff's theorem states that the product of any collection of compact topological spaces is compact. The theorem is named after Andrey Nikolayevich Tychonoff, who proved it first in 1930 for powers of the closed unit interval and in 1935 stated the full theorem along with the...
stating that every productIn topology and related areas of mathematics, a product space is the cartesian product of a family of topological spaces equipped with a natural topology called the product topology...
of compactIn mathematics, more specifically general topology and metric topology, a compact space is an abstract mathematical space in which, intuitively, whenever one takes an infinite number of "steps" in the space, eventually one must get arbitrarily close to some other point of the space...
topological spaceTopological spaces are mathematical structures that allow the formal definition of concepts such as convergence, connectedness, and continuity. They appear in virtually every branch of modern mathematics and are a central unifying notion...
s is compact.
- In the product topology, the closure
In mathematics, the closure of a subset S in a topological space consists of all points which are intuitively "close to S". A point which is in the closure of S is a point of closure of S...
of a product of subsets is equal to the product of the closures.
- Any product of complete
In mathematical analysis, a metric space M is said to be complete if every Cauchy sequence of points in M has a limit that is also in M or alternatively if every Cauchy sequence in M converges in M....
uniform spaceIn the mathematical field of topology, a uniform space is a set with a uniform structure. Uniform spaces are topological spaces with additional structure which is used to define uniform properties such as completeness, uniform continuity and uniform convergence.The conceptual difference between...
s is complete.
- Functional analysis
Functional analysis is the branch of mathematics, and specifically of analysis, concerned with the study of vector spaces and operators acting upon them. It has its historical roots in the study of functional spaces, in particular transformations of functions, such as the Fourier transform, as well...
- The closed unit ball of the dual of a normed vector space
In mathematics, with 2- or 3-dimensional vectors with real-valued entries, the idea of the "length" of a vector is intuitive and can easily be extended to any real vector space Rn. The following properties of "vector length" are crucial....
over the reals has an extreme pointAn extreme point or an extremal point is a point that belongs to the extremity of something.*In mathematics, an extreme point of a convex set S in a real vector space is a point in S which does not lie in any open line segment joining two points of S. Intuitively, an extreme point is a "corner" of S...
.
Category theory
There are several results in
category theoryIn mathematics, category theory deals in an abstract way with mathematical structures and relationships between them: it abstracts from sets and functions to objects linked in diagrams by morphisms or arrows....
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 setsIn mathematics, the category of sets, denoted as Set, is the category whose objects are all sets and whose morphisms are all functions. It is the most basic and the most commonly used category in mathematics.-Properties of the category of 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
In mathematics, a category is an algebraic structure consisting of a collection of "objects", linked together by a collection of "arrows" that have two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. Objects and arrows may...
has a skeletonIn mathematics, a skeleton of a category is a subcategory which, roughly speaking, does not contain any extraneous isomorphisms. In a certain sense, the skeleton of a category is the "smallest" equivalent category which captures all "categorical properties". In fact, two categories are equivalent...
.
- If two small categories are weakly equivalent, then they are equivalent
In category theory, an abstract branch of mathematics, an equivalence of categories is a relation between two categories that establishes that these categories are "essentially the same". There are numerous examples of categorical equivalences from many areas of mathematics...
.
- Every continuous functor on a small-complete category which satisfies the appropriate solution set condition has a left-adjoint
In mathematics, adjoint functors are pairs of functors which stand in a particular relationship with one another, called an adjunction. The relationship of adjunction is ubiquitous in mathematics, as it rigorously reflects the intuitive notions of optimization and efficiency...
(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 choiceIn mathematics, the axiom of dependent choices, denoted DC, is a weak form of the axiom of choice which is still sufficient to develop most of real analysis...
(DC). A still weaker example is the
axiom of countable choiceThe axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom of set theory, similar to the axiom of choice. It states that any countable collection of non-empty sets must have a choice function...
(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 analysisMathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of calculus. It is the branch of pure mathematics most explicitly concerned with the notion of a limit, whether the limit of a sequence or the limit of a function...
, and are consistent with some principles, such as the Lebesgue measurability of all sets of reals, that are disprovable from the axiom of choice.
Other choice axioms weaker than axiom of choice include the
Boolean prime ideal theoremIn mathematics, a prime ideal theorem guarantees the existence of certain types of subsets in a given abstract algebra. A common example is the Boolean prime ideal theorem, which states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on...
and the
axiom of uniformizationIn set theory, the axiom of uniformization, a weak form of the axiom of choice, states that if is a subset of , where and are Polish spaces,then there is a subset of that is a partial function from to , and whose domain equalsSuch a function is called a uniformizing function for , or a...
.
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
The modern study of set theory was initiated by Cantor and Dedekind in the 1870s. After the discovery of paradoxes in informal set theory, numerous axiom systems were proposed in the early twentieth century, of which the Zermelo–Fraenkel axioms, with the axiom of choice, are the best-known.The...
- Any union
In set theory, the union of a collection of sets is the set of all distinct elements in the collection. The union of a collection of sets gives a set .- Definition :A simple example:...
of countably many countable sets is itself countable.
- If the set A is infinite, then there exists an injection
In mathematics, an injective function is a function that associates distinct arguments with distinct values; in other words, every unique argument produces a unique result...
from the natural numberIn mathematics, there are two conventions for the set of natural numbers: it is either the set of positive integers {, , , ...} according to the traditional definition or the set of non-negative integers {, 1, 2, ...} according to...
s N to A (see Dedekind infinite).
- Every infinite game in which is a Borel subset of Baire space
In set theory, the Baire space is the set of all infinite sequences of natural numbers with a certain topology. This space is commonly used in descriptive set theory, to the extent that its elements are often called “reals.” It is often denoted B, NN, or ωω...
is determined.
- Measure theory
- The Vitali theorem
In mathematics, a Vitali set is an elementary example of a set of real numbers that is not Lebesgue measurable, named after Giuseppe Vitali. The Vitali theorem is the existence theorem that there are such sets...
on the existence of non-measurable setIn mathematics, a non-measurable set is a subset of a set with finite positive measure where the subset's structure is so complicated that it cannot itself have a meaningful measure. Such sets are constructed to shed light on the notions of length, area and volume in formal set theory.The notion...
s which states that there is a subset of the real numbers that is not Lebesgue measurable.
- The Hausdorff paradox
In mathematics, the Hausdorff paradox, named after Felix Hausdorff, states that if you remove a certain countable subset of the sphere S2, the remainder can be divided into three disjoint subsets A, B and C such that A, B, C and B ∪ C are all congruent...
.
- The Banach–Tarski paradox
The Banach–Tarski paradox is a theorem in set theoretic geometry which states that a solid ball in 3-dimensional space can be split into a finite number of non-overlapping pieces, which can then be put back together in a different way to yield two identical copies of the original ball...
.
- The Lebesgue measure
In mathematics, the Lebesgue measure, named after Henri Lebesgue, is the standard way of assigning a length, area or volume to subsets of Euclidean space. It is used throughout real analysis, in particular to define Lebesgue integration...
of a countable disjoint unionIn mathematics, the term disjoint union may refer to one of two different concepts:* In set theory, a disjoint union is a modified union operation which indexes the elements according to which set they originated in;...
of measurable sets is equal to the sum of the measures of the individual sets.
- Algebra
Algebra is the branch of mathematics concerning the study of the rules of operations and the things which can be constructed from them, including terms, polynomials, equations and algebraic structures...
- Every field
In abstract algebra, a field is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
has an algebraic closureIn 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....
.
- Every field extension
In mathematics, more specifically in abstract algebra, field extensions are the main object of study in field theory. The general idea is to start with a base field and construct in some manner a larger field which contains the base field and satisfies additional properties.Field extensions can be...
has a transcendence basis.
- Stone's representation theorem for Boolean algebras
In mathematics, Stone's representation theorem for Boolean algebras states that every Boolean algebra is isomorphic to a field of sets. The theorem is fundamental to the deeper understanding of Boolean algebra that emerged in the first half of the 20th century. The theorem was first proved by Stone...
needs the Boolean prime ideal theoremIn mathematics, a prime ideal theorem guarantees the existence of certain types of subsets in a given abstract algebra. A common example is the Boolean prime ideal theorem, which states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on...
.
- The Nielsen-Schreier theorem, that every subgroup of a free group is free.
- The additive group
An additive group may refer to:*an abelian group, when it is written using the symbol + for its binary operation*a group scheme representing the underlying-additive-group functor...
s of R and C are isomorphic. http://www.cs.nyu.edu/pipermail/fom/2006-February/009959.html
- Functional analysis
Functional analysis is the branch of mathematics, and specifically of analysis, concerned with the study of vector spaces and operators acting upon them. It has its historical roots in the study of functional spaces, in particular transformations of functions, such as the Fourier transform, as well...
- The Hahn-Banach theorem in functional analysis
Functional analysis is the branch of mathematics, and specifically of analysis, concerned with the study of vector spaces and operators acting upon them. It has its historical roots in the study of functional spaces, in particular transformations of functions, such as the Fourier transform, as well...
, allowing the extension of linear functionals
- The theorem that every Hilbert space
The mathematical concept of a Hilbert space, named after David Hilbert, generalizes the notion of Euclidean space. It extends the methods of vector algebra and calculus from the two-dimensional Euclidean plane and three-dimensional space to spaces with any finite or infinite number of dimensions...
has an orthonormal basis.
- The Banach-Alaoglu theorem
In functional analysis and related branches of mathematics, the Banach–Alaoglu theorem states that the closed unit ball of the dual space of a normed vector space is compact in the weak* topology. A common proof identifies the unit ball with the weak* topology as a closed subset of a product of...
about compactness of sets of functionals.
- The Baire category theorem
The Baire category theorem is an important tool 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....
about completeIn mathematical analysis, a metric space M is said to be complete if every Cauchy sequence of points in M has a limit that is also in M or alternatively if every Cauchy sequence in M converges in M....
metric spaceIn mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
s, and its consequences, such as the open mapping theoremIn functional analysis, the open mapping theorem, also known as the Banach–Schauder theorem, is a fundamental result which states that if a continuous linear operator between Banach spaces is surjective then it is an open map...
and the closed graph theoremIn mathematics, the closed graph theorem is a basic result in functional analysis which characterizes continuous linear operators between Banach spaces in terms of the operator graph.- The closed graph theorem :...
.
- On every infinite-dimensional topological vector space there is a discontinuous linear map
In mathematics, linear maps form an important class of "simple" functions which preserve the algebraic structure of linear spaces and are often used as approximations to more general functions . If the spaces involved are also topological spaces , then it makes sense to ask whether all linear maps...
.
- General topology
In mathematics, general topology or point-set topology is the branch of topology which studies properties of topological spaces and structures defined on them...
- A uniform space is compact if and only if it is complete and totally bounded.
- Every Tychonoff space
In topology and related branches of mathematics, Tychonoff spaces and completely regular spaces are particularly nice kinds of topological spaces.These conditions are examples of separation axioms....
has a Stone–Čech compactificationIn the mathematical discipline of general topology, Stone–Čech compactification is a technique for constructing a universal map from a topological space X to a compact Hausdorff space βX...
.
Stronger forms of the negation of AC
Now, consider stronger forms of the negation of AC. For example, if we abbreviate by BP the claim that every set of real numbers has the
property of BaireA subset of a topological space has the property of Baire if it differs from an open set by a meager set; that is, if there is an opensuch thatis meager .If a subset of a Polish space has the property of Baire, then its corresponding Banach-Mazur game is determined...
, then BP is stronger than ¬AC, which asserts the nonexistence of any choice function on perhaps only a single set of nonempty sets. Note that strengthened negations may be compatible with weakened forms of AC. For example, ZF + DC + 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. SolovayRobert Martin Solovay is a set theorist who spent many years as a professor at UC Berkeley. Among his most noted accomplishments are showing that the statement "every set of real numbers is Lebesgue measurable" is consistent with ZF without the axiom of choice, and isolating the notion of...
, cannot be proved in ZFC itself, but requires a mild large cardinal assumption (the existence of an
inaccessible cardinalIn set theory, an uncountable regular cardinal number is called weakly inaccessible if it is a weak limit cardinal, and strongly inaccessible, or just inaccessible, if it is a strong limit cardinal...
). The much stronger
axiom of determinacyThe axiom of determinacy is a possible axiom for set theory introduced Jan Mycielski and Hugo Steinhaus. It refers to certain two-person games of length ω with perfect information...
, or AD, implies that every set of reals is Lebesgue measurable, has the property of Baire, and has the
perfect set propertyIn descriptive set theory, a subset of a Polish space has the perfect set property if it is either countable or has a nonempty perfect subset.As nonempty perfect sets in a Polish space always have the cardinality of the continuum, a set with the perfect set property cannot be a counterexample to...
(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 cardinalIn set theory, a Woodin cardinal is a cardinal number λ such that for all functionsthere exists a cardinal κ < λ withand an elementary embeddingfrom V into a transitive inner model M with critical point κ and...
s).
Statements consistent with the negation of AC
There are models of Zermelo-Fraenkel set theory in which the axiom of choice is false. We will abbreviate "Zermelo-Fraenkel set theory plus the negation of the axiom of choice" by ZF¬C. For certain models of ZF¬C, it is possible to prove the negation of some standard facts.
Note that any model of ZF¬C is also a model of ZF, so for each of the following statements, there exists a model of ZF in which that statement is true.
- There exists a model of ZF¬C in which there is a function f from the real numbers to the real numbers such that f is not continuous at a, but f is sequentially continuous at a, i.e., for any sequence {xn} converging to a, limn f(xn)=f(a).
- There exists a model of ZF¬C which has an infinite set of real numbers without a countably infinite subset.
- There exists a model of ZF¬C in which real numbers are a countable union of countable sets.
- There exists a model of ZF¬C in which there is a field with no algebraic closure.
- In all models of ZF¬C there is a vector space with no basis.
- There exists a model of ZF¬C in which there is a vector space with two bases of different cardinalities.
- There exists a model of ZF¬C in which there is a free complete boolean algebra
In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum . Complete Boolean algebras are used to construct Boolean-valued models of set theory in the theory of forcing...
on countably many generators.
For proofs, see
Thomas JechThomas J. Jech is a mathematician specializing in set theory who was at Penn State for more than 25 years. He was educated at Charles University and is now at the of the Academy of Sciences of the Czech Republic.-Books:* Lectures in set theory, Springer-Verlag Lecture Notes in Mathematics 217 ...
,
The Axiom of Choice, American Elsevier Pub. Co., New York, 1973.
- 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
The Banach–Tarski paradox is a theorem in set theoretic geometry which states that a solid ball in 3-dimensional space can be split into a finite number of non-overlapping pieces, which can then be put back together in a different way to yield two identical copies of the original ball...
which are provable in ZFC. Furthermore, this is possible whilst assuming the Axiom of dependent choiceIn mathematics, the axiom of dependent choices, denoted DC, is a weak form of the axiom of choice which is still sufficient to develop most of real analysis...
, which is weaker than AC but sufficient to develop most of real analysisReal analysis, or theory of functions of a real variable is a branch of mathematical analysis dealing with the set of real numbers. In particular, it deals with the analytic properties of real functions and sequences, including convergence and limits of sequences of real numbers, the calculus of...
.
- In all models of ZF¬C, the generalized continuum hypothesis
In mathematics, the continuum hypothesis is a hypothesis, advanced by Georg Cantor in 1877, about the possible sizes of infinite sets. It states:Establishing the truth or falsehood of the continuum hypothesis is the first of Hilbert's twenty-three problems presented in the year 1900...
does not hold.
Quotes
"The Axiom of Choice is obviously true, the
well-ordering principleIn Mathematics, the well-ordering theorem states that every set can be well-ordered. This is known as the Zermelo's theorem and is equivalent to the Axiom of Choice as a result of a theorem which states that if every set can be well ordered, then for every set there exists a choice function.Ernst...
obviously false, and who can tell about
Zorn's lemmaZorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory that states:Every partially ordered set in which every chain has an upper bound contains at least one maximal element....
?" — Jerry Bona
- This is a joke: although the three are all mathematically equivalent, many mathematicians find the axiom of choice to be intuitive, the well-ordering principle to be counterintuitive, and Zorn's lemma to be too complex for any intuition.
"The Axiom of Choice is necessary to select a set from an infinite number of socks, but not an infinite number of shoes." —
Bertrand RussellBertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was an English philosopher, logician, mathematician, historian, and social critic. Although he spent the majority of his life in England, he was born in Wales, where he also died.Russell led the British "revolt against idealism" in the...
- The observation here is that one can define a function to select from an infinite number of pairs of shoes by stating for example, to choose the left shoe. Without the axiom of choice, one cannot assert that such a function exists for pairs of socks, because left and right socks are (presumably) indistinguishable from each other.
"Tarski tried to publish his theorem [the equivalence between AC and 'every infinite set
A has the same cardinality as
AxA, see above] in Comptes Rendus, but
FréchetMaurice Fréchet was a French mathematician. He made major contributions to the topology of point sets and introduced the entire concept of metric spaces. He also made several important contributions to the field of statistics and probability, as well as calculus...
and
LebesgueHenri Léon Lebesgue was a French mathematician most famous for Lebesgue's theory of integration, which was a generalization of the seventeenth century concept of integration—summing the area between an axis and the curve of a function defined for that axis...
refused to present it. Fréchet wrote that an implication between two well known [true] propositions is not a new result, and Lebesgue wrote that an implication between two false propositions is of no interest".
- Polish-American mathematician Jan Mycielski relates this anecdote in a 2006 article in the Notices of the AMS.
"The axiom gets its name not because mathematicians prefer it to other axioms." — A. K. Dewdney
- This quote comes from the famous April Fools' Day
April Fools' Day or All Fools' Day is a day celebrated in many countries on April 1. The day is marked by the commission of hoaxes and other practical jokes of varying sophistication on friends, family members, enemies, and neighbors, or sending them on a fool's errand, the aim of which is to...
article in the computer recreations column of the Scientific AmericanScientific American is a popular science magazine published since August 28, 1845, which according to the magazine makes it the oldest continuously published magazine in the United States...
, April 1989.
External links