The Axiom of Choice and Beyond

You have just proved that $|\mathbb{N}| < |\mathbb{R}|$, that $|\mathcal{P}(\mathbb{N})| = |\mathbb{R}|$, and that Cantor-Schröder-Bernstein lets you compute cardinalities without ever building an explicit bijection. Two natural questions remain. First: are there cardinalities strictly between $\aleph_0 = |\mathbb{N}|$ and $\mathfrak{c} = |\mathbb{R}|$? Second: when we said "pick an element from each set" in some of the Chapter 8 arguments, were we doing something legal? Both questions point at axioms beyond the ones used so far — the Axiom of Choice and the Continuum Hypothesis — and at the most surprising results in twentieth-century mathematics: both are independent of the standard axioms. This section is the capstone of Velleman's textbook treatment of infinite sets; it tells you what professional set theorists worry about, and where you can read further.

The Axiom of Choice

Statement (Axiom of Choice, AC). For every collection $\mathcal{F}$ of nonempty sets, there exists a choice function $c \colon \mathcal{F} \to \bigcup \mathcal{F}$ such that $c(A) \in A$ for every $A \in \mathcal{F}$.

In plain English: given any family of nonempty sets — possibly infinitely many, possibly uncountably many — we can simultaneously pick one element from each. For one set, no axiom is needed: $A$ is nonempty, so by definition $\exists x \in A$. For finitely many sets, repeated application of $\exists$-elimination works. The axiom is needed when $\mathcal{F}$ is infinite and the sets have no canonical "first" element to single out.

Russell's illustration is sharp: from infinitely many pairs of shoes you can pick the left shoe of each pair (no axiom needed — "left" is a uniform recipe). From infinitely many pairs of indistinguishable socks, no uniform recipe is available, and AC is exactly the principle that lets you do it anyway.

Where AC sneaks in

Many results that feel constructive secretly rely on AC. A short list:

• Every vector space has a basis. The proof for infinite-dimensional spaces uses Zorn's Lemma, which is equivalent to AC.
• A countable union of countable sets is countable. Listing each countable $A_n$ as $a_{n,0}, a_{n,1}, a_{n,2}, \ldots$ requires choosing one enumeration per $n$ — an AC move.
• Every surjection has a right inverse. If $f \colon A \to B$ is onto, building $g \colon B \to A$ with $f \circ g = \mathrm{id}_B$ means choosing one preimage from each nonempty fiber $f^{-1}(b)$ — again AC.
• Tychonoff's theorem in topology. The statement "any product of compact spaces is compact" is in fact equivalent to AC.

