Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 38 · Axioms and Paradoxes

The Axiom of Choice

Learn what the axiom of choice says, when you need it, and how it relates to Zorn's lemma and the well-ordering theorem, with code for explicit choices.

Suppose you have a collection of non-empty sets and you want to pick one element from each. If there are only finitely many sets, you can do it by hand. If there are infinitely many and no rule tells you which element to take, can you still do it? The axiom of choice (AC) says yes. It is the most debated axiom of set theory, and it is the "C" in ZFC.

The statement

Axiom of Choice. For every family 𝓕 of non-empty sets, there is a function c defined on 𝓕 with c(S) ∈ S for every S ∈ 𝓕. Such a c is called a choice function.

Equivalent form: the Cartesian product of non-empty sets is non-empty. A point of the product ∏ Sᵢ is exactly a choice of one element from each Sᵢ.

When you do not need it

Choice is only required when there is no rule to specify the selection. Two situations where you do not need it:

  1. Finitely many sets. Pick an element from the first, then the second, and so on. This only uses ordinary logic.
  2. A rule that works for every set. If every set in the family is a non-empty set of natural numbers, choose the smallest element. That rule is a choice function, and no axiom was used.
Python An explicit choice function for subsets of N

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Russell's socks and shoes

Bertrand Russell gave a famous example. Given infinitely many pairs of shoes, you can choose one shoe from each pair uniformly: take the left shoe. Given infinitely many pairs of socks, which are indistinguishable within a pair, there is no uniform rule to say which sock to take; choosing one from each pair seems to require the axiom of choice.

For the same reason, in the product of non-empty sets, a point is a "choice function", and without a rule its existence needs AC.

Python Choice from finite products: nothing to prove

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Equivalent forms: Zorn's lemma and the well-ordering theorem

Given the other ZF axioms, the following statements are all equivalent to the axiom of choice:

  • Well-ordering theorem (Zermelo, 1904). Every set can be well-ordered.
  • Zorn's lemma. If every chain in a nonempty partially ordered set P has an upper bound in P, then P has a maximal element. (A chain is a subset on which the order is total; a maximal element has nothing strictly above it.)
  • Comparability of cardinals. For any sets A and B, either |A| ≤ |B| or |B| ≤ |A|.

A famous joke says: "The axiom of choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?"

A finite look at Zorn's lemma

In a finite partially ordered set, every chain is finite and has an upper bound (its top element), and a maximal element obviously exists. The content of Zorn's lemma is that the same conclusion holds for infinite posets. Here is a finite check: the subsets of {1, 2, 3} under inclusion.

Python Maximal elements and chains in a finite poset

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A typical use of Zorn's lemma: every vector space has a basis. Order the linearly independent subsets by inclusion; each chain has an upper bound (its union); so a maximal independent set exists, and it must span. Without choice one cannot prove this in general.

Consequences: wonderful and strange

Choice proves many results mathematicians rely on:

  • Every vector space has a basis (even ℝ as a vector space over ℚ).
  • Every ring with a unit has a maximal ideal.
  • A countable union of countable sets is countable.
  • The product of compact topological spaces is compact (Tychonoff's theorem).

It also proves surprising things:

  • Non-measurable sets exist: subsets of the real line to which no length can sensibly be assigned (Vitali, 1905).
  • The Banach–Tarski paradox: a solid ball can be cut into finitely many pieces which can be reassembled, by rotations and translations alone, into two balls the same size as the original. The pieces are non-measurable, so there is no contradiction with volume, and the result is not physically realizable.

In 1938 Kurt Gödel showed that AC is consistent with ZF (if ZF is consistent), and in 1963 Paul Cohen showed that its negation is also consistent with ZF. So AC is independent of the other axioms, and most working mathematicians adopt it.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What does the axiom of choice assert?

    A choice function picks one element from each set in the family.
  2. 2. Why can you choose an element from each of infinitely many non-empty sets of natural numbers without AC?

    Every non-empty set of natural numbers has a least element, which is an explicit rule.
  3. 3. Which statement is equivalent to the axiom of choice (in ZF)?

    The well-ordering theorem is equivalent to AC, as are Zorn's lemma and the comparability of any two cardinals.
  4. 4. Which classical result relies on Zorn's lemma?

    Maximal linearly independent sets exist by Zorn's lemma, and they are bases.

Summary

  • AC says every family of non-empty sets has a choice function.
  • It is needed only when there is no explicit rule for picking: finite families and sets of naturals need no choice.
  • AC is equivalent to the well-ordering theorem, Zorn's lemma and comparability of cardinals.
  • It proves useful theorems (bases, maximal ideals, Tychonoff) and counterintuitive ones (non-measurable sets, Banach–Tarski).
  • AC is independent of ZF: Gödel proved it consistent, Cohen proved its negation consistent.

Next: The Continuum Hypothesis