The axiom of choice (AC) is an axiom of set theory asserting that, for any set-indexed family of nonempty sets, there exists a function selecting one element from each set. It guarantees the existence of a simultaneous selection even when no explicit selection rule is specified. Adding AC to Zermelo–Fraenkel set theory (ZF) produces the system called ZFC. Choice connects foundational questions about infinite sets with existence theorems throughout mathematics. (math.vanderbilt.edu)
Formal statement and interpretation
Let (I) be a set and ((A_i){i\in I}) a family of nonempty sets. AC states that there exists a function [ f:I\longrightarrow\bigcup{i\in I}A_i ] such that [ f(i)\in A_i\qquad\text{for every }i\in I. ] Such an (f) is called a choice function. The sets need not be disjoint, and different indices may designate the same set. Equivalently, every Cartesian product of nonempty sets is nonempty: an element of the product is precisely a simultaneous assignment of one member to each factor. (math.vanderbilt.edu)
The word “choice” does not describe a temporal process, a random selection, or a computational procedure. The axiom asserts existence, not uniqueness, and does not supply an algorithm for finding the selected elements. An individual application may nevertheless have an explicit choice function; in that case, invoking AC is unnecessary. (math.vanderbilt.edu)
For a finite family, the existence of a choice function is provable in ZF. Infinitely many selections may also be possible without AC when a uniform rule is available. For example, from every nonempty subset of the natural numbers, one can select its least member. The issue is therefore not infinity alone, but selection from arbitrary families lacking a supplied rule. (sites.lsa.umich.edu)
Equivalent principles
Several differently worded statements are equivalent to AC over ZF: each can be proved from AC, and each, if added to ZF, implies AC. Three particularly important formulations are these: (people.math.ethz.ch)
- Well-ordering theorem: Every set admits a total order in which every nonempty subset has a least element. The order need not resemble an order already associated with that set.
- Zorn’s lemma: A nonempty partially ordered set has a maximal element if every chain has an upper bound in the set. A chain is a subset whose elements are pairwise comparable; a maximal element need not be greater than every other element.
- Splitting of surjections: Every surjective function (p:X\to Y) has a right inverse (s:Y\to X), satisfying (p(s(y))=y). Such an inverse chooses one element from each fiber (p^{-1}({y})). (people.math.ethz.ch)
These formulations offer different proof techniques. Well-ordering permits constructions proceeding through an ordered set, while Zorn’s lemma establishes the existence of an object that cannot be enlarged while preserving specified properties. (people.math.ethz.ch)
Mathematical applications
In linear algebra, AC implies that every vector space over a field has a basis. A standard proof applies Zorn’s lemma to the partially ordered collection of linearly independent subsets. A maximal independent subset spans the space, because otherwise another vector could be added. The universal assertion that every vector space has a basis is itself equivalent to AC over ZF. (people.math.ethz.ch)
In topology, Tychonoff’s theorem states that an arbitrary product of compact spaces is compact in the product topology. In this unrestricted form, it is equivalent to AC. Choice also supports extension arguments in functional analysis, notably proofs of the Hahn–Banach theorem. However, being a consequence of AC does not automatically make a theorem equivalent to it. (people.math.ethz.ch)
Choice has less intuitive consequences in measure theory and geometry. It yields subsets of the real line that are not measurable with respect to Lebesgue measure. It also enables the Banach–Tarski paradox: a solid ball in three-dimensional Euclidean space can be partitioned into finitely many sets and reassembled by rigid motions into two balls congruent to the original. These pieces are not ordinary physical fragments; their nonmeasurability prevents the usual volume-additivity argument from applying. (publish.uwo.ca)
History and independence
Ernst Zermelo explicitly formulated AC in 1904 while proving that every set can be well-ordered. The resulting debate concerned whether an existence proof could legitimately depend on simultaneous selections for which no particular rule had been given. (publish.uwo.ca)
Kurt Gödel announced a relative-consistency result in 1938: if ZF is consistent, adding AC does not introduce a contradiction. His method used the constructible universe, an inner universe of sets satisfying choice. In 1963, Paul Cohen established the complementary independence result using methods associated with forcing and models in which choice fails. (pmc.ncbi.nlm.nih.gov)
Together, these results show that, assuming ZF is consistent, neither AC nor its negation is provable from ZF. They do not establish the absolute consistency of ZF itself. Omitting AC also differs from asserting its negation: ZF alone leaves the question unsettled. (pmc.ncbi.nlm.nih.gov)
Restricted choice principles
Weaker principles restrict the families or selections under consideration. The axiom of countable choice asserts the existence of a choice function for every family of nonempty sets indexed by a countable set. Full AC implies this principle, but the converse does not hold over ZF. Such distinctions allow foundational investigations to identify how much choice a particular argument requires, rather than treating every use of infinite selection as an application of full AC. (plato.stanford.edu)