Modern mathematics by default works in ZFC — Zermelo-Fraenkel set theory with the Axiom of Choice. Constructive mathematics (Bishop's school, intuitionism, type-theoretic approaches) refuses AC in the form above, and gets a different mathematics in which existence proofs must produce explicit witnesses.

Equivalents of AC

Three statements are logically equivalent over ZF (ZFC minus AC):

• The Axiom of Choice (AC). As above.
• Zorn's Lemma. If $(P, \leq)$ is a nonempty partially ordered set in which every chain (totally ordered subset) has an upper bound, then $P$ has a maximal element.
• Well-Ordering Theorem. Every set can be well-ordered — that is, given a linear order in which every nonempty subset has a least element.

Each of the three is a useful tool in a different setting. Zorn's Lemma is the workhorse of algebra (every commutative ring has a maximal ideal; every field has an algebraic closure). The Well-Ordering Theorem powers transfinite induction. AC itself is the cleanest to state. Bertrand Russell famously remarked that the Axiom of Choice is "obviously true," the Well-Ordering Theorem is "obviously false," and Zorn's Lemma is "nobody knows" — despite all three being equivalent.

The Banach-Tarski paradox

One unsettling consequence of AC is the Banach-Tarski paradox (Banach and Tarski, 1924): the unit ball in $\mathbb{R}^3$ can be partitioned into finitely many pieces that, when reassembled using only rigid motions, produce two unit balls of the same size as the original. The pieces are not "measurable" in the usual sense — you could not weigh them — and the construction relies essentially on AC. The paradox is not a contradiction in ZFC; it is a warning that the geometric intuition of "volume" does not extend to all subsets of $\mathbb{R}^3$, only to the measurable ones.

This is one reason measure theory always restricts attention to the $\sigma$-algebra of measurable sets — precisely the sets where Banach-Tarski-style pathologies are forbidden.

The Continuum Hypothesis

Cantor proved $|\mathbb{N}| < |\mathbb{R}|$ (§8.2 diagonal argument). Writing $\aleph_0 = |\mathbb{N}|$ and $\mathfrak{c} = |\mathbb{R}|$, Cantor asked: is there any cardinality $\kappa$ with $\aleph_0 < \kappa < \mathfrak{c}$? The Continuum Hypothesis (CH) asserts that there is none — equivalently, that $\mathfrak{c} = \aleph_1$, the smallest uncountable cardinal.

This was Hilbert's first problem on his 1900 list of open problems. The resolution came in two surprising halves:

• Gödel (1938): CH cannot be disproved from the axioms of ZFC. There is a model of ZFC (the constructible universe $L$) in which CH is true.
• Cohen (1963): CH cannot be proved from the axioms of ZFC either. Cohen invented the technique of forcing to build a model of ZFC in which $\mathfrak{c} = \aleph_2$ (so CH is false).

Together: CH is independent of ZFC. Neither it nor its negation is a theorem of standard set theory. This is not a deficiency of ZFC — it is an intrinsic limitation revealed by the existence of multiple consistent models. Cohen won the Fields Medal in 1966 for forcing, which has since become a central technique in set theory and is used to settle dozens of analogous independence questions.

Pause and think: Why is "CH is independent of ZFC" a stronger statement than "we do not yet know whether CH is true"? (Hint: the former is a theorem proven within mathematics; the latter is a statement about our current state of knowledge. Gödel and Cohen proved that no future advance within ZFC can settle CH — that is a permanent, not a temporary, limitation.)

Try it

• Before reading further: state AC in your own words. Then explain why no axiom is needed to pick one element from a single nonempty set, but an axiom IS needed to pick one from each of infinitely many nonempty sets without a uniform rule.
• Predict first: does the proof that "$\mathbb{N} \times \mathbb{N}$ is countable" use AC? (Hint: no — the Cantor pairing function provides an explicit bijection. The use of AC is in claims of pure existence without a constructive witness.)
• Verify Russell's socks example: explain why "left shoe of each pair" is a recipe that needs no choice axiom, while "one sock of each pair" is not.
• State Zorn's Lemma and apply it to argue that every nonempty partial order with the chain-upper-bound property contains a maximal element. Where does the abstract statement of AC enter the proof?
• Explain the difference between (i) "CH is unproved" and (ii) "CH is independent of ZFC." Why is the second a theorem and not a statement about future research?

A trap to watch for

It is tempting to dismiss the Axiom of Choice as a curiosity used only by set theorists. This is wrong. A working analyst, algebraist, or topologist invokes AC dozens of times per paper, usually without naming it. Saying "let $(x_n)$ be a sequence with $x_n \in A_n$ for each $n$" is already a (countable) choice. Saying "let $\mathcal{B}$ be a basis of the vector space $V$" for infinite-dimensional $V$ is AC via Zorn. The point of this section is not that you should avoid AC — you cannot in mainstream mathematics — but that you should recognise when it is being used, so that arguments depending on it can be flagged when working in constructive or computational contexts where it is unavailable.

What you now know

You can state the Axiom of Choice, its main equivalents (Zorn's Lemma and the Well-Ordering Theorem), and the Banach-Tarski paradox as a non-intuitive consequence. You know the Continuum Hypothesis, why it was Hilbert's first problem, and how Gödel and Cohen together proved it independent of ZFC. This closes Chapter 8 of Velleman and the textbook proper. Beyond this point lies axiomatic set theory: large cardinal axioms, inner models, forcing, descriptive set theory — topics for a follow-up course such as Jech's or Kunen's. You now have the foundations to read them.

References

• Velleman, D. J. (2019). How to Prove It: A Structured Approach (3rd ed.). Cambridge University Press, ch. 8.
• Halmos, P. R. (1960). Naive Set Theory. Van Nostrand (Axiom of Choice chapter).
• Enderton, H. B. (1977). Elements of Set Theory. Academic Press, ch. 6.
• Jech, T. (2003). Set Theory (3rd millennium ed.). Springer.
• Cohen, P. J. (1966). Set Theory and the Continuum Hypothesis. W. A. Benjamin.
• Banach, S., Tarski, A. (1924). "Sur la décomposition des ensembles de points en parties respectivement congruentes." Fundamenta Mathematicae 6, 244–277.