Throughout mathematics, constructions that feel routine in the finite case become deeply problematic in the infinite case. Given a finite collection of nonempty sets, one can simply pick an element from each --- no principle beyond the logical rules of set theory is needed. But given an *infinite* family of nonempty sets, the act of simultaneously choosing one element from each is no longer guaranteed by the other axioms of Zermelo-Fraenkel set theory (ZF). The **Axiom of Choice** asserts that such simultaneous selections are always possible: every family of nonempty sets admits a *choice function*.

This axiom is so natural that mathematicians used it implicitly for decades before Zermelo isolated it in 1904. Yet it is also so powerful that it produces consequences many find deeply counterintuitive: sets of real numbers that are not Lebesgue measurable, decompositions of a ball into finitely many pieces that can be reassembled into two balls of the same size, and well-orderings of $\mathbb{R}$ that no one can explicitly describe. The Axiom of Choice is the only standard axiom of set theory whose consistency *and* independence from the remaining axioms have both been established: Godel showed in 1938 that it cannot be disproved from ZF, and Cohen showed in 1963 that it cannot be proved from ZF either. It is genuinely optional --- and yet virtually all of modern mathematics depends on it.

[example: A Choice That Cannot Be Made Explicitly] Consider the quotient group $\mathbb{R}/\mathbb{Q}$, where two real numbers are identified if their difference is rational. Each equivalence class $[x] = x + \mathbb{Q} = \{x + q : q \in \mathbb{Q}\}$ is a countable dense subset of $\mathbb{R}$. The quotient $\mathbb{R}/\mathbb{Q}$ is an uncountable collection of nonempty sets, and these sets partition $\mathbb{R}$. A **Vitali set** is a subset $V \subset \mathbb{R}$ that contains exactly one representative from each equivalence class $[x]$. To construct $V$, one must choose, for each of the uncountably many classes $[x] \in \mathbb{R}/\mathbb{Q}$, a single element $v_{[x]} \in [x]$. No explicit rule for making this selection is known --- the equivalence classes are all "alike" in the sense that no measurable or topological property distinguishes any particular element of $[x]$ from any other. The Axiom of Choice guarantees that $V$ exists. But as we shall see, any such $V$ is necessarily non-measurable with respect to Lebesgue measure. Without the Axiom of Choice, it is consistent with ZF that every subset of $\mathbb{R}$ is Lebesgue measurable (Solovay, 1970, assuming the consistency of an inaccessible cardinal). The Vitali set is thus a pure creature of Choice: it exists only because the axiom permits a simultaneous selection that no constructive procedure can replicate. [/example]

## Definition

The fundamental problem the Axiom of Choice addresses is the gap between *existence of elements* and *existence of a selection*. In ZF, one can prove that each set in a family is nonempty --- meaning each contains at least one element --- without having any mechanism to simultaneously designate one element from each set. For a single nonempty set $A$, the statement $\exists\, x \in A$ is a theorem of logic. For two nonempty sets $A$ and $B$, one obtains an element of $A \times B$ by two applications of existential instantiation. For finitely many sets, induction suffices. But for an arbitrary (possibly uncountable) family, no finite sequence of logical steps produces the required selection, and the other axioms of ZF do not fill this gap.

The Axiom of Choice closes this gap by fiat.

[definition: Axiom of Choice] Let $\{A_i\}_{i \in I}$ be a family of nonempty sets indexed by a set $I$. The **Axiom of Choice** (AC) asserts the existence of a **choice function**: a function \begin{align*} f: I &\to \bigcup_{i \in I} A_i \end{align*} satisfying $f(i) \in A_i$ for every $i \in I$. Equivalently, AC states that the Cartesian product $\prod_{i \in I} A_i$ is nonempty whenever each $A_i$ is nonempty. [/definition]

