Concept

Axiom of choice

Overview

In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of non-empty sets, one can identify another set containing one element chosen from each set, even if the collection is infinite. Formally, the axiom establishes existence rather than a construction; it states that for every set

I

{\displaystyle I}

and every

I

{\displaystyle I}

-indexed family

(

S

i

)

i

∈

I

{\displaystyle (S_{i})_{i\in I}}

of nonempty sets, there exists an

I

{\displaystyle I}

-indexed set

(

x

i

)

i

∈

I

{\displaystyle (x_{i})_{i\in I}}

of elements of

∪

i

∈

I

S

i

{\displaystyle \cup _{i\in I}S_{i}}

such that

x

i

∈

S

i

{\displaystyle x_{i}\in S_{i}}

for every

i

∈

I

{\displaystyle i\in I}

. The axiom of choice was formulated in 1904 by Ernst Zermelo in order to formalize his proof of the well-ordering theorem.

In many cases, a set created by choosing elements can be made without invoking the axiom of choice, particularly if the number of sets from which to choose the elements is finite (in which induction can be applied), or if a canonical rule on how to choose the elements is available – some distinguishing property that happens to hold for exactly one element in each set. An illustrative example is sets picked from the natural numbers. From such sets, one may always select the smallest number, e.g. given the sets {{4, 5, 6}, {10, 12}, {1, 400, 617, 8000}}, the set containing each smallest element is {4, 10, 1}. In this case, "select the smallest number" is a choice function. Even if infinitely many sets are collected from the natural numbers, it will always be possible to form a choice function from choosing the smallest element from each set to produce a set; the axiom of choice is not needed here. On the other hand, for the collection of all non-empty subsets of the real numbers, there is no known canonical rule by which one can choose one element from each of these subsets. In that case, the axiom of choice must be invoked to construct the desired choice function.

Bertrand Russell coined an analogy: for any (even infinite) collection of unordered pairs of shoes, one can pick out the left shoe from each pair to obtain an appropriate collection (i.e. set) of shoes; this makes it possible to define a choice function without using the axiom of choice. However, for an infinite collection of unordered pairs of socks (assumed to have no distinguishing features such as being a left sock rather than a right sock), there is no natural (i.e., canonical) way of choosing one sock from each pair, so one must appeal to the axiom of choice to construct the desired choice function.

Although originally controversial, the axiom of choice is now used without reservation by most mathematicians, and is included in the standard form of axiomatic set theory, Zermelo–Fraenkel set theory with the axiom of choice (ZFC). One motivation for this is that a number of generally accepted mathematical results, such as Tychonoff's theorem, require the axiom of choice for their proofs. Contemporary set theorists also study axioms that are not compatible with the axiom of choice, such as the axiom of determinacy. While some varieties of constructive mathematics avoid the axiom of choice, others embrace it.

Overview adapted from Wikipedia (CC BY-SA 4.0; see the article history for authors).

Possible passages

Found by search and not yet checked by a person; they may only mention the idea in passing.

1. The notion of a limit, which is fundamental in the greater part of higher mathematics, used to be defined by means of quantity, as a term to which the terms of some series approximate as nearly as we please. But nowadays the limit is defined quite differently, and the series which it limits may not approximate to it at all. This improvement also is due to Cantor, and it is one which has revolutionised mathematics…

   Bertrand Russell, Mysticism and Logic and Other Essays

   States what Axiom of choice is; the author is tied to Axiom of choice in the knowledge graph.

   Read the chapter · Open in the reader

2. Congruence was to refer to geometrical bodies, with none of the properties of ordinary bodies except impenetrability (Erdmann, Axiome der Geometrie, p. 26). A straight line is defined as determined by two of its points[14], and a plane as determined by three. These premisses, with a slight exception as to the straight line, we shall hereafter find essential to every Geometry. I have drawn attention to them, as it is…

   Bertrand Russell, An essay on the foundations of geometry

   States what Axiom of choice is; the author is tied to Axiom of choice in the knowledge graph.

   Read the chapter · Open in the reader

3. Thus there arises a classification of modes of formation, or in the language commonly used by mathematicians, a classification of Functions. Any number, considered as formed from any other number, is called a function of it; and there are as many kinds of functions as there are modes of formation. The simple functions are by no means numerous, most functions being formed by the combination of several of the…

   John Stuart Mill, A System of Logic, Ratiocinative and Inductive

   States what Axiom of choice is.

   Read the chapter · Open in the reader

Philosophers who discussed Axiom of choice

• Kurt Gödel
• Willard Van Orman Quine
• Alain Badiou
• John Lane Bell

Related ideas

• First-order logic
• Independence (mathematical logic)
• Finite set
• Gödel's completeness theorem
• Infinite set
• Compactness theorem
• Zermelo–Fraenkel set theory
• Kurt Gödel
• Logical equivalence
• Law of excluded middle
• Ernst Zermelo
• Propositional logic
• Mathematics
• Per Martin-Löf
• Group (mathematics)
• Mathematical logic
• Model theory
• Real number
• Constructivism (philosophy of mathematics)
• Sentence (mathematical logic)
• Power set
• Peano axioms
• Set theory
• Willard Van Orman Quine

Place in the tradition

Part of Analytic philosophy.

Explore Axiom of choice in the interactive graph →