axiom of choice


The Zermelo-Fraenkel axiomsMathworldPlanetmath for set theoryMathworldPlanetmath are often accepted as a basis for an axiomatic set theory. On the other hand, the axiom of choiceMathworldPlanetmath is somewhat controversial, and it is currently segregated from the ZF system of set theory axioms. When the axiom of choice is combined with the ZF axioms, the whole axiom system is called “ZFC” (for “Zermelo-Fraenkel with Choice”).

Axiom (Axiom of choice).

Let C be a set of nonempty sets. Then there exists a function

f:CSCS

such that f(x)x for all xC.

The function f is sometimes called a choice function on C.

For finite setsMathworldPlanetmath C, a choice function can be constructed without appealing to the axiom of choice. In particular, if C=, then the choice function is clear: it is the empty setMathworldPlanetmath! It is only for infiniteMathworldPlanetmath (and usually uncountable) sets C that the existence of a choice function becomes an issue. Here one can see why it is not considered “obvious” and always taken for an axiom by everyone: one really cannot imagine any process which makes uncountably many selections without also imagining some rule for making the selections. Given such a rule, the axiom of choice is not needed. Thus, objects that are proved to exist using the axiom of choice cannot generally be described by any kind of systematic rule, for if they could it would not be necessary to their construction.

Let us consider a couple of examples. Imagine that there are infinitely many pairs of shoes (each consisting of one left shoe and one right shoe). Let 𝒫 denote the set of all pairs of shoes. In this scenario, it can be verified that the function f:𝒫𝒫 defined by f(P)= the left shoe of P is a choice function. Similarly, imagine that there are infinitely many pairs of socks. Let 𝒮 denote the set of all pairs of socks. In this scenario, one cannot assume that a function g:𝒮𝒮 exists without appealing to the axiom of choice (or something equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath to it). Note that this scenario cannot be resolved in the same manner as the previous scenario because most people do not a ”left sock” and a ”right sock”.

Strange objects that can be constructed using the axiom of choice include non-measurable sets (leading to the http://planetmath.org/node/7057HausdorffPlanetmathPlanetmath and http://planetmath.org/node/4464Banach-Tarski paradoxa), and Hamel bases for any vector spaceMathworldPlanetmath. A Hamel basisMathworldPlanetmath may not seem strange, but try to imagine a set S of continuous functionsMathworldPlanetmathPlanetmath such that every continuous function can be expressed uniquely as a linear combinationMathworldPlanetmath of finitely many elements of S. Since in fact the existence of a basis for every vector space is equivalent to the axiom of choice, it is almost guaranteed that no such set S can ever be described. It is for this reason that some mathematicians dislike the axiom of choice.

On the other hand, many very useful facts can be proven using the axiom of choice. For example, the fact that every vector space has a basis, every ring with identity element 10 has a maximal idealMathworldPlanetmathPlanetmath and many other algebraic theorems which are difficult or impossible to prove without using the axiom of choice.

In pure set theory, the axiom of choice is only relevant where most people’s intuition more or less breaks down, when dealing with hierarchies of uncountable infinitiesMathworldPlanetmath.

The relevance of the axiom of choice to various of mathematics has led to a detailed study of its truth. It turns out that if the Zermelo-Fraenkel axioms are consistentPlanetmathPlanetmath, then they remain consistent upon adding the axiom of choice. But they also remain consistent upon adding the negationMathworldPlanetmath of the axiom of choice (see [G] and [C]).

Some mathematicians have suggested an axiom that would result in all subsets of the real numbers being measurable; this would of course imply the negation of the axiom of choice.

There are many alternative formulations of the axiom of choice, although it is not always trivial to prove . These include:

  • The generalized Cartesian product of a non-empty family of sets is non-empty iff every set is non-empty. Due to this equivalence the axiom of choice is sometimes called the multiplicative axiom (http://planetmath.org/node/11514Proof).

  • Every relationMathworldPlanetmathPlanetmath R is a union of functions with the same domain as R (http://planetmath.org/node/8763Proof).

  • Every ring with identity element 10 has a maximal ideal (http://planetmath.org/node/4713Proof).

  • Every surjection is a retractionMathworldPlanetmath (http://planetmath.org/TypesOfMorphisms) (http://planetmath.org/node/11517Proof).

  • Every tree has a branch.

  • Every vector space has a basis (for AC implying existence of vector bases, see http://planetmath.org/node/3494here, and its converseMathworldPlanetmath, proved by Andreas Blass in 1984, http://www.math.lsa.umich.edu/ ablass/bases-AC.pdfhere).

  • Given any two sets, there exists an injection from one to another (http://planetmath.org/node/11645Proof).

  • Hausdorff’s maximum principle (http://planetmath.org/node/3493Proof).

  • http://planetmath.org/node/5598König’s theorem.

  • Kuratowski’s lemma (http://planetmath.org/node/11512Proof).

  • Tukey’s lemma (http://planetmath.org/node/4672Proof).

  • TychonoffPlanetmathPlanetmath’s theorem (for AC implying Tychonoff, see http://planetmath.org/node/9797here, and its converse http://planetmath.org/node/11540here).

  • Zermelo’s postulateMathworldPlanetmath (http://planetmath.org/node/8342Proof).

  • Zermelo’s well-ordering theorem (http://planetmath.org/node/3493Proof).

  • Zorn’s lemma (http://planetmath.org/node/3358Proof).

Figure 1 shows how these equivalences are proven on PlanetMath.

Figure 1: StructureMathworldPlanetmath of the equivalence proofs on PlanetMath. The abbreviations are explained in table 1. An arrow AB means that “A implies B” is proven on PlanetMath.
AC Axiom of Choice
Hamel Every vector space has a basis
Hausdorff Hausdorff’s maximum principle
König König’s theorem
Krull Every ring with identity element 10 has a maximal ideal
Tukey Tukey’s lemma
Well Zermelo’s well-ordering theorem (http://planetmath.org/ZermelosWellOrderingTheorem)
Zorn Zorn’s lemma
Table 1: Abbreviations

References

  • C P. J. Cohen, The independence of the continuum hypothesisMathworldPlanetmath. I, II, Proc. Natl. Acad. Sci. USA 50, 1143–1148 (1963); 51, 105–110 (1964).
  • G K. Gödel, The consistency of the axiom of choice and of the generalized continuum-hypothesis, Proc. Natl. Acad. Sci. USA 24, 556–557 (1938).
Title axiom of choice
Canonical name AxiomOfChoice
Date of creation 2013-03-22 11:47:42
Last modified on 2013-03-22 11:47:42
Owner GrafZahl (9234)
Last modified by GrafZahl (9234)
Numerical id 43
Author GrafZahl (9234)
Entry type Axiom
Classification msc 03E30
Classification msc 03E25
Synonym multiplicative axiom
Related topic MaximalityPrinciple
Related topic ZermeloFraenkelAxioms
Related topic ContinuumHypothesis
Related topic GeneralizedContinuumHypothesis
Related topic HaudorffsMaximumPrinciple
Related topic ZornsLemmaAndTheWellOrderingTheoremEquivalenceOfHaudorffsMaximumPrinciple
Related topic EveryVectorSpaceHasABasis
Related topic TukeysLemma
Related topic ZermelosPostulat