In the set containing each smallest element is . In this case, "select the smallest number" is a

_{''i''} : ''i''∈ω) of nonempty sets, a function is obtained at each finite stage, but there is no stage at which a choice function for the entire family is constructed, and no "limiting" choice function can be constructed, in general, in ZF without the axiom of choice.

_{ω} or CC), which states that a choice function exists for any countable set of nonempty sets. These axioms are sufficient for many proofs in elementary mathematical analysis, and are consistent with some principles, such as the Lebesgue measurability of all sets of reals, that are disprovable from the full axiom of choice.
Other choice axioms weaker than axiom of choice include the Boolean prime ideal theorem and the Uniformization (set theory), axiom of uniformization. The former is equivalent in ZF to Alfred Tarski, Tarski's 1930 ultrafilter lemma: every Filter (mathematics), filter is a subset of some Ultrafilter (set theory), ultrafilter.

_{''n''} f(''x_{n}'')=f(a).
*In some model, there is an infinite set of real numbers without a countably infinite subset.
*In some model, 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.
*In some model, there is a field with no algebraic closure.
*In all models of ZF¬C there is a vector space with no basis.
*In some model, there is a vector space with two bases of different cardinalities.
*In some model there is a free complete boolean algebra on countably many generators.
*In some model there is Amorphous set, 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

PDF download via digizeitschriften.de

::Translated in: Jean van Heijenoort, 2002. ''From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931''. New edition. Harvard University Press. ::*1904. "Proof that every set can be well-ordered," 139-41. ::*1908. "Investigations in the foundations of set theory I," 199–215.

Axiom of Choice

entry in the Springer Encyclopedia of Mathematics.

Axiom of Choice and Its Equivalents

entry at ProvenMath. Includes formal statement of the Axiom of Choice, Hausdorff's Maximal Principle, Zorn's Lemma and formal proofs of their equivalence down to the finest detail.

based on the book b

Paul Howard

