The Axiom of Choice and Its Equivalents

Part 10, Chapter 10: Foundations, Cardinality, Choice, and Incompleteness

Learning objectives

State the Axiom of Choice and its choice-function formulation
State Zorn's Lemma and explain its logical equivalence to AC
State the Well-Ordering Theorem (every set has a well-ordering)
Recognize the Banach-Tarski paradox and the role of non-measurable sets

The Axiom of Choice (AC) is the most-debated axiom in mathematics. Stated plainly, it says: for any collection of nonempty sets, you can simultaneously pick one element from each set, even when the collection is uncountable and there is no rule for choosing. Almost every working mathematician uses it daily, "every vector space has a basis," "every ring with unity has a maximal ideal," "the product of compact spaces is compact" all require AC. Yet AC also produces deeply counterintuitive consequences, most famously the Banach-Tarski paradox: a solid ball can be decomposed into finitely many pieces and reassembled into two balls. Godel (1940) and Cohen (1963) settled the foundational question: AC is logically independent of the other ZF axioms.

The Axiom of Choice

(AC) Let $\{A_i\}_{i \in I}$ be a family of nonempty sets indexed by an arbitrary set $I$ . Then there exists a function

$f: I \to \bigcup_{i \in I} A_i \qquad \text{with} \qquad f(i) \in A_i \text{ for every } i \in I.$ iinIAiqquadtextwithqquadf(i)inAitextforeveryiinI.

The function $f$ is called a choice function. For finite $I$ this is provable without AC: just pick elements one by one in finitely many steps. For countable $I$ a weaker axiom (Countable Choice, AC $_\omega$ omega) suffices and is also typically uncontroversial. The strong form, arbitrary index sets $I$ , possibly uncountable, with no canonical selection rule available, is the AC of the controversy.

The widget visualizes set families and selections. The Axiom of Choice asserts that even when you have a Venn diagram with uncountably many regions, each nonempty, you can pick one element from each, even if there is no formula or algorithm describing the selection.

Zorn's Lemma

(Zorn) Let $(P, \leq)$ be a partially ordered set in which every chain (totally ordered subset) has an upper bound in $P$ . Then $P$ contains a maximal element $m$ : an element such that no $p > m$ exists in $P$ .

Zorn's Lemma is the workhorse formulation of AC in algebra and topology. It is logically equivalent to AC (each implies the other in ZF). Standard applications:

Every vector space has a basis (apply Zorn to the poset of linearly independent subsets under inclusion).
Every nonzero ring with $1$ has a maximal ideal (apply Zorn to the poset of proper ideals).
Hahn-Banach theorem (existence of bounded linear extensions) requires AC for infinite-dimensional cases.
Tychonoff theorem (the product of any family of compact spaces is compact in the product topology) is in fact EQUIVALENT to AC.

The Well-Ordering Theorem

(Zermelo, 1904) Every set $A$ can be well-ordered: there exists a total ordering $\preceq$ on $A$ such that every nonempty subset has a least element. The natural numbers are already well-ordered by $\leq$ ; the reals are NOT well-ordered by their usual $\leq$ (the open interval $(0, 1)$ has no least element). Well-ordering says: pick a different order, and even $\mathbb{R}$ can be well-ordered. The Well-Ordering Theorem is also equivalent to AC.

The triangle of equivalents. In ZF set theory, the following three statements are mutually equivalent:

