Axiom of Choice

The statement

Let { A_i }_{i ∈ I} be an indexed family of non-empty sets. The axiom of choice asserts the existence of a choice function f : I → ⋃_{i} A_i with f(i) ∈ A_i for every i ∈ I.

Equivalently, the Cartesian product ∏_{i ∈ I} A_i is non-empty whenever every factor is non-empty.

If I is finite, no axiom is needed: pick representatives one at a time and use the standard ZF rules for finite constructions. If I is countable and the A_i are well-orderable in a uniform way (e.g., subsets of ℕ), the weaker axiom of countable choice suffices. The full strength of AC matters only when I is uncountable and there is no canonical way to single out an element of each A_i.

Russell's parable

Bertrand Russell explained the axiom with an everyday image. Imagine you have countably infinitely many pairs of shoes and countably infinitely many pairs of socks.

• Shoes. "Always pick the left shoe" is a uniform rule. From this rule we extract one shoe from every pair, and we have a choice function definable in plain ZF. No axiom required.
• Socks. The pairs are identical — there is no "left sock". A uniform rule does not exist. To extract one sock from each pair you must postulate that a choice function exists. That is the axiom of choice.

The parable captures AC's essence: it asserts the existence of a function that no rule defines.

ZF vs ZFC vs other foundations

System	What it is	Includes AC?	Strength	Where it shows up
ZF	Zermelo-Fraenkel set theory: 9 axioms (extensionality, pairing, union, power set, infinity, separation, replacement, foundation, empty set)	No	Strong enough for most "concrete" mathematics	Constructive set theory, reverse mathematics
ZF + DC	ZF plus Dependent Choice — every iterative choice on a non-empty relation can proceed	Weak form only	Enough for most of classical analysis	Real analysis, descriptive set theory
ZF + ACω	ZF plus Countable Choice — choice functions exist for countable collections	Countable form only	Enough for Lebesgue measure, separability arguments	Measure theory, analysis on ℝⁿ
ZFC	ZF + full Axiom of Choice	Yes	Standard foundation of modern mathematics	Algebra, topology, functional analysis, model theory
ZFC + GCH	ZFC + Generalized Continuum Hypothesis	Yes	Decides cardinal arithmetic	Set theory research
ZF + AD	ZF + Axiom of Determinacy (incompatible with full AC)	No (contradicts AC)	Implies every set of reals is Lebesgue measurable	Inner-model theory, regular subsets of ℝ
NBG	Von Neumann-Bernays-Gödel — a class-conservative extension of ZFC	Yes (in NBG-AC)	Conservative over ZFC for set statements	Category theory foundations

AC equivalents over ZF

Many seemingly unrelated statements are equivalent to AC; proving any one of them inside ZF establishes the others.

• Zorn's lemma. Every non-empty partially ordered set in which every chain has an upper bound contains a maximal element.
• Well-ordering theorem. Every set can be well-ordered (i.e., totally ordered so that every non-empty subset has a least element).
• Tychonoff's theorem. Any product of compact topological spaces is compact.
• Hahn-Banach (general form). Every bounded linear functional on a subspace extends to a bounded linear functional on the whole space, with the same norm.
• Existence of Hamel basis. Every vector space has a basis.
• Maximal ideal theorem. Every non-trivial ring has a maximal ideal.
• Krull's theorem. Every proper ideal in a unital ring extends to a maximal ideal.
• Comparison of cardinalities. For any sets A, B, either |A| ≤ |B| or |B| ≤ |A|.
• König's theorem. If κᵢ < λᵢ for all i in some index set I, then Σ κᵢ < ∏ λᵢ.

Each of these is theorem-strength inside ZFC and undecidable inside plain ZF; assuming any one of them in ZF gives the others.

Banach-Tarski as an AC consequence

The most famous illustration of AC's power: the Banach-Tarski paradox (Banach and Tarski, 1924).

The closed unit ball B in ℝ³ can be partitioned into finitely many disjoint subsets which, by rotation and translation alone, can be reassembled into two disjoint copies of B.

The proof uses AC to construct non-measurable subsets of B exploiting the free non-abelian structure of the rotation group SO(3). The "pieces" are wildly non-measurable sets — they have no consistent volume — so the intuitive law "rearranging without overlap preserves volume" simply doesn't apply.

