The Axiom of Choice and Its Equivalences

Core Idea

The axiom of choice (AC) has many equivalent formulations: the well-ordering theorem (every set can be well-ordered), Zorn's lemma (maximal elements exist in certain posets), Zermelo's axiom (choice functions exist), and the multiplicative principle (products of nonempty sets are nonempty). Each formulation is intuitively different, yet logically equivalent over ZF. AC is independent of ZF and required for many results (e.g., Hahn-Banach, Tychonoff compactness).

How It's Best Learned

Prove AC ↔ well-ordering theorem by constructing well-orderings from choice functions. Derive Zorn's lemma from AC via ordinals. Show consistency of each: any ZFC proof can be 'avoided' in ZF+¬AC (e.g., vector spaces need not have bases). Discuss constructive alternatives (DC, AD).

Common Misconceptions

• Assuming AC is 'obvious' (it is not; it postulates global selection, which is nonconstructive).
• Confusing choice functions (AC) with the ability to choose finitely many items (need only finite axiom of choice).

Explainer

You already know the axiom of choice from your prerequisite study: given any collection of nonempty sets, there exists a function that picks one element from each. You also know the well-ordering theorem: every set can be well-ordered (given a total order in which every nonempty subset has a least element). The surprising fact is that these two statements — stated in entirely different terms, one about selection functions and one about orderings — are logically equivalent over ZF set theory. Neither implies the other in any obvious way from the statements alone, which is what makes their equivalence a genuine theorem.

The proof that AC implies the well-ordering theorem uses transfinite recursion: given a choice function f, well-order the set S by using f to pick a "least" element, then pick the least of what remains, and so on through all ordinal stages until S is exhausted. This process must terminate — if it ran for more than |S| steps, we'd have a contradiction — so every element of S gets assigned an ordinal rank, giving a well-ordering. Going the other direction is easier: if S is well-ordered, define the choice function by always picking the well-ordering minimum from each nonempty subset.

Zorn's lemma is the third major equivalent: if every chain (totally ordered subset) in a partially ordered set has an upper bound in the set, then the set has a maximal element. This sounds nothing like AC or the well-ordering theorem, yet all three are equivalent. Zorn's lemma is the formulation most frequently *used* in mathematics: to prove that every vector space has a basis, consider the poset of all linearly independent sets ordered by inclusion; every chain has an upper bound (its union); Zorn's lemma gives a maximal element; maximality implies it spans the space. Without AC, it is consistent with ZF that there exist vector spaces with no basis at all.

The deeper point is that these equivalences reveal AC as a principle about global coherence: it says that mathematical objects fitting local consistency requirements (nonempty sets, chains with upper bounds, etc.) can always be assembled into globally consistent choices (selection functions, maximal elements, well-orderings). This global assembly is precisely what makes AC nonconstructive — it asserts existence without providing a recipe. In ZF alone, you cannot prove AC (Gödel showed AC is consistent with ZF) and you cannot refute it (Cohen showed ¬AC is also consistent). This independence means you are genuinely free to work with ZFC or explore alternatives like the axiom of determinacy (AD), which contradicts AC but implies all sets of reals are measurable — a mathematically cleaner world with different tradeoffs.