The Axiom of Choice and Its Formulations

The axiom of choice asserts that every family of nonempty sets admits a choice function. Despite its intuitive appeal, it has surprising consequences and is independent of the other ZF axioms.

The Axiom

Definition6.1Axiom of choice (AC)

For every family $\{A_i\}_{i \in I}$ of nonempty sets, there exists a choice function $f: I \to \bigcup_{i \in I} A_i$ with $f(i) \in A_i$ for all $i \in I$ .

Equivalently, if $\mathcal{F}$ is a set of nonempty sets, there exists a function $f: \mathcal{F} \to \bigcup \mathcal{F}$ with $f(A) \in A$ for all $A \in \mathcal{F}$ .

RemarkWhy AC is controversial

For finite families, the existence of choice functions is provable in ZF. For countable families of nonempty subsets of $\mathbb{R}$ , one can sometimes construct explicit choices. But for arbitrary uncountable families of arbitrary nonempty sets, no construction is possible in general -- the axiom simply postulates existence. AC implies the existence of non-measurable sets (Vitali), well-orderings of $\mathbb{R}$ , and the Banach-Tarski paradox, all of which are counterintuitive.

Equivalent Formulations

Theorem6.1Equivalents of the axiom of choice

The following are equivalent over ZF:

Axiom of choice (AC).
Well-ordering theorem: Every set can be well-ordered.
Zorn's lemma: If every chain in a partially ordered set has an upper bound, then the set has a maximal element.
Hausdorff maximal principle: Every chain in a partially ordered set is contained in a maximal chain.
Tukey's lemma: Every set of finite character has a maximal element under inclusion.
For every surjection $f: A \twoheadrightarrow B$ , there exists a right inverse $g: B \to A$ with $f \circ g = \mathrm{id}_B$ .
The Cartesian product of any family of nonempty sets is nonempty.

Weaker Forms

Definition6.2Weaker choice principles

Several weaker forms of AC are used in analysis and topology:

Countable choice (AC $_\omega$ ): Every countable family of nonempty sets has a choice function.
Dependent choice (DC): If $R$ is a binary relation on a nonempty set $A$ such that for every $a \in A$ there exists $b$ with $aRb$ , then there exists a sequence $(a_n)$ with $a_n R a_{n+1}$ for all $n$ .
Boolean prime ideal theorem (BPI): Every Boolean algebra has a prime ideal (equivalent to the ultrafilter lemma).

The implications are: AC $\implies$ DC $\implies$ AC $_\omega$ , and none reverses.

ExampleUses of AC in mathematics

Every vector space has a basis: requires full AC.
Hahn-Banach theorem: requires only BPI.
Baire category theorem for complete metric spaces: requires only DC.
Every countable union of countable sets is countable: requires AC $_\omega$ .
Tychonoff's theorem (arbitrary products of compact spaces are compact): equivalent to AC.