and Jean Rubin. *. {{DEFAULTSORT:Axiom Of Choice Axiom of choice,

mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...

, the axiom of choice, or AC, is an axiom
An axiom, postulate or assumption is a statement that is taken to be truth, true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Greek ''axíōma'' () 'that which is thought worthy or fit' o ...

of set theory
Set theory is the branch of mathematical logic that studies Set (mathematics), 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, i ...

equivalent to the statement that ''a Cartesian product
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

of a collection of non-empty sets is non-empty''. 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 the collection is infinite
Infinite may refer to:
Mathematics
*Infinite set, a set that is not a finite set
*Infinity, an abstract concept describing something without any limit
Music
*Infinite (band), a South Korean boy band
*''Infinite'' (EP), debut EP of American mus ...

. Formally, it states that for every indexed family
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...

$(S\_i)\_$ of nonempty
In mathematics, the empty set is the unique Set (mathematics), set having no Element (mathematics), elements; its size or cardinality (count of elements in a set) is 0, zero. Some axiomatic set theories ensure that the empty set exists by includ ...

sets there exists an indexed family $(x\_i)\_$ of elements such that $x\_i\; \backslash in\; S\_i$ for every $i\; \backslash in\; I$. The axiom of choice was formulated in 1904 by Ernst Zermelo
Ernst Friedrich Ferdinand Zermelo (, ; 27 July 187121 May 1953) was a German logic
Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for ...

in order to formalize his proof of the well-ordering theorem
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

.
In many cases, such a selection can be made without invoking the axiom of choice; this is in particular the case if the number of sets is finite, or if a selection rule 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 choice function
A choice function (selector, selection) is a mathematical function
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are c ...

. 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 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 polymath
A polymath ( el, πολυμαθής, , "having learned much"; la, homo universalis, "universal human") is an individual whose know ...

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 selection; this makes it possible to directly define a choice function. For an ''infinite'' collection of pairs of socks (assumed to have no distinguishing features), there is no obvious way to make a function that selects 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
Set theory is the branch of mathematical logic that studies Set (mathematics), 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, i ...

, Zermelo–Fraenkel set theory with the axiom of choice (). One motivation for this use is that a number of generally accepted mathematical results, such as Tychonoff's theorem
In mathematics, Tychonoff's theorem states that the product of any collection of compact space, compact topological spaces is compact with respect to the product topology. The theorem is named after Andrey Nikolayevich Tikhonov (whose surname som ...

, 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 In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and the ...

. The axiom of choice is avoided in some varieties of constructive mathematics
In the philosophy of mathematics, constructivism asserts that it is necessary to find (or "construct") a mathematical object to prove that it exists. In classical mathematics, one can prove the existence of a mathematical object without "finding ...

, although there are varieties of constructive mathematics in which the axiom of choice is embraced.
Statement

Achoice function
A choice function (selector, selection) is a mathematical function
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are c ...

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:
:$\backslash forall\; X\; \backslash left;\; href="/html/ALL/s/\backslash varnothing\_\backslash notin\_X\_\backslash implies\_\backslash exists\_f\_\backslash colon\_X\_\backslash rightarrow\_\backslash bigcup\_X\_\backslash quad\_\backslash forall\_A\_\backslash in\_X\_\backslash ,\_(\_f(A)\_\backslash in\_A\_)\_\backslash right.html"\; ;"title="\backslash varnothing\; \backslash notin\; X\; \backslash implies\; \backslash exists\; f\; \backslash colon\; X\; \backslash rightarrow\; \backslash bigcup\; X\; \backslash quad\; \backslash forall\; A\; \backslash in\; X\; \backslash ,\; (\; f(A)\; \backslash in\; A\; )\; \backslash right">\backslash varnothing\; \backslash notin\; X\; \backslash implies\; \backslash exists\; f\; \backslash colon\; X\; \backslash rightarrow\; \backslash bigcup\; X\; \backslash quad\; \backslash forall\; A\; \backslash in\; X\; \backslash ,\; (\; f(A)\; \backslash in\; A\; )\; \backslash right$
Thus, the negation of the axiom of choice states that there exists a collection of nonempty sets that has no choice function.
Each choice function on a collection ''X'' of nonempty sets is an element of the Cartesian product
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

of the sets in ''X''. This is not the most general situation of a Cartesian product of a family
In human society
A society is a Social group, group of individuals involved in persistent Social relation, social interaction, or a large social group sharing the same spatial or social territory, typically subject to the same Politic ...

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
illustrating the intersection of two sets
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 ...

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'' ofpairwise disjoint
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

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
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities an ...

''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
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities an ...

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 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 bymathematical induction
Mathematical induction is a mathematical proof technique. It is essentially used to prove that a statement ''P''(''n'') holds for every natural number ''n'' = 0, 1, 2, 3, . . . ; that is, the overall statement is a ...

. 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 untilZermelo
Ernst Friedrich Ferdinand Zermelo (, ; 27 July 187121 May 1953) was a German logic
Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for ...

.
Not every situation requires the axiom of choice. For finite sets ''X'', the axiom of choice follows from the other axioms of set theory. In that case it is equivalent to saying that if we have several (a finite number of) boxes, each containing at least one item, then we can choose exactly one item from each box. Clearly we can do this: We start at the first box, choose an item; go to the second box, choose an item; and so on. The number of boxes is finite, so eventually our choice procedure comes to an end. The result is an explicit choice function: a function that takes the first box to the first element we chose, the second box to the second element we chose, and so on. (A formal proof for all finite sets would use the principle of mathematical induction
Mathematical induction is a mathematical proof technique. It is essentially used to prove that a statement ''P''(''n'') holds for every natural number ''n'' = 0, 1, 2, 3, . . . ; that is, the overall statement is a ...

to prove "for every natural number ''k'', every family of ''k'' nonempty sets has a choice function.") This method cannot, however, be used to show that every countable family of nonempty sets has a choice function, as is asserted by the axiom of countable choice
The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom
An axiom, postulate or assumption is a statement that is taken to be truth, true, to serve as a premise or starting point for further reasoning and argumen ...

. If the method is applied to an infinite sequence (''X''Examples

The nature of the individual nonempty sets in the collection may make it possible to avoid the axiom of choice even for certain infinite collections. For example, suppose that each member of the collection ''X'' is a nonempty subset of the natural numbers. Every such subset has a smallest element, so to specify our choice function we can simply say that it maps each set to the least element of that set. This gives us a definite choice of an element from each set, and makes it unnecessary to apply the axiom of choice. The difficulty appears when there is no natural choice of elements from each set. If we cannot make explicit choices, how do we know that our set exists? For example, suppose that ''X'' is the set of all non-empty subsets of thereal number
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...

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 select a point in each orbit requires the axiom of choice. See non-measurable set
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

for more details.
The reason that we are able to choose least elements from subsets of the natural numbers is the fact that the natural numbers are well-order
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

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

A proof requiring the axiom of choice may establish the existence of an object without explicitly defining the object in the language of set theory. For example, while the axiom of choice implies that there is awell-ordering
In mathematics, a well-order (or well-ordering or well-order relation) on a Set (mathematics), 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. The set ''S'' together ...

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 (mathematics), measure theory, a branch of mathematics, the Lebesgue measure, named after france, French mathematician Henri Lebesgue, is the standard way of assigning a measure (mathematics), measure to subsets of ''n''-dimensional Eucli ...

can be proved to exist using the axiom of choice, it is consistent
In classical
Classical may refer to:
European antiquity
*Classical antiquity, a period of history from roughly the 7th or 8th century B.C.E. to the 5th century C.E. centered on the Mediterranean Sea
*Classical architecture, architecture derive ...

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
Canonical may refer to:
Science and technology
* Canonical form
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geo ...

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 formalizes mathematical structure
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and ...

). 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 theory, set-theoretic geometry, which states the following: Given a solid ball (mathematics), ball in 3‑dimensional space, existence theorem, there exists a decomposition of the ball into a finite ...

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
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

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 In logic and mathematics, statements p and q are said to be logically equivalent if they are provable from each other under a set of axioms, or have the same truth value in every model (logic), model. The logical equivalence of p and q is sometimes ...

(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
A model is an informative representation of an object, person or system. The term originally denoted the plan
A plan is typically any diagram or list of steps with details of timing and resources, used to achieve an Goal, objective to do somet ...

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 proof
In mathematics, a constructive proof is a method of mathematical proof, proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object. This is in contrast to a non-constructive proof (also ...

s" in which the existence of an object is proved although no explicit example is constructed. ZFC, however, is still formalized in classical logic. The axiom of choice has also been thoroughly studied in the context of constructive mathematics, where non-classical logic is employed. The status of the axiom of choice varies between different varieties of constructive mathematics.
In Martin-Löf type theory
Intuitionistic type theory (also known as constructive type theory, or Martin-Löf type theory) is a type theory and an alternative Foundations of mathematics, foundation of mathematics.
Intuitionistic type theory was created by Per Martin-Löf, a S ...

and higher-order Heyting arithmeticIn mathematical logic, Heyting arithmetic (sometimes abbreviated HA) is an axiomatization of arithmetic in accordance with the philosophy of intuitionism.Troelstra 1973:18 It is named after Arend Heyting, who first proposed it.
Introduction
Heyting ...

, the appropriate statement of the axiom of choice is (depending on approach) included as an axiom or provable as a theorem. Errett Bishop
Errett Albert Bishop (July 14, 1928 – April 14, 1983) was an Americans, American mathematician known for his work on analysis. He expanded constructive analysis in his 1967 ''Foundations of Constructive Analysis'', where he Mathematical proof, p ...

argued that the axiom of choice was constructively acceptable, saying
In constructive set theory
Constructive set theory is an approach to mathematical constructivism
In the philosophy of mathematics
Philosophy (from , ) is the study of general and fundamental questions, such as those about reason
Reason is the capacity of consc ...

, however, Diaconescu's theoremIn 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 197 ...

shows that the axiom of choice implies the law of excluded middle
In logic
Logic is an interdisciplinary field which studies truth and reasoning
Reason is the capacity of consciously making sense of things, applying logic
Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, la ...

(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
In logic
Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for instance by listing varieties of fallacies. Formal logic represents stateme ...

properties that the axiom of choice in constructive set theory does.
Some results in constructive set theory use the axiom of countable choice
The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom
An axiom, postulate or assumption is a statement that is taken to be truth, true, to serve as a premise or starting point for further reasoning and argumen ...

or the axiom of dependent choice In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and the ...

, 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
Kurt Friedrich Gödel ( , ; April 28, 1906 – January 14, 1978) was a logician
Logic is an interdisciplinary field which studies truth
Truth is the property of being in accord with fact or reality.Merriam-Webster's Online Dict ...

showed that the ''negation'' of the axiom of choice is not a theorem of ZF by constructing an inner model
In set theory, a branch of mathematical logic, an inner model for a Theory (mathematical logic), theory ''T'' is a substructure (mathematics), substructure of a model (mathematical logic), model ''M'' of a set theory that is both a model for ''T'' ...

(the constructible universe
In mathematics, in set theory, the constructible universe (or Gödel's constructible universe), denoted by , is a particular Class (set theory), class of Set (mathematics), sets that can be described entirely in terms of simpler sets. is the union ...

) which satisfies ZFC and thus showing that ZFC is consistent if ZF itself is consistent. In 1963, Paul Cohen
Paul Joseph Cohen (April 2, 1934 – March 23, 2007) was an American mathematician
A mathematician is someone who uses an extensive knowledge of mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers ( and ...

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 independentIn mathematical logic
Mathematical logic, also called formal logic, is a subfield of mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algeb ...

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: every ideal
Ideal may refer to:
Philosophy
* Ideal (ethics)
An ideal is a principle
A principle is a proposition or value that is a guide for behavior or evaluation. In law
Law is a system
A system is a group of Interaction, interacting ...

in a ring is contained in a maximal ideal
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...

, every vector space
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

has a basis
Basis may refer to:
Finance and accounting
*Adjusted basisIn tax accounting, adjusted basis is the net cost of an asset after adjusting for various tax-related items.
Adjusted Basis or Adjusted Tax Basis refers to the original cost or other b ...

, and every product
Product may refer to:
Business
* Product (business)
In marketing, a product is an object or system made available for consumer use; it is anything that can be offered to a Market (economics), market to satisfy the desire or need of a customer ...

of compact space
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

s is compact. Without the axiom of choice, these theorems may not hold for mathematical objects of large cardinality.
The proof of the independence result also shows that a wide class of mathematical statements, including all statements that can be phrased in the language of Peano arithmetic
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian people, Italian mathematician Giuseppe Peano. These axioms have been ...

, are provable in ZF if and only if they are provable in ZFC. Statements in this class include the statement that P = NP
The P versus NP problem is a major List of unsolved problems in computer science, unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified can also be solved quickly.
The informal term ''quick ...

, the Riemann hypothesis
In mathematics, the Riemann hypothesis is a conjecture
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces ...

, 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
In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states:
In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this is equivalent to the following equation in a ...

(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

Theaxiom of constructibility
The axiom of constructibility is a possible axiom
An axiom, postulate or assumption is a statement that is taken to be truth, true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Greek ''ax ...

and the generalized continuum hypothesis
In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states:
In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this is equivalent to the following equation in a ...

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
In the foundations of mathematics
Foundations of mathematics is the study of the philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philosophical theorie ...

and Morse–Kelley set theory In the foundations of mathematics, Morse–Kelley set theory (MK), Kelley–Morse set theory (KM), Morse–Tarski set theory (MT), Quine–Morse set theory (QM) or the system of Quine and Morse is a first-order logic, first-order axiomatic set theor ...

, there is an axiom called the axiom of global choice In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and the ...

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
In set theory, the axiom of limitation of size was proposed by John von Neumann in his 1925 axiom system for Set (mathematics), sets and Class (set theory), classes.; English translation: . It formalizes the limitation of size principle, which avo ...

. Tarski's axiom, which is used in Tarski–Grothendieck set theory and states (in the vernacular) that every set belongs to Grothendieck universe In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and the ...

, 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 areZorn's lemma
Zorn's lemma, also known as the Kuratowski–Zorn lemma, after mathematicians Max August Zorn, Max Zorn and Kazimierz Kuratowski, is a proposition of set theory. It states that a partially ordered set containing upper bounds for every chain (or ...

and the well-ordering theorem
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

. 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 Set (mathematics), 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, i ...

**Well-ordering theorem
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

: Every set can be well-ordered. Consequently, every cardinal
Cardinal or The Cardinal may refer to:
Christianity
* Cardinal (Catholic Church), a senior official of the Catholic Church
* Cardinal (Church of England), two members of the College of Minor Canons of St. Paul's Cathedral
Navigation
* Cardin ...

has an initial ordinal
The von Neumann Von Neumann may refer to:
* John von Neumann (1903–1957), a Hungarian American mathematician
* Von Neumann family
* Von Neumann (surname), a German surname
* Von Neumann (crater), a lunar impact crater
See also
* Von Neumann al ...

.
**Tarski's theorem about choice In mathematics, Tarski's theorem, proved by , states that in Zermelo–Fraenkel set theory, ZF the theorem "For every infinite set A, there is a bijective map between the sets A and A\times A" implies the axiom of choice. The opposite direction was ...

: For every infinite set ''A'', there is a bijective map
In mathematics, a bijection, bijective function, one-to-one correspondence, or invertible function, is a function (mathematics), function between the elements of two set (mathematics), sets, where each element of one set is paired with exactly on ...

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.
**The Cartesian product
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

of any family of nonempty sets is nonempty.
** König's theorem: Colloquially, the sum of a sequence of cardinals is strictly less than the product of a sequence of larger cardinals. (The reason for the term "colloquially" is that the sum or product of a "sequence" of cardinals cannot be defined without some aspect of the axiom of choice.)
**Every surjective function
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

has a right inverse.
*Order theory
Order theory is a branch of mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geom ...

**Zorn's lemma
Zorn's lemma, also known as the Kuratowski–Zorn lemma, after mathematicians Max August Zorn, Max Zorn and Kazimierz Kuratowski, is a proposition of set theory. It states that a partially ordered set containing upper bounds for every chain (or ...

: 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
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and t ...

: In any partially ordered set, every totally ordered subset is contained in a maximal totally ordered subset. The restricted principle "Every partially ordered set has a maximal totally ordered subset" is also equivalent to AC over ZF.
** Tukey's lemma: Every non-empty collection of finite character has a maximal element with respect to inclusion.
**Antichain In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and the ...

principle: Every partially ordered set has a maximal antichain In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and the ...

.
*Abstract algebra
In algebra, which is a broad division of mathematics, abstract algebra (occasionally called modern algebra) is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics), rings, field (mathema ...

**Every vector space
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities a ...

has a basis
Basis may refer to:
Finance and accounting
*Adjusted basisIn tax accounting, adjusted basis is the net cost of an asset after adjusting for various tax-related items.
Adjusted Basis or Adjusted Tax Basis refers to the original cost or other b ...

.
**Krull's theorem In mathematics, and more specifically in ring theory, Krull's theorem, named after Wolfgang Krull, asserts that a zero ring, nonzero ring (mathematics), ring has at least one maximal ideal. The theorem was proved in 1929 by Krull, who used transfin ...

: Every unital ring
Ring most commonly refers either to a hollow circular shape or to a high-pitched sound. It thus may refer to:
*Ring (jewellery), a circular, decorative or symbolic ornament worn on fingers, toes, arm or neck
Ring may also refer to:
Sounds
* Ri ...

other than the trivial ring contains a maximal ideal
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and th ...

.
**For every non-empty set ''S'' there is a binary operation
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

defined on ''S'' that gives it a group structure. (A cancellative
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...

binary operation is enough, see group structure and the axiom of choice.)
**Every set is a projective object in the Category (mathematics), category Category of sets, Set of sets.
*Functional analysis
**The closed unit ball of the dual of a normed vector space over the reals has an extreme point.
*Point-set topology
**Tychonoff's theorem
In mathematics, Tychonoff's theorem states that the product of any collection of compact space, compact topological spaces is compact with respect to the product topology. The theorem is named after Andrey Nikolayevich Tikhonov (whose surname som ...

: Every product topology, product of Compact space, compact topological spaces is compact.
**In the product topology, the closure (topology), closure of a product of subsets is equal to the product of the closures.
*Mathematical logic
**If ''S'' is a set of sentences of first-order logic and ''B'' is a consistent subset of ''S'', then ''B'' is included in a set that is maximal among consistent subsets of ''S''. The special case where ''S'' is the set of all first-order sentences in a given signature (logic), signature is weaker, equivalent to the Boolean prime ideal theorem; see the section "Weaker forms" below.
*Graph theory
**Every connected graph has a spanning tree.
Category theory

There are several results incategory theory
Category theory formalizes mathematical structure
In mathematics
Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and ...

which invoke the axiom of choice for their proof. These results might be weaker than, equivalent to, or stronger than the axiom of choice, depending on the strength of the technical foundations. For example, if one defines categories in terms of sets, that is, as sets of objects and morphisms (usually called a small category), or even locally small categories, whose hom-objects are sets, then there is no category of sets, category of all sets, and so it is difficult for a category-theoretic formulation to apply to all sets. On the other hand, other foundational descriptions of category theory are considerably stronger, and an identical category-theoretic statement of choice may be stronger than the standard formulation, à la class theory, mentioned above.
Examples of category-theoretic statements which require choice include:
*Every small category (mathematics), category has a skeleton (category theory), skeleton.
*If two small categories are weakly equivalent, then they are equivalence of categories, equivalent.
*Every continuous functor on a small-complete category which satisfies the appropriate solution set condition has a adjoint functors, left-adjoint (the Freyd adjoint functor theorem).
Weaker forms

There are several weaker statements that are not equivalent to the axiom of choice, but are closely related. One example is theaxiom of dependent choice In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and the ...

(DC). A still weaker example is the axiom of countable choice
The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom
An axiom, postulate or assumption is a statement that is taken to be truth, true, to serve as a premise or starting point for further reasoning and argumen ...

(ACResults 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 Set (mathematics), 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, i ...

**The ultrafilter lemma (with ZF) can be used to prove the Axiom of choice for finite sets: Given $I\; \backslash neq\; \backslash varnothing$ and a collection $\backslash left(X\_i\backslash right)\_$ of non-empty sets, their product $\backslash prod\_\; X\_$ is not empty.
**Any union (set theory), union of countably many countable sets is itself countable (because it is necessary to choose a particular ordering for each of the countably many sets).
**If the set ''A'' is infinite set, infinite, then there exists an injective function, injection from the natural numbers N to ''A'' (see Dedekind infinite).
**Eight definitions of a finite set#Other concepts of finiteness, finite set are equivalent.
**Every infinite determinacy#Basic notions, game $G\_S$ in which $S$ is a Borel set, Borel subset of Baire space (set theory), Baire space is determinacy#Basic notions, determined.
*Measure theory
**The Vitali set, Vitali theorem on the existence of non-measurable set
In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and ...

s which states that there is a subset of the real numbers that is not Lebesgue measurable.
**The Hausdorff paradox.
**The Banach–Tarski paradox
The Banach–Tarski paradox is a theorem in set theory, set-theoretic geometry, which states the following: Given a solid ball (mathematics), ball in 3‑dimensional space, existence theorem, there exists a decomposition of the ball into a finite ...

.
**The Lebesgue measure of a countable disjoint union of measurable sets is equal to the sum of the measures of the individual sets.
*Algebra
**Every field (mathematics), field has an algebraic closure.
**Every field extension has a transcendence basis.
**Stone's representation theorem for Boolean algebras needs the Boolean prime ideal theorem.
**The Nielsen–Schreier theorem, that every subgroup of a free group is free.
**The additive groups of real numbers, R and complex number, C are isomorphic.
*Functional analysis
**The Hahn–Banach theorem in functional analysis, allowing the extension of linear map, linear functionals
**The theorem that every Hilbert space has an orthonormal basis.
**The Banach–Alaoglu theorem about compactness of sets of functionals.
**The Baire category theorem about complete space, complete metric spaces, and its consequences, such as the open mapping theorem (functional analysis), open mapping theorem and the closed graph theorem.
**On every infinite-dimensional topological vector space there is a discontinuous linear map.
*General topology
**A uniform space is compact if and only if it is complete and totally bounded.
**Every Tychonoff space has a Stone–Čech compactification.
*Mathematical logic
**Gödel's completeness theorem for first-order logic: every consistent set of first-order sentences has a completion. That is, every consistent set of first-order sentences can be extended to a maximal consistent set.
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 Set (mathematics), 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, i ...

**Partition principle: if there is a Surjective function, surjection from ''A'' to ''B'', there is an Injective function, injection from ''B'' to ''A''. Equivalently, every Partition of a set, partition ''P'' of a set ''S'' is less than or equal to ''S'' in size.
**Converse Schröder–Bernstein theorem: if two sets have surjections to each other, they are equinumerous.
**Weak partition principle: 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 algebra, which is a broad division of mathematics, abstract algebra (occasionally called modern algebra) is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics), rings, field (mathema ...

**Hahn embedding theorem: Every ordered abelian group ''G'' order-embeds as a subgroup of the additive group $\backslash mathbb^\backslash Omega$ endowed with a lexicographical order, where Ω is the set of Archimedean equivalence classes of Ω. 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; however, this consistency result, due to Robert M. Solovay, cannot be proved in ZFC itself, but requires a mild large cardinal assumption (the existence of an inaccessible cardinal). The much strongeraxiom of determinacy In mathematics
Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and the ...

, 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. *In some model, 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 Sequential continuity, sequentially continuous at ''a'', i.e., for any sequence converging to ''a'', limBanach–Tarski paradox
The Banach–Tarski paradox is a theorem in set theory, set-theoretic geometry, which states the following: Given a solid ball (mathematics), ball in 3‑dimensional space, existence theorem, there exists a decomposition of the ball into a finite ...

which are provable in ZFC. Furthermore, this is possible whilst assuming the Axiom of dependent choice, which is weaker than AC but sufficient to develop most of real analysis.
*In all models of ZF¬C, the generalized continuum hypothesis does not hold.
For proofs, see .
Additionally, by imposing definability conditions on sets (in the sense of descriptive set theory) one can often prove restricted versions of the axiom of choice from axioms incompatible with general choice. This appears, for example, in the Moschovakis coding lemma.
Axiom of choice in type theory

In type theory, a different kind of statement is known as the axiom of choice. This form begins with two types, σ and τ, and a relation ''R'' between objects of type σ and objects of type τ. The axiom of choice states that if for each ''x'' of type σ there exists a ''y'' of type τ such that ''R''(''x'',''y''), then there is a function ''f'' from objects of type σ to objects of type τ such that ''R''(''x'',''f''(''x'')) holds for all ''x'' of type σ: :$(\backslash forall\; x^\backslash sigma)(\backslash exists\; y^\backslash tau)\; R(x,y)\; \backslash to\; (\backslash exists\; f^)(\backslash forall\; x^\backslash sigma)\; R(x,f(x)).$ Unlike in set theory, the axiom of choice in type theory is typically stated as an axiom scheme, in which ''R'' varies over all formulas or over all formulas of a particular logical form.Quotes

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 by stating for example, to choose a 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. 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 article in the ''computer recreations'' column of the ''Scientific American'', April 1989.Notes

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 reprint, 2013, . * *Herman Rubin, Jean E. Rubin: Equivalents of the axiom of choice. North Holland, 1963. Reissued by Elsevier, 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, 2003. * *Ernst Zermelo
Ernst Friedrich Ferdinand Zermelo (, ; 27 July 187121 May 1953) was a German logic
Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for ...

, "Untersuchungen über die Grundlagen der Mengenlehre I," ''Mathematische Annalen 65'': (1908) pp. 261–81PDF download via digizeitschriften.de

::Translated in: Jean van Heijenoort, 2002. ''From Frege to Gödel: A Source Book in Mathematical Logic, 1879–1931''. New edition. Harvard University Press. ::*1904. "Proof that every set can be well-ordered," 139-41. ::*1908. "Investigations in the foundations of set theory I," 199–215.

External links

Axiom of Choice

entry in the Springer Encyclopedia of Mathematics.

Axiom of Choice and Its Equivalents

entry at ProvenMath. Includes formal statement of the Axiom of Choice, Hausdorff's Maximal Principle, Zorn's Lemma and formal proofs of their equivalence down to the finest detail.

based on the book b

Paul Howard

and Jean Rubin. *. {{DEFAULTSORT:Axiom Of Choice Axiom of choice,