$\boxed{\text{Axiom of Choice} \iff \text{Zorn's Lemma} \iff \text{Well-Ordering Theorem}}$

You can prove any one of them from any of the others. Different mathematical contexts make different formulations more natural: algebraists usually invoke Zorn; set theorists invoke well-ordering; analysts invoke choice functions.

The Banach-Tarski paradox

In 1924, Banach and Tarski proved a theorem so counterintuitive that it became the standard exhibit in arguments against AC. The Banach-Tarski paradox: the closed unit ball $B \subset \mathbb{R}^3$ can be decomposed into 5 disjoint pieces $P_1, \ldots, P_5$ and rotated/translated to form TWO disjoint balls each of unit radius. Volume is doubled out of thin air.

The trick: the pieces $P_i$ i are non-Lebesgue-measurable sets, weird fractal-like point sets whose existence is guaranteed by AC but cannot be explicitly constructed or visualized. Volume only makes sense for measurable sets, so the "doubling" does not violate any physical conservation law. The paradox is a statement about pure set theory, not about real spheres of butter.

Godel showed (1940) that AC is consistent with ZF (the constructible universe $L$ satisfies AC). Cohen showed (1963) that $\neg \text{AC}$ is also consistent (via forcing). Hence AC is independent of ZF: neither provable nor disprovable from ZF alone. Most contemporary mathematics adopts AC, but constructivist and computable-analysis traditions reject it.

Where this shows up

Functional analysis: The Hahn-Banach theorem (extension of bounded linear functionals) underlies duality theory, distributions, and the Riesz representation theorem. Without AC, infinite-dimensional functional analysis collapses into a much more restrictive world.
Algebraic geometry / commutative algebra: Existence of maximal ideals (and hence of points in $\operatorname{Spec}(R)$ ) requires AC. Krull's theorem, "every proper ideal lies in a maximal ideal", is the precise statement.
Probability theory: The full machinery of $\sigma$ -algebras and existence of probability measures on uncountable spaces uses AC (via the Caratheodory extension theorem and Tychonoff for product measure existence on infinite products).
Topology: The Tychonoff theorem (compactness of arbitrary products) is exactly AC. Without it, compactness behaves very differently in infinite-dimensional spaces.
Computability theory: Constructive mathematics and computable analysis explicitly REJECT AC because it provides no algorithm to compute the choice function. Different foundational schools make different bets here; the working mathematician's consensus accepts AC.

Pause and think: Suppose you have countably many pairs of shoes lined up. Why does picking "the left shoe from each pair" not require AC? Now suppose you have countably many pairs of socks, identical, no canonical "left" sock. Why does picking one from each pair require AC (in fact, only Countable Choice)? The shoes have a rule; the socks do not.

Try it

Sketch why "every vector space has a basis" requires Zorn's Lemma. (Hint: the poset is the collection of linearly independent subsets ordered by inclusion; the union of a chain of linearly independent sets is linearly independent, verify this in two lines, so Zorn applies.)
True or false: every infinite-dimensional vector space has a basis without any use of AC. (Answer: false. Without AC, models of ZF exist where $\mathbb{R}$ over $\mathbb{Q}$ has no Hamel basis.)
Predict: do you need AC to construct a maximal ideal in a finite ring? (Answer: no, for finite rings, the search for a maximal ideal terminates after finitely many steps.) What about an infinite ring? (Yes, in general.)
Explain why the Banach-Tarski paradox does not violate the conservation of volume. (Hint: volume / Lebesgue measure is only defined for measurable sets; Banach-Tarski uses non-measurable pieces.)

A trap to watch for

"Countable Choice" (AC $_\omega$ omega), which suffices for a countably-indexed family of nonempty sets, is much weaker than the full Axiom of Choice and almost universally accepted, the entire theory of $L^p$ spaces, real analysis, and elementary measure theory rests only on AC $_\omega$ omega. The "controversial" full AC is needed for uncountable index sets: it is the principle behind Banach-Tarski, the existence of non-measurable sets, the Hahn-Banach theorem in full generality, and Tychonoff for non-metrizable products. When critiques of AC are aired, the target is almost always the full uncountable form, not Countable Choice. If you find yourself "needing AC" in a finite or countable construction, double-check: you probably only need much weaker machinery.

What you now know

You can state AC, Zorn's Lemma, and the Well-Ordering Theorem; recognize them as logically equivalent and use whichever is most convenient; identify the standard algebraic and analytic applications; and explain why Banach-Tarski does not violate conservation of volume (the pieces are non-measurable). The next section closes the chapter and the book with Godel's incompleteness theorems, the precise limits of what any consistent formal system can prove.

Mark section complete →

References

Garrity, T. (2002). All the Mathematics You Missed: But Need to Know for Graduate School. Cambridge University Press, §10.4-10.5.
Halmos, P. R. (1960). Naive Set Theory. Springer, §15-17 (Choice, Zorn, Well-Ordering).
Jech, T. (2003). Set Theory: The Third Millennium Edition. Springer, ch. 5.
Enderton, H. B. (1977). Elements of Set Theory. Academic Press, ch. 6 and 7.
Hrbacek, K., Jech, T. (1999). Introduction to Set Theory (3rd ed.). CRC Press, ch. 8.