The equivalence of the two formulations is immediate: a choice function $f: I \to \bigcup_{i \in I} A_i$ with $f(i) \in A_i$ is the same data as an element $(f(i))_{i \in I}$ of the product $\prod_{i \in I} A_i$. The product formulation makes the connection to topology transparent --- it is the starting point for Tychonoff's theorem, which asserts that an arbitrary product of [compact spaces](/page/Compact%20Space) is compact and is, remarkably, *equivalent* to the Axiom of Choice in ZF.

[remark: When Choice Is Not Needed] The Axiom of Choice is not invoked in every argument involving selection from sets. The following situations do *not* require AC: 1. **Finite families.** If $I$ is finite, a choice function can be constructed by finitely many applications of existential instantiation within ZF. 2. **Families with a definable selection rule.** If each $A_i$ has a *canonical* or *distinguished* element that can be specified by a formula, no appeal to Choice is necessary. For instance, one can always select the least element from a family of nonempty subsets of $\mathbb{N}$ (using the well-ordering of $\mathbb{N}$, which is a theorem of ZF). 3. **A single arbitrary choice.** Given one nonempty set $A$, the statement "let $a \in A$" is an application of existential instantiation, not of the Axiom of Choice. The Axiom of Choice is needed precisely when one must make *infinitely many simultaneous selections* with *no definable rule* for choosing. The paradigmatic case is the Vitali set construction: each equivalence class $[x] \in \mathbb{R}/\mathbb{Q}$ is nonempty, but no formula in the language of set theory picks out a canonical representative from each class. [/remark]

## Equivalent Formulations

The power of the Axiom of Choice is illuminated by its equivalence with several statements that, on their face, appear to have nothing to do with selecting elements from sets. The three most important equivalents --- Zorn's Lemma, the Well-Ordering Theorem, and Tychonoff's theorem --- each provide a different operational handle on the same underlying principle.

### Zorn's Lemma

In algebra and functional analysis, one frequently needs to extend partial structures to maximal ones: a linearly independent set to a basis, a proper ideal to a maximal ideal, a partial order to a total order. The difficulty is that the extension process may require transfinitely many steps, and at each step one must choose which element to add. Zorn's Lemma packages this transfinite construction into a clean sufficient condition for the existence of maximal elements.

[quotetheorem:1226]

Zorn's Lemma is equivalent to the Axiom of Choice in ZF: each implies the other using only the remaining ZF axioms. The proof that AC implies Zorn's Lemma proceeds by transfinite recursion. One constructs an increasing chain in $P$ by repeatedly choosing, at each successor step, an element strictly above the current one (using a choice function on the set of strict upper bounds). At limit steps, one takes an upper bound of the chain constructed so far (which exists by hypothesis). If the process never terminates, the chain, indexed by all ordinals, would inject the proper class of ordinals into the set $P$, violating the axiom of replacement. Therefore the process must terminate, and the terminal element is maximal.

The converse --- Zorn's Lemma implies AC --- is more subtle. Given a family $\{A_i\}_{i \in I}$ of nonempty sets, one considers the partially ordered set of partial choice functions: functions $f: J \to \bigcup_{i \in I} A_i$ defined on some subset $J \subset I$ with $f(i) \in A_i$ for all $i \in J$, ordered by extension. Every chain of partial choice functions has an upper bound (their union), so Zorn's Lemma produces a maximal partial choice function. If its domain were a proper subset of $I$, one could extend it by choosing any element from $A_j$ for some $j \notin J$, contradicting maximality. Therefore the maximal element is a total choice function.

Zorn's Lemma is the form of Choice most frequently invoked in algebra. It is used to prove that every vector space has a [basis](/page/Basis), every ring has a maximal ideal, every field has an algebraic closure, and every filter can be extended to an ultrafilter. In each case, the argument follows the same template: define the "partial objects" one seeks to extend, verify the chain condition, and apply Zorn.

### The Well-Ordering Theorem

The Well-Ordering Theorem addresses a different structural question: can every set be equipped with a well-ordering?

[definition: Well-Ordering] A **well-ordering** on a set $S$ is a total order $\leq$ on $S$ such that every nonempty subset of $S$ has a least element. [/definition]