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.

Use Exercises 1–5 to prove the following:

Theorem. The choice axiom is equivalent to the well-ordering theorem.

Proof. Let X be a set; let c be a fixed choice function for the nonempty subsets of X. If T is a subset of X andT, we say that (T, <) is a tower in X ifT and if for each x ∈ T,

where Sx(T) is the section of T by x.

(a) Let (T1, <1) and (T2, <2) be two towers in X. Show that either these two ordered sets are the same, or one equals a section of the other. [Hint: Switching indices if necessary, we can assume that h : T1 → T2 is order preserving and h(T1) equals either T2 or a section of T2. Use Exercise 2 to show that h(x) = x for all x.)

(b) If (T, <) is a tower in X and T ≠ X, show there is a tower in X of which (T, <) is a section.

(c) Let {(Tk, <k)| k ∈ K} be the collection of all towers in X. Let

Show that (T, <) is a tower in X. Conclude that T = X.