In the following exercise, we ask you to prove the equivalence of the choice axiom, the we...

In the following exercise, we ask you to prove the equivalence of the choice axiom, the well-ordering theorem, and the maximum principle. We comment that of these exercises, only Exercise 7 uses the choice axiom.

Using Exercises 1–4, construct an uncountable well-ordered set, as follows. Let  be the collection of all pairs (A, <), where A is a subset of ℤ+ and < is a well-ordering of A. (We allow A to be empty.) Define (A, <) ~ (A′, <′) if (A, <) and (A′, <′) have the same order type. It is trivial to show this is an equivalence relation. Let [(A, <)] denote the equivalence class of (A, <); let E denote the collection of these equivalence classes. Define

if (A, <) has the order type of a section of (A′, <′).

(a) Show that the relation ≪ is well defined and is a simple order on E. Note that the equivalence class [(∅, ∅)] is the smallest element of E.

(b) Show that if α = [(A, <)1 is an element of E, then (A, <) has the same order type as the section Sα(E) of E by α. [Hint: Define a map f : A → E by setting f(x) = [(Sx(A), restriction of <)] for each x ∈ A.]

(c) Conclude that E is well-ordered by ≪.

(d) Show that E is uncountable. [Hint: If h : E → ℤ+. is a bijection, then h gives rise to a well-ordering of ℤ+.]

This same argument, with ℤ+ replaced by an arbitrary well-ordered set X, proves (without use of the choice axiom) the existence of a well-ordered set E whose cardinality is greater than that of X.

This exercise shows that one can construct an uncountable well-ordered set, and hence the minimal uncountable well-ordered set, by an explicit construction that does not use the choice axiom. However, this result is less interesting than it might appear. The crucial property of SΩ, the one we use repeatedly, is the fact that every countable subset of SΩ has an upper bound in SΩ. That fact depends, in turn, on the fact that a countable union of countable sets is countable. And the proof of that result (if you examine it carefully) involves an infinite number of arbitrary choices—that is, it depends on the choice axiom.

Said differently, without the choice axiom we may be able to construct the minimal uncountable well-ordered set, but we can’t use it for anything!