Axiom of Choice

Also found in: Dictionary, Acronyms, Wikipedia.

axiom of choice

[¦ak·sē·əm əv ′chȯis]
The axiom that for any family A of sets there is a function that assigns to each set S of the family A a member of S.
McGraw-Hill Dictionary of Scientific & Technical Terms, 6E, Copyright © 2003 by The McGraw-Hill Companies, Inc.

Axiom of Choice

(AC, or "Choice") An axiom of set theory:

If X is a set of sets, and S is the union of all the elements of X, then there exists a function f:X -> S such that for all non-empty x in X, f(x) is an element of x.

In other words, we can always choose an element from each set in a set of sets, simultaneously.

Function f is a "choice function" for X - for each x in X, it chooses an element of x.

Most people's reaction to AC is: "But of course that's true! From each set, just take the element that's biggest, stupidest, closest to the North Pole, or whatever". Indeed, for any finite set of sets, we can simply consider each set in turn and pick an arbitrary element in some such way. We can also construct a choice function for most simple infinite sets of sets if they are generated in some regular way. However, there are some infinite sets for which the construction or specification of such a choice function would never end because we would have to consider an infinite number of separate cases.

For example, if we express the real number line R as the union of many "copies" of the rational numbers, Q, namely Q, Q+a, Q+b, and infinitely (in fact uncountably) many more, where a, b, etc. are irrational numbers no two of which differ by a rational, and

Q+a == q+a : q in Q

we cannot pick an element of each of these "copies" without AC.

An example of the use of AC is the theorem which states that the countable union of countable sets is countable. I.e. if X is countable and every element of X is countable (including the possibility that they're finite), then the sumset of X is countable. AC is required for this to be true in general.

Even if one accepts the axiom, it doesn't tell you how to construct a choice function, only that one exists. Most mathematicians are quite happy to use AC if they need it, but those who are careful will, at least, draw attention to the fact that they have used it. There is something a little odd about Choice, and it has some alarming consequences, so results which actually "need" it are somehow a bit suspicious, e.g. the Banach-Tarski paradox. On the other side, consider Russell's Attic.

AC is not a theorem of Zermelo Fr?nkel set theory (ZF). G?del and Paul Cohen proved that AC is independent of ZF, i.e. if ZF is consistent, then so are ZFC (ZF with AC) and ZF(~C) (ZF with the negation of AC). This means that we cannot use ZF to prove or disprove AC.
This article is provided by FOLDOC - Free Online Dictionary of Computing (
References in periodicals archive ?
Integrating the money commodity in the domain of the world of commodities is possible via the right inverse, implicitly admitting the axiom of choice. The question is how to choose the most appropriate commodity from all the potential commodities serving as money.
The axiom of choice is firmly entrenched in the body of mathematics.
(21) For the controversial status of the axiom of choice among other axioms of set theory, see Yiannis Moschovakis, Notes on Set Theory (New York: Springer, 2006).
Concerning the theorems mentioned above, the Axiom of Choice turns out to be indeed necessary: In section 4, we construct transitive models of Zermelo-Fraenkel set theory without the Axiom of Choice (ZF) containing a real closed field K, but no integer part of K.
(14) On the other hand, John Byl, who opts for mathematical realism, attempts to ground a portion of mathematics--including the law of noncontradiction, the axiom of choice, and notions of a completed infinity--on attributes of God found in the scriptures.
What is so intriguing about the Axiom of Choice for our discussion of the possible worlds of drama and performance is its position on ontology.
The BT paradox is one of many point-set paradoxes that cannot be proved without the axiom of choice. Cohen was able to show that a consistent set theory may include or exclude the axiom of choice.
Hintikka holds that the relevant version of the axiom of choice is (or should be) unproblematic in constructive contexts.
KEYWORDS: Badiou; Axiom of Choice; Subject; Individual; Non-constructible Sets; Temporality
The axiom of choice (AC) states that for any partition of a set into disjoint nonempty pieces there exists a function picking an element from each piece.
Logically, the book is tour de force, and yet does notoverburden the reader with needless symbolism or undue technical complexity (notwithstanding the crucial role which the Axiom of Choice plays in the formal argument).
His argument relies on the Banach-Tarski paradox, namely that given the orthodoxy and the Axiom of Choice it can be shown that a spherical region of unit radius is the sum of rive regions each congruent to rive regions whose sure is two spheres of unit radius.