Advanced undergraduateFoundationsPlanned

The axiom of choice and its equivalents

The axiom of choice, its equivalents Zorn's lemma and the well-ordering theorem, typical applications in algebra and analysis, and its non-constructive consequences.

math.found.axiom-of-choice

Show everything needed to reach this topic

The lesson for this topic has not been written yet. The outline below is part of the curriculum map and has not been reviewed.

Builds on

Ordinals and cardinals

Required prerequisites, all the way down: 20

You will learn to

Prove, over ZF, that the axiom of choice, Zorn's lemma and the well-ordering theorem are equivalent.
Use Zorn's lemma to prove that every vector space has a basis and that every non-zero commutative ring with identity has a maximal ideal.
Describe results, such as the existence of a non-measurable set of reals, that are provable with choice but not in ZF alone (relative to the consistency of an inaccessible cardinal).

Definition

Axiom of choice (AC): every family of non-empty sets has a choice function.
Well-ordering theorem: every set admits a well-order.
Countable choice and dependent choice (DC) are weaker principles that suffice for much of classical analysis.

Theorem

Over ZF, AC, Zorn's lemma and the well-ordering theorem are equivalent.
Gödel: if ZF is consistent, so is ZFC. Cohen (1963): if ZF is consistent, so is ZF + ¬AC.
AC implies that some subset of ℝ is not Lebesgue measurable (Vitali). Solovay showed that, if an inaccessible cardinal is consistent with ZFC, then ZF + DC is consistent with every set of reals being Lebesgue measurable.

Common misconceptions

Thinking choice is only needed for uncountable families; choosing from countably many two-element sets can already require it.
Believing the Banach–Tarski paradox refutes AC; it shows that some sets cannot be assigned a volume invariant under rigid motions.
Assuming every proof that uses Zorn's lemma can easily be made constructive.

Leads to

Axiomatic set theory: hierarchy, cardinal arithmetic and L

Optional discoveries

Measure theory and integration Vitali's construction of a non-measurable set uses AC; this is one reason Lebesgue measure is defined on a σ-algebra of sets rather than on all subsets of ℝ.
Functional analysis The Hahn–Banach theorem is usually proved with Zorn's lemma, although it follows from the strictly weaker ultrafilter lemma.
Advanced linear algebra Over ZF, 'every vector space has a basis' is equivalent to the axiom of choice (Blass, 1984).