The paradox is not a contradiction; it is a theorem in ZFC. Its moral: AC produces sets so badly behaved that no measure can be defined on them, and such sets can do things our spatial intuition forbids. In ZF + DC + "every set of reals is Lebesgue measurable" (Solovay's model, with an inaccessible cardinal), Banach-Tarski fails.

What needs AC, what doesn't

Result	Needs AC?	Comment
Finite set has a maximal element	No	Trivial induction
Every finite-dimensional vector space has a basis	No	Constructible by Gaussian elimination
Every vector space has a basis	Yes (equivalent)	Blass 1984
ℝ has a well-ordering	Yes	Gödel 1938; no definable well-ordering exists in ZFC
Every Lebesgue measurable function is Lebesgue measurable	No	Tautology; measurability defined intrinsically
Existence of a non-Lebesgue-measurable set in ℝ	Yes (almost)	Uses AC to choose Vitali set; Solovay's model has all sets Lebesgue measurable
Every product of compact spaces is compact	Yes (Tychonoff = AC)	For finite products no AC needed; for arbitrary products yes
Hahn-Banach for separable Banach spaces	No (countable choice suffices)	Full Hahn-Banach is strictly weaker than AC but unprovable in ZF
Every infinite set has a countable subset	Countable choice	Provable from ACω
The continuum hypothesis (CH)	Independent of ZFC	Cohen 1963 — neither AC alone nor its negation decides CH

Why it matters

• Algebra. Every vector space has a basis (Hamel basis), every commutative ring has a maximal ideal, every field has an algebraic closure, every Lie algebra has a Cartan subalgebra. All standard algebra textbooks invoke Zorn's lemma — that is, AC.
• Functional analysis. Hahn-Banach extension, Tychonoff's theorem, the existence of ultrafilters, the Banach-Alaoglu theorem on weak-* compactness. The dual space machinery of functional analysis is fundamentally AC-dependent.
• Topology. Tychonoff's theorem (product of compact = compact) is equivalent to AC. The Stone-Čech compactification, the existence of nontrivial ultrafilters, and many separation theorems require AC.
• Logic and model theory. Compactness theorem in first-order logic (every finitely satisfiable theory is satisfiable) is equivalent to a weak form of AC (the Boolean prime ideal theorem). Łoś's theorem on ultraproducts uses choice in its construction.
• Measure theory and probability. Vitali's construction of a non-measurable set, the existence of a Hahn decomposition, and the Radon-Nikodym theorem all rely on AC in standard treatments. Solovay's model (ZF + DC, "every set of reals is Lebesgue measurable") shows what mathematics looks like without AC.

Gödel and Cohen — the independence of AC

Gödel (1938) constructed the inner model L of "constructible sets" inside ZF. L satisfies all ZF axioms, AC, and even GCH. Hence ZF + AC is consistent if ZF is consistent — AC cannot be disproved from ZF.

Cohen (1963) introduced forcing, a method for adjoining "generic" sets to a ground model to control which statements hold. Cohen built a forcing extension of ZF in which AC fails. Hence ZF + ¬AC is consistent if ZF is consistent — AC cannot be proved from ZF.

Together: AC is independent of ZF. The mathematical community then chose, by overwhelming consensus, to adopt AC. Thus ZFC. The same techniques showed CH is independent of ZFC — a story that motivates the next concept on this site.

Alternatives and weaker forms

• Axiom of Countable Choice (ACω). Choice functions exist for countable families. Strictly weaker than AC; sufficient for nearly all of basic real analysis, but proves "ℕ × ℕ is countable" and "countable union of countables is countable" without full AC.
• Axiom of Dependent Choice (DC). Strictly between ACω and AC. Allows iterative choices that depend on previous selections. Powers most existence theorems in dynamical systems and ergodic theory.
• Boolean Prime Ideal theorem (BPI). Every Boolean algebra has a prime ideal. Strictly weaker than AC but stronger than DC; equivalent to the compactness theorem in first-order logic.
• Hahn-Banach. Strictly between BPI and AC; sufficient for most functional analysis.
• Axiom of Determinacy (AD). Asserts every infinite two-player perfect-information game has a winning strategy for one player. Incompatible with full AC, but implies every set of reals is Lebesgue measurable. Provides a different mathematical universe where Banach-Tarski fails.

Common mistakes

• Believing ZFC is "needed" for finite mathematics. No. Combinatorics on finite sets, finite-dimensional linear algebra, and computational arithmetic live happily inside ZF (and in fact inside far weaker systems). AC matters only when you reach across uncountable collections.
• Treating AC as obvious. The intuition "of course you can pick one from each" works for finite or definable cases. For uncountable, undefinable cases there is genuinely no rule — that is the entire point of the axiom.
• Confusing AC with the well-ordering principle on ℕ. "Every non-empty subset of ℕ has a least element" is a theorem of plain ZF and uses no choice. The well-ordering theorem (well-ordering of every set, including ℝ) is the AC-equivalent statement.
• Thinking Banach-Tarski refutes AC. It doesn't — it's a theorem in ZFC, not a contradiction. It refutes the intuition that "rearranging pieces preserves volume" as a universal statement; volume is preserved only on measurable rearrangements, and AC produces non-measurable ones.
• Using Zorn or Tychonoff without realising you're using AC. Common in research papers. If you "extend by Zorn's lemma", "take a maximal subset", "take an ultrafilter", or "apply Tychonoff" you are using AC. There is nothing wrong with this — but knowing you've done so makes it easier to see when alternatives suffice.
• Asserting "AC fails in constructive mathematics". More precisely: in many constructive systems, full AC implies excluded middle (Diaconescu's theorem), so it's strong enough to collapse constructive logic. But weaker forms of choice (countable, dependent) often coexist with constructive logic.