Ordinals and axioms · Definition

Axiom of choice

set theoryordinals and axioms

Before you start you need to know

It seems obvious that we can always pick one element from each set, but with infinite families that intuition is not enough. Zermelo formulated it in 1904 to prove the well-ordering theorem.

Definition

Statement that every family of nonempty sets admits a choice function \(f\) that picks one element from each set in the family.

\[\forall X\,(\emptyset\notin X \rightarrow \exists f\,\forall A\in X\,(f(A)\in A))\]

The axiom of choice is independent of ZF: Gödel showed in 1938 that it is consistent with ZF, and Cohen showed in 1963 that its negation is also consistent. It is equivalent to several principles, such as Zorn's lemma, the well-ordering theorem, and the claim that every surjection has a right inverse. With it, every set can be well-ordered and any two cardinals are comparable, so cardinals become totally ordered.

Let \(\mathcal{P}^*(\mathbb{R})\) be the family of nonempty subsets of \(\mathbb{R}\). Some of them have a natural representative, such as the infimum of those bounded below, but no known rule selects one element from each. The axiom guarantees that a choice function on this family exists, even if it cannot be described.

A common mistake is to think the axiom is needed for finite families, where choice is explicit and follows from ZF by induction. Another is to believe the axiom gives a concrete construction: it only asserts that a choice function exists, without saying how to compute it.

Think about it

Why isn't it enough to always pick the first element of each set?

Because without a well-order there is no definable rule that picks a 'first' element, so the choice requires the axiom.

Exercises 10

  1. What does the axiom of choice state?
  2. Given a family \(X\) of nonempty sets, what must a choice function \(f\) satisfy?
  3. Which of these statements is equivalent to the axiom of choice over ZF?
  4. In what context is the axiom of choice formulated as an independent axiom?
  5. What does the axiom of choice guarantee for a family \(X\) of nonempty sets?
  6. Let \(X=\{\{1,2\},\{3,4,5\}\}\). Is the axiom of choice needed to find a choice function on \(X\)?
  7. For an infinite family of pairs of indistinguishable socks, what is needed to choose one sock from each pair?
  8. Let \(f:A\to B\) be surjective. Using the axiom of choice, which function \(g:B\to A\) can be constructed?
  9. A student claims that the family \(\{(0,n): n\in\mathbb{N}, n\ge 1\}\) admits no choice function without the axiom. Which counterexample refutes this claim?
  10. A student claims that, without the axiom of choice, every surjection \(p:X\to Y\) has a right inverse. What is correct to say about this claim?

What comes next

References

  • Herbert B. Enderton, Elements of Set Theory, 1st edition, Academic Press, 1977.
  • Thomas Jech, Set Theory (The Third Millennium Edition), 3rd millennium edition, Springer, 2003.