7 The Axiom of Choice (Revisited)

7
The Axiom of Choice (Revisited)

In Chapter 3 (see page 66), we first introduced the following principle, which is applied in many areas of mathematics.

Axiom of Choice. Let $\text{[math]}$ be an indexed function with nonempty terms. Then there is an indexed function $\text{[math]}$ such that $\text{[math]}$ , for all $\text{[math]}$ .

The above function $\text{[math]}$ , where $\text{[math]}$ for all $\text{[math]}$ , is called a choice function for $\text{[math]}$ . The axiom of choice is used to prove many theorems in mathematics. In real analysis, for example, the axiom of choice is (tacitly) applied to prove that a real valued function $\text{[math]}$ is continuous at a point $\text{[math]}$ if and only if $\text{[math]}$ for every sequence $\text{[math]}$ that converges to $\text{[math]}$ . It is thus said that continuity is equivalent to sequential continuity. The axiom of choice is also used to prove that every vector space has a basis.

In Chapter 3, it was shown that the axiom of choice implies the following theorem, which asserts the existence of another choice function $\text{[math]}$ .

Theorem 3.3.24 (AC). Let $\text{[math]}$ be a set of nonempty sets. Then there is a function $\text{[math]}$ such that $\text{[math]}$ for all $\text{[math]}$ .

It was then left as an exercise to show that Theorem 3.3.24 implies the axiom of choice. Hence, the theorem is actually equivalent to the axiom. Moreover, the axiom of choice is equivalent to a number of seemingly unrelated theorems. In this chapter, we will show that the axiom implies two other results that are also equivalent to it; but before we do this, we mention an application of the axiom of choice to topology, which concerns “product sets.”

Let $\text{[math]}$ be an indexed function with nonempty terms. The product set, denoted by $\text{[math]}$ , is defined by

: (7.1)

Typically, when $\text{[math]}$ is an infinite set, the only way to conclude that this product set is nonempty is to appeal to the axiom of choice as follows: Let $\text{[math]}$ be a choice function such that $\text{[math]}$ for all $\text{[math]}$ . Define $\text{[math]}$ by $\text{[math]}$ . Then $\text{[math]}$ , and thus, the product is nonempty.

Product sets are used to create a variety of topological spaces and to prove Tychonoff’s compactness theorem, a classic result in topology. In Chapter 9 (see Exercise 19 on page 226), one is asked to complete a proof of a theorem on product sets due to Julius König.

Many important consequences of the axiom of choice can be proved from the following weaker version.

Countable Axiom of Choice. Suppose that $\text{[math]}$ is an indexed function with nonempty terms. If $\text{[math]}$ is countable, then there is a function $\text{[math]}$ such that $\text{[math]}$ , for all $\text{[math]}$ .

Thus, if $\text{[math]}$ is a countable set of nonempty sets, then the countable axiom of choice implies there is a function $\text{[math]}$ such that $\text{[math]}$ for all $\text{[math]}$ . The axiom of choice, of course, implies the countable axiom of choice, but not conversely.

Finally, we remark that the replacement axiom shall not be applied in this chapter; however, it will be used in Chapters 8 and 9.

7.1 Zorn’s Lemma

Zorn’s Lemma, also known as the maximum principle, is an important theorem about partially ordered sets that is normally used to prove the existence of a mathematical object when it cannot be explicitly produced. According to Max Zorn, he first formulated his principle at Hamburg in 1933. Zorn published this maximum principle in 1935. Amil Artin then used Zorn’s principle to establish theorems in algebra. Artin later proved that the principle implies the axiom of choice.

In 1935, Zorn proposed adding his maximum principle to ZF, the axioms of set theory. Although Zorn was not the first to suggest such a principle, he demonstrated how useful his formulation was in applications, particularly in topology, abstract algebra, and real analysis. Zorn also asserted (but did not prove) that his lemma and the axiom of choice are equivalent. To review the concepts of a maximal element and a chain, see Definitions 3.4.6 and 3.4.14.

Zorn’s Lemma 7.1.1 (AC). Let $\text{[math]}$ be a partially ordered set. If every chain in $\text{[math]}$ has an upper bound, then $\text{[math]}$ contains a maximal element.

Our proof of Zorn’s Lemma 7.1.1 will apply “proof by contradiction”; that is, we shall let $\text{[math]}$ be a partially ordered set in which every chain has an upper bound. We will then assume that $\text{[math]}$ has no maximal elements and thereby derive a contradiction. The proof will depend on a few lemmas and definitions, which we now present.

Let $\text{[math]}$ be a partially ordered set and $\text{[math]}$ . Recalling Definition 3.4.8, an element $\text{[math]}$ is called an upper bound for $\text{[math]}$ when $\text{[math]}$ satisfies $\text{[math]}$ . We will say that $\text{[math]}$ is a proper upper bound if, in addition, we have that $\text{[math]}$ .

Definition 7.1.2. Let $\text{[math]}$ be a partially ordered set in which $\text{[math]}$ is a chain. Then $\text{[math]}$ is the set of proper upper bounds for $\text{[math]}$ .

If $\text{[math]}$ is a poset and $\text{[math]}$ is a chain, then

Thus, $\text{[math]}$ is nonempty if and only if $\text{[math]}$ has proper upper bounds in $\text{[math]}$ .

Definition 7.1.3. Let $\text{[math]}$ be a chain in $\text{[math]}$ , where $\text{[math]}$ is a partially ordered set. We shall say that $\text{[math]}$ is cofinal in $\text{[math]}$ when $\text{[math]}$ and for all $\text{[math]}$ , there is a $\text{[math]}$ such that $\text{[math]}$ .

Lemma 7.1.4. Suppose that $\text{[math]}$ is a poset and let $\text{[math]}$ be a chain. If $\text{[math]}$ is cofinal in $\text{[math]}$ , then $\text{[math]}$ .

Lemma 7.1.5. Let $\text{[math]}$ be a partially ordered set in which every chain has an upper bound. If $\text{[math]}$ has no maximal elements, then every chain $\text{[math]}$ in $\text{[math]}$ has a proper upper bound, and hence, $\text{[math]}$ is nonempty.

Proof. Assume that $\text{[math]}$ has no maximal elements. Let $\text{[math]}$ be a chain in $\text{[math]}$ . Since every chain in $\text{[math]}$ has an upper bound, let $\text{[math]}$ be an upper bound for $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ is a proper upper bound for $\text{[math]}$ . Suppose $\text{[math]}$ . So, because $\text{[math]}$ is not a maximal element, there is a $\text{[math]}$ such that $\text{[math]}$ . Thus, $\text{[math]}$ and $\text{[math]}$ is a proper upper bound for $\text{[math]}$ . ☐

We now present a proof of Zorn’s Lemma.

Proof (of Zorn’s Lemma 7.1.1). Let $\text{[math]}$ be a partially ordered set in which every chain $\text{[math]}$ has an upper bound in $\text{[math]}$ . We will prove that there is an $\text{[math]}$ such that $\text{[math]}$ is a maximal element. Assume, for a contradiction, that $\text{[math]}$ has no maximal elements. By Lemma 7.1.5 and the axiom of choice, there is a function $\text{[math]}$ such that $\text{[math]}$ whenever $\text{[math]}$ is a chain in $\text{[math]}$ . As $\text{[math]}$ , we see that

: (7.2)

A chain $\text{[math]}$ in $\text{[math]}$ shall be called a ladder if whenever $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ is the smallest element in $\text{[math]}$ (see Definition 3.4.11 on page 73). In other words, if $\text{[math]}$ and $\text{[math]}$ has a proper upper bound in $\text{[math]}$ , then $\text{[math]}$ and $\text{[math]}$ is the smallest element in $\text{[math]}$ that is a proper upper bound for $\text{[math]}$ .

Ladders exist. To confirm this, note that $\text{[math]}$ is (vacuously) a ladder and that $\text{[math]}$ . For another example, let $\text{[math]}$ . Since $\text{[math]}$ is a chain, we have that $\text{[math]}$ . One can show that the set $\text{[math]}$ is also a ladder.

Claim 1. Suppose $\text{[math]}$ where $\text{[math]}$ and $\text{[math]}$ are ladders. Let $\text{[math]}$ and $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ .

Proof. Let $\text{[math]}$ and $\text{[math]}$ are as in the claim. Let $\text{[math]}$ and $\text{[math]}$ . Assume that $\text{[math]}$ . Suppose, for a contradiction, that $\text{[math]}$ . Thus, $\text{[math]}$ . Let $\text{[math]}$ be defined by

: (7.3)

So, $\text{[math]}$ . Since $\text{[math]}$ , we also have that $\text{[math]}$ . Clearly, $\text{[math]}$ is a proper upper bound for $\text{[math]}$ . Because $\text{[math]}$ is a ladder, it follows that

: (7.4)

Now, because $\text{[math]}$ and $\text{[math]}$ , the set $\text{[math]}$ also has a proper upper bound in $\text{[math]}$ . Thus, $\text{[math]}$ . Since $\text{[math]}$ and $\text{[math]}$ , (7.4) implies that $\text{[math]}$ . Hence, $\text{[math]}$ by (7.3), and this contradicts (7.2). (Claim 1) ☐

Claim 2. Suppose that $\text{[math]}$ and $\text{[math]}$ are ladders. Then either $\text{[math]}$ or $\text{[math]}$ .

Proof. Let $\text{[math]}$ and $\text{[math]}$ be ladders. Assume, for a contradiction, that $\text{[math]}$ and $\text{[math]}$ . Hence, there is an $\text{[math]}$ so that $\text{[math]}$ and a $\text{[math]}$ so that $\text{[math]}$ . Let

: (7.5)

Clearly, $\text{[math]}$ and $\text{[math]}$ . Because $\text{[math]}$ and $\text{[math]}$ is a proper upper bound for $\text{[math]}$ , it follows that $\text{[math]}$ and $\text{[math]}$ . Similarly, as $\text{[math]}$ and $\text{[math]}$ is a proper upper bound for $\text{[math]}$ , we see that $\text{[math]}$ and $\text{[math]}$ . So, in summary, we have

So $\text{[math]}$ by (1), and $\text{[math]}$ by (2). Since $\text{[math]}$ and $\text{[math]}$ , we conclude from (7.5) that $\text{[math]}$ , contradicting (7.2). (Claim 2) ☐

Now let $\text{[math]}$ . By the power set and subset axioms, we see that $\text{[math]}$ is a set. Therefore, $\text{[math]}$ is the set of all ladders.

Claim 3. $\text{[math]}$ is a ladder.

Proof. To see that $\text{[math]}$ is a chain, let $\text{[math]}$ and $\text{[math]}$ be in $\text{[math]}$ . Hence, $\text{[math]}$ for some $\text{[math]}$ , and $\text{[math]}$ for some $\text{[math]}$ . By Claim 2, either $\text{[math]}$ or $\text{[math]}$ . So, we can assume that $\text{[math]}$ and $\text{[math]}$ are in $\text{[math]}$ . As $\text{[math]}$ is a chain, either $\text{[math]}$ or $\text{[math]}$ . Thus, $\text{[math]}$ is a chain. Suppose $\text{[math]}$ has a proper upper bound in $\text{[math]}$ , say, $\text{[math]}$ . We shall show that $\text{[math]}$ and $\text{[math]}$ . Since $\text{[math]}$ , we have that $\text{[math]}$ for some $\text{[math]}$ . We will now show that $\text{[math]}$ . Let $\text{[math]}$ . So, $\text{[math]}$ . Because $\text{[math]}$ , it follows that $\text{[math]}$ for some $\text{[math]}$ . By Claim 2, either $\text{[math]}$ or $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ . If $\text{[math]}$ , then (as $\text{[math]}$ and $\text{[math]}$ ) Claim 1 implies that $\text{[math]}$ . Hence, $\text{[math]}$ , and $\text{[math]}$ is a proper upper bound for $\text{[math]}$ . Since $\text{[math]}$ is a ladder, $\text{[math]}$ and $\text{[math]}$ . Consequently, $\text{[math]}$ and $\text{[math]}$ . Therefore, $\text{[math]}$ is a ladder. (Claim 3) ☐

Let $\text{[math]}$ . As $\text{[math]}$ is the set of all ladders, ( $\text{[math]}$ ) $\text{[math]}$ whenever $\text{[math]}$ is a ladder. Claim 3 states that $\text{[math]}$ is a ladder. Since $\text{[math]}$ is a chain, we have by assumption that $\text{[math]}$ is nonempty. Thus, $\text{[math]}$ . Let $\text{[math]}$ .

Claim 4. $\text{[math]}$ is a ladder.

Proof. Since $\text{[math]}$ is a chain and $\text{[math]}$ for each $\text{[math]}$ , it follows that $\text{[math]}$ is a chain. Let $\text{[math]}$ have a proper upper bound $\text{[math]}$ in $\text{[math]}$ . Thus, $\text{[math]}$ and $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ and $\text{[math]}$ , because $\text{[math]}$ is a ladder. If $\text{[math]}$ , then $\text{[math]}$ , and there are two cases to consider.

CASE 1: $\text{[math]}$ is not cofinal in $\text{[math]}$ . Thus, $\text{[math]}$ has a proper upper bound $\text{[math]}$ in $\text{[math]}$ . Hence, $\text{[math]}$ and $\text{[math]}$ as $\text{[math]}$ is a ladder. Therefore, $\text{[math]}$ and $\text{[math]}$ because $\text{[math]}$ .

CASE 2: $\text{[math]}$ is cofinal in $\text{[math]}$ . Lemma 7.1.4 implies that $\text{[math]}$ . So we clearly have that $\text{[math]}$ and $\text{[math]}$ . (Claim 4) ☐

Since $\text{[math]}$ is a ladder, ( $\text{[math]}$ ) implies that $\text{[math]}$ . As $\text{[math]}$ , we conclude that $\text{[math]}$ , and this contradicts (7.2). (Zorn’s Lemma) ☐

Hence, the axiom of choice implies Zorn’s Lemma 7.1.1. Moreover, one can also prove that Zorn’s Lemma implies the axiom of choice (see Exercise 10). A different proof of Zorn’s Lemma is summarized in Exercise 14 on page 193; however, this alternative proof relies on ordinals and the replacement axiom.

Corollary 7.1.6 (AC). Suppose that $\text{[math]}$ is a partially ordered set in which every chain has an upper bound. For each $\text{[math]}$ , there exists a maximal element $\text{[math]}$ such that $\text{[math]}$ .

Proof. Let $\text{[math]}$ be a poset in which every chain has an upper bound, and let $\text{[math]}$ . Define $\text{[math]}$ and $\text{[math]}$ . Thus, $\text{[math]}$ is a partially ordered set (see Exercise 14 on page 76) in which every chain has an upper bound. By Zorn’s Lemma, $\text{[math]}$ has a maximal element $\text{[math]}$ . So $\text{[math]}$ and $\text{[math]}$ is a maximal element in $\text{[math]}$ . ☐

7.1.1 Two Applications of Zorn’s Lemma

Zorn’s Lemma is frequently applied to posets of the form $\text{[math]}$ where $\text{[math]}$ is a set (of sets) and $\text{[math]}$ is the subset relation (see Problem 1 on page 70). In such applications, one proceeds as described in Exercise 5. We will now present two theorems whose proofs apply Zorn’s Lemma as outlined by Exercise 5.

The first theorem, often called the comparability theorem, shows that one can compare the cardinalities of any two sets (see Definition 5.4.14). First, we shall state and prove a relevant lemma.

Lemma 7.1.7. Let $\text{[math]}$ . If $\text{[math]}$ is a maximal element in the poset $\text{[math]}$ , then either $\text{[math]}$ or $\text{[math]}$ .

Proof. Let $\text{[math]}$ be the poset defined in the statement of the lemma, and let $\text{[math]}$ be a maximal element in $\text{[math]}$ . Clearly, $\text{[math]}$ and $\text{[math]}$ . We shall prove the either $\text{[math]}$ or $\text{[math]}$ . Suppose, for a contradiction, that $\text{[math]}$ and $\text{[math]}$ . Let $\text{[math]}$ and $\text{[math]}$ . Now let $\text{[math]}$ . Clearly, $\text{[math]}$ . Because $\text{[math]}$ and $\text{[math]}$ , it follows that $\text{[math]}$ is a one-to-one function. Thus, $\text{[math]}$ . Since $\text{[math]}$ and $\text{[math]}$ , this contradicts the fact that $\text{[math]}$ is maximal. Therefore, either $\text{[math]}$ or $\text{[math]}$ . ☐

We can now state and prove the comparability theorem, which is actually equivalent to the axiom of choice (see Exercise 23, page 218).

Theorem 7.1.8 (AC). For any two sets $\text{[math]}$ and $\text{[math]}$ , either $\text{[math]}$ or $\text{[math]}$ .

Proof. Let $\text{[math]}$ and $\text{[math]}$ be sets, and let $\text{[math]}$ . We will show that every chain in the poset $\text{[math]}$ has an upper bound. To do this, suppose that $\text{[math]}$ is a chain. Thus, for all $\text{[math]}$ and $\text{[math]}$ , we have that either $\text{[math]}$ or $\text{[math]}$ . Clearly, $\text{[math]}$ . Exercise 11 on page 68 shows that $\text{[math]}$ is a one-to-one function. So $\text{[math]}$ and $\text{[math]}$ for each $\text{[math]}$ . We conclude that $\text{[math]}$ is an upper bound for $\text{[math]}$ . Hence, by Zorn’s Lemma, the poset $\text{[math]}$ has a maximal element $\text{[math]}$ . Lemma 7.1.7 asserts that either $\text{[math]}$ or $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ because $\text{[math]}$ is one-to-one. If $\text{[math]}$ , then $\text{[math]}$ as $\text{[math]}$ is one-to-one by Corollary 3.3.15 and Theorem 3.2.7. ☐

Our second theorem, identified as the order-extension principle, shows that any partial order on a set can be extended to a total order on the same set. A proof of this theorem was first published by Edward Marczewski in 1930. Our proof will apply Zorn’s Lemma to a partial order on a set of partial orders. We first state and prove a useful lemma, which shows that if a partial order is not a total order, then it can be extended to a larger partial order.

Lemma 7.1.9. If $\text{[math]}$ is a partial order on $\text{[math]}$ that is not a total order on $\text{[math]}$ , then there is a partial order $\text{[math]}$ on $\text{[math]}$ such that $\text{[math]}$ and $\text{[math]}$ .

Proof. Let $\text{[math]}$ is a partial order on $\text{[math]}$ that is not a total order on $\text{[math]}$ . Since $\text{[math]}$ is not a total order, there exist $\text{[math]}$ and $\text{[math]}$ such that ( $\text{[math]}$ ) $\text{[math]}$ and $\text{[math]}$ . Let $\text{[math]}$ be defined by

Because $\text{[math]}$ is reflexive on $\text{[math]}$ , we see that $\text{[math]}$ and $\text{[math]}$ . Thus, $\text{[math]}$ . Let $\text{[math]}$ . So $\text{[math]}$ . Also, $\text{[math]}$ as $\text{[math]}$ and $\text{[math]}$ by ( $\text{[math]}$ ). We will now show that $\text{[math]}$ is a partial order on $\text{[math]}$ . Since $\text{[math]}$ , we have that

: (7.6)

Let $\text{[math]}$ . Since $\text{[math]}$ , we see from (7.6) that $\text{[math]}$ . So $\text{[math]}$ is reflexive on $\text{[math]}$ . To show that $\text{[math]}$ is antisymmetric, suppose that $\text{[math]}$ and $\text{[math]}$ . We shall show that $\text{[math]}$ . Since $\text{[math]}$ and $\text{[math]}$ , the equivalence in (7.6) yields the following four cases (three of which, as we will see, cannot hold):

1. $\text{[math]}$ and $\text{[math]}$ . Since $\text{[math]}$ is antisymmetric, we conclude that $\text{[math]}$ .

2. $\text{[math]}$ and $\text{[math]}$ . So ( $\text{[math]}$ ) $\text{[math]}$ , ( $\text{[math]}$ ) $\text{[math]}$ , ( $\text{[math]}$ ) $\text{[math]}$ . Conditions ( $\text{[math]}$ ) and ( $\text{[math]}$ ) imply that $\text{[math]}$ . Hence, ( $\text{[math]}$ ) implies that $\text{[math]}$ , which contradicts ( $\text{[math]}$ ).

3. $\text{[math]}$ and $\text{[math]}$ . As in the previous case 2, this is impossible.

4. $\text{[math]}$ and $\text{[math]}$ . Thus, ( $\text{[math]}$ ) $\text{[math]}$ , ( $\text{[math]}$ ) $\text{[math]}$ , ( $\text{[math]}$ ) $\text{[math]}$ , ( $\text{[math]}$ ) $\text{[math]}$ . Clearly, ( $\text{[math]}$ ) and ( $\text{[math]}$ ) imply that $\text{[math]}$ , contradicting ( $\text{[math]}$ ).

Because case 1 is the only possibility, we conclude that $\text{[math]}$ is antisymmetric. Finally, we now show that $\text{[math]}$ is transitive. Assume $\text{[math]}$ and $\text{[math]}$ . We must show that $\text{[math]}$ . As $\text{[math]}$ and $\text{[math]}$ , the equivalence (7.6) again yields four cases to consider:

1. $\text{[math]}$ and $\text{[math]}$ . Since $\text{[math]}$ is transitive, we conclude that $\text{[math]}$ .

2. $\text{[math]}$ and $\text{[math]}$ . Thus, ( $\text{[math]}$ ) $\text{[math]}$ , ( $\text{[math]}$ ) $\text{[math]}$ , ( $\text{[math]}$ ) $\text{[math]}$ . As ( $\text{[math]}$ ) and ( $\text{[math]}$ ) imply that $\text{[math]}$ , we see from ( $\text{[math]}$ ) that $\text{[math]}$ and $\text{[math]}$ . Hence, $\text{[math]}$ .

3. $\text{[math]}$ and $\text{[math]}$ . So ( $\text{[math]}$ ) $\text{[math]}$ , ( $\text{[math]}$ ) $\text{[math]}$ , ( $\text{[math]}$ ) $\text{[math]}$ . Since ( $\text{[math]}$ ) and ( $\text{[math]}$ ) imply that $\text{[math]}$ , we conclude from ( $\text{[math]}$ ) that $\text{[math]}$ and $\text{[math]}$ . Thus, $\text{[math]}$ .

4. $\text{[math]}$ and $\text{[math]}$ . Hence, ( $\text{[math]}$ ) $\text{[math]}$ , ( $\text{[math]}$ ) $\text{[math]}$ , ( $\text{[math]}$ ) $\text{[math]}$ , ( $\text{[math]}$ ) $\text{[math]}$ . Clearly, ( $\text{[math]}$ ) and ( $\text{[math]}$ ) imply that $\text{[math]}$ , contradicting ( $\text{[math]}$ ).

In each of the valid cases, we have either $\text{[math]}$ or $\text{[math]}$ . Thus, by (7.6), $\text{[math]}$ . Hence, $\text{[math]}$ is a partial order on $\text{[math]}$ such that $\text{[math]}$ and $\text{[math]}$ . ☐

We can now show that Zorn’s Lemma implies the order-extension principle.

Theorem 7.1.10 (AC). Let $\text{[math]}$ be a partial order on $\text{[math]}$ . Then there exists a total order $\text{[math]}$ on $\text{[math]}$ such that $\text{[math]}$ .

Proof. Let $\text{[math]}$ be a partial order on $\text{[math]}$ , and let

Hence, $\text{[math]}$ . We now show that every chain in the poset $\text{[math]}$ has an upper bound. Let $\text{[math]}$ be a chain. Thus, for all $\text{[math]}$ and $\text{[math]}$ , either $\text{[math]}$ or $\text{[math]}$ . Clearly, $\text{[math]}$ . Exercises 17 and 18 on page 76 imply that $\text{[math]}$ is a partial order on $\text{[math]}$ . So $\text{[math]}$ and $\text{[math]}$ for all $\text{[math]}$ . Hence, $\text{[math]}$ is an upper bound for $\text{[math]}$ . Hence, by Corollary 7.1.6, there is a maximal element $\text{[math]}$ such that $\text{[math]}$ . Since $\text{[math]}$ is maximal, Lemma 7.1.9 implies that $\text{[math]}$ is a total order on $\text{[math]}$ . ☐

Exercises 7.1

1. Let $\text{[math]}$ be an indexed function so that $\text{[math]}$ , for all $\text{[math]}$ . Without appealing to the axiom of choice, prove that if $\text{[math]}$ is countably infinite, then there is a function $\text{[math]}$ such that $\text{[math]}$ , for all $\text{[math]}$ .

2. Let $\text{[math]}$ , and let $\text{[math]}$ denote $\text{[math]}$ . Now suppose that for all $\text{[math]}$ , there is a $\text{[math]}$ such that $\text{[math]}$ . Using the axiom of choice, show that there is a function $\text{[math]}$ such that $\text{[math]}$ for all $\text{[math]}$ .

3. Let $\text{[math]}$ , and let $\text{[math]}$ denote $\text{[math]}$ . Suppose that $\text{[math]}$ and for all $\text{[math]}$ , there is a $\text{[math]}$ such that $\text{[math]}$ . By Exercise 2 and the axiom of choice, there is an $\text{[math]}$ such that $\text{[math]}$ for all $\text{[math]}$ . Using Theorem 4.2.1, show that there is a function $\text{[math]}$ such that $\text{[math]}$ for all $\text{[math]}$ .

4. Prove Lemma 7.1.4.

5. Let $\text{[math]}$ be a partially ordered set where $\text{[math]}$ is a set (of sets). Suppose that for every chain $\text{[math]}$ we have that $\text{[math]}$ is in $\text{[math]}$ .

(a) Let $\text{[math]}$ be a chain. Prove that $\text{[math]}$ is an upper bound for $\text{[math]}$ .

(b) Using Zorn’s Lemma, show that there exists an $\text{[math]}$ that is maximal, that is, $\text{[math]}$ is not the proper subset of any $\text{[math]}$ .

6. Let $\text{[math]}$ and $\text{[math]}$ . Consider the partially ordered set $\text{[math]}$ .

(a) Using Zorn’s Lemma, show that there is an $\text{[math]}$ that is maximal.

(b) Prove that if $\text{[math]}$ is onto $\text{[math]}$ , then $\text{[math]}$ is a bijection.

7. Let $\text{[math]}$ be a poset. Let $\text{[math]}$ . Consider the partially ordered set $\text{[math]}$ .

(a) Let $\text{[math]}$ be a chain in $\text{[math]}$ . Show that $\text{[math]}$ is a chain in $\text{[math]}$ .

(b) Conclude, via Zorn’s Lemma, that there exists a chain $\text{[math]}$ in $\text{[math]}$ that is maximal, that is, $\text{[math]}$ is not the proper subset of any other chain in $\text{[math]}$ .

8. Let $\text{[math]}$ be the set of nonzero natural numbers. Then $\text{[math]}$ is a poset where $\text{[math]}$ is the divisibility relation on $\text{[math]}$ (see Problem 2 on page 71). Define a partial order $\text{[math]}$ on $\text{[math]}$ such that $\text{[math]}$ and $\text{[math]}$ .

9. Using Theorem 7.1.10, show there is a total order $\text{[math]}$ on $\text{[math]}$ such that for all $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ . Show that $\text{[math]}$ on $\text{[math]}$ .

10. Let $\text{[math]}$ be an indexed function with nonempty terms, and let

Thus, $\text{[math]}$ is a partially ordered set. Assuming Zorn’s Lemma, prove the axiom of choice as follows:

(a) Let $\text{[math]}$ be a chain. Prove that $\text{[math]}$ is in $\text{[math]}$ and is an upper bound for $\text{[math]}$ .

(b) Conclude, via Zorn’s Lemma, that $\text{[math]}$ has a maximal element $\text{[math]}$ .

Exercise Notes: The conclusion of Exercise 3 is called the axiom of dependent choices (DC). For Exercise 6(a), apply Exercise 5. Exercise 7 shows that Zorn’s Lemma implies the Hausdorff maximal principle, which proclaims that every partially ordered set contains a maximal chain. This principle is also equivalent to the axiom of choice. For Exercise 10(a), see Exercise 11(a) on page 68.

7.2 Filters and Ultrafilters

We now introduce the concept of a filter, which has a variety of applications in set theory and in topology. Filters were introduced by Henri Cartan in 1937 and subsequently used by Bourbaki in the book Topologie générale.

The motivation for our next definition is to give meaning to the intuitive notion of a “large” subset of $\text{[math]}$ .

Definition 7.2.1. Let $\text{[math]}$ be nonempty and let $\text{[math]}$ . Then $\text{[math]}$ is a filter on $\text{[math]}$ if it satisfies the following three conditions:

(1) $\text{[math]}$ and $\text{[math]}$ .

(2) If $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ .

(3) If $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ .

So if $\text{[math]}$ and $\text{[math]}$ is a filter, then $\text{[math]}$ behaves like a “large” set.

If $\text{[math]}$ is a filter on $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ . To prove this, suppose that $\text{[math]}$ . Thus, by Definition 7.2.1(2), $\text{[math]}$ , which contradicts Definition 7.2.1(1).

Clearly, the singleton set $\text{[math]}$ is a filter on any nonempty set $\text{[math]}$ . For another example, let $\text{[math]}$ be a nonempty subset of $\text{[math]}$ and let $\text{[math]}$ . One can verify (see Exercise 1) that $\text{[math]}$ satisfies the conditions of Definition 7.2.1. Hence, $\text{[math]}$ is a filter on $\text{[math]}$ , and it is called the filter on $\text{[math]}$ generated by $\text{[math]}$ . When $\text{[math]}$ is a singleton, then $\text{[math]}$ shall be called a principal filter. For example, if $\text{[math]}$ , then the principal filter generated by $\text{[math]}$ can be expressed by

: (7.7)

Definition 7.2.2. Let $\text{[math]}$ be a filter on $\text{[math]}$ . We say that $\text{[math]}$ is a maximal filter if for all filters $\text{[math]}$ on $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ .

If $\text{[math]}$ , then the principal filter $\text{[math]}$ generated by $\text{[math]}$ is a maximal filter. To see why it is maximal, let $\text{[math]}$ be a filter on $\text{[math]}$ so that $\text{[math]}$ . Let $\text{[math]}$ . To prove that $\text{[math]}$ , assume $\text{[math]}$ . Thus, $\text{[math]}$ and $\text{[math]}$ . So $\text{[math]}$ , and hence, $\text{[math]}$ . Since $\text{[math]}$ , we conclude from Definition 7.2.1(1) that $\text{[math]}$ , a contradiction. So $\text{[math]}$ and $\text{[math]}$ . On the other hand, for $\text{[math]}$ and $\text{[math]}$ where $\text{[math]}$ , one can verify that the filter generated by $\text{[math]}$ is not maximal.

We now present an example of a nonprincipal filter. Let $\text{[math]}$ be an infinite set. Let $\text{[math]}$ be defined by

One can show that $\text{[math]}$ is a filter on $\text{[math]}$ . For example, to verify Definition 7.2.1(2), let $\text{[math]}$ and $\text{[math]}$ be in $\text{[math]}$ . Since $\text{[math]}$ , we conclude that $\text{[math]}$ is finite, as $\text{[math]}$ and $\text{[math]}$ are finite. Thus, $\text{[math]}$ is in $\text{[math]}$ . A set $\text{[math]}$ is said to be a cofinite subset of $\text{[math]}$ , if $\text{[math]}$ and $\text{[math]}$ is finite. So the filter $\text{[math]}$ is called the filter of all cofinite subsets of $\text{[math]}$ . To show that $\text{[math]}$ is not a principal filter, let $\text{[math]}$ and $\text{[math]}$ . Consider the set $\text{[math]}$ . Then $\text{[math]}$ (because $\text{[math]}$ is finite) and $\text{[math]}$ . Therefore, $\text{[math]}$ is not generated by any singleton.

Definition 7.2.3. Let $\text{[math]}$ be a filter on $\text{[math]}$ . Then $\text{[math]}$ is said to be an ultrafilter on $\text{[math]}$ if for all $\text{[math]}$ , either $\text{[math]}$ or $\text{[math]}$ .

Let $\text{[math]}$ . The principle filter $\text{[math]}$ generated by $\text{[math]}$ (see (7.7)) is an ultrafilter. So there are principal ultrafilters. Do nonprincipal ultrafilters exist? Let $\text{[math]}$ be an infinite set and let $\text{[math]}$ be the filter of all cofinite subsets of $\text{[math]}$ . Our goal in this section is to prove a result that implies the existence of an ultrafilter $\text{[math]}$ such that $\text{[math]}$ . Exercise 9 then implies that $\text{[math]}$ is nonprincipal. Thus, nonprincipal ultrafilters do, in fact, exist.

The following lemma identifies two important properties that an ultrafilter possesses.

Lemma 7.2.4. Let $\text{[math]}$ be an ultrafilter on $\text{[math]}$ .

(1) For all $\text{[math]}$ and $\text{[math]}$ , if $\text{[math]}$ , then either $\text{[math]}$ or $\text{[math]}$ .

(2) Let $\text{[math]}$ be a filter on $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ .

Proof. The proofs of (1) and (2) are left for Exercises 7 and 8, respectively. ☐

Lemma 7.2.4(2) shows that an ultrafilter is maximal. Furthermore, if a filter is maximal, then it is an ultrafilter (see Exercise 15).

Definition 7.2.5. Let $\text{[math]}$ and $\text{[math]}$ be nonempty. Then $\text{[math]}$ has the finite intersection property if whenever $\text{[math]}$ is nonempty and finite, then $\text{[math]}$ .

Lemma 7.2.6. Let $\text{[math]}$ and $\text{[math]}$ be nonempty. Suppose that $\text{[math]}$ has the finite intersection property. Then there is a filter $\text{[math]}$ on $\text{[math]}$ such that $\text{[math]}$ .

Proof. Let $\text{[math]}$ . Assume $\text{[math]}$ has the finite intersection property. Define

Clearly, $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ . We shall prove that $\text{[math]}$ is a filter; that is, we will establish items (2) and (3) of Definition 7.2.1. Let $\text{[math]}$ and $\text{[math]}$ . So $\text{[math]}$ and $\text{[math]}$ where $\text{[math]}$ and $\text{[math]}$ are nonempty and finite. Thus, $\text{[math]}$ . Exercise 12 on page 40 implies that $\text{[math]}$ . Hence, $\text{[math]}$ . Since $\text{[math]}$ is a finite subset of $\text{[math]}$ (see Exercise 15 on page 116), we have that $\text{[math]}$ . Thus, (2) of Definition 7.2.1 holds. To prove (3), let $\text{[math]}$ and $\text{[math]}$ . Since $\text{[math]}$ for some nonempty finite $\text{[math]}$ , it follows that $\text{[math]}$ . Therefore, $\text{[math]}$ is a filter. ☐

Definition 7.2.7. Let $\text{[math]}$ and $\text{[math]}$ be nonempty. Then $\text{[math]}$ is closed under finite intersections if whenever $\text{[math]}$ is nonempty and finite, then $\text{[math]}$ .

One can prove by induction that a filter is closed under finite intersections, and therefore, a filter has the finite intersection property (see Exercise 2).

Lemma 7.2.8. Let $\text{[math]}$ be a filter on $\text{[math]}$ . Suppose that $\text{[math]}$ is such that $\text{[math]}$ and $\text{[math]}$ . Then the set $\text{[math]}$ has the finite intersection property.

Proof. Let $\text{[math]}$ be a filter on $\text{[math]}$ , and suppose that $\text{[math]}$ is such that $\text{[math]}$ and ( $\text{[math]}$ ) $\text{[math]}$ . Because $\text{[math]}$ is a filter, ( $\text{[math]}$ ) implies that $\text{[math]}$ .

Claim. For every $\text{[math]}$ , we have that $\text{[math]}$ .

Proof. Assume, for a contradiction that $\text{[math]}$ for some $\text{[math]}$ . Since $\text{[math]}$ and $\text{[math]}$ , it follows that $\text{[math]}$ . Thus, because $\text{[math]}$ is a filter, we have that $\text{[math]}$ , which contradicts ( $\text{[math]}$ ). (Claim) ☐

Let $\text{[math]}$ be finite and nonempty. So either $\text{[math]}$ or $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ . As $\text{[math]}$ has the finite intersection property, it follows that $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ for a finite $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ , and thus, $\text{[math]}$ . If $\text{[math]}$ , then one can show that $\text{[math]}$ . Since $\text{[math]}$ is closed under finite intersections, $\text{[math]}$ . Hence, $\text{[math]}$ by the above claim. Thus, $\text{[math]}$ and $\text{[math]}$ has the finite intersection property. (Lemma) ☐

Lemmas 7.2.6 and 7.2.8, together with Zorn’s Lemma, imply the following theorem, which has many applications in mathematics.

Ultrafilter Theorem 7.2.9 (AC). If $\text{[math]}$ is a filter on $\text{[math]}$ , then there is an ultrafilter $\text{[math]}$ on $\text{[math]}$ such that $\text{[math]}$ .

Proof. See Exercise 14. ☐

7.2.1 Ideals

Filters allowed us to investigate the concept of a “large” subset of a set $\text{[math]}$ . Ideals allow us to pursue the concept of a “small” subset of $\text{[math]}$ . As we will see, given a filter on $\text{[math]}$ , one can construct an ideal on $\text{[math]}$ , and conversely.

Definition 7.2.10. Let $\text{[math]}$ be nonempty and let $\text{[math]}$ . We say that $\text{[math]}$ is an ideal on $\text{[math]}$ if it satisfies the following three conditions:

(1) $\text{[math]}$ and $\text{[math]}$ .

(2) If $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ .

(3) If $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ .

The singleton $\text{[math]}$ is an ideal on any nonempty set $\text{[math]}$ . Let $\text{[math]}$ be a proper subset and let

The set $\text{[math]}$ is an ideal, since it clearly satisfies the conditions of Definition 7.2.10. This ideal $\text{[math]}$ is called the ideal on $\text{[math]}$ generated by $\text{[math]}$ .

The following lemma shows that there is an intimate connection between filters and ideals.

Lemma 7.2.11. Let $\text{[math]}$ be nonempty. Then the following hold:

(1) If $\text{[math]}$ is a filter on $\text{[math]}$ , the $\text{[math]}$ is an ideal on $\text{[math]}$ .

(2) If $\text{[math]}$ is an ideal on $\text{[math]}$ , the $\text{[math]}$ is a filter on $\text{[math]}$ .

Proof. See Exercises 19 and 20. ☐

Let $\text{[math]}$ and $\text{[math]}$ be as in Lemma 7.2.11. Then $\text{[math]}$ is called the dual ideal, and $\text{[math]}$ is called the dual filter. It is easy to show that $\text{[math]}$ and $\text{[math]}$ .

Definition 7.2.12. Let $\text{[math]}$ be an ideal on $\text{[math]}$ . Then $\text{[math]}$ is said to be a prime ideal on $\text{[math]}$ if for all $\text{[math]}$ , either $\text{[math]}$ or $\text{[math]}$ .

Theorem 7.2.13. Let $\text{[math]}$ be a nonempty set. Then $\text{[math]}$ is an ultrafilter on $\text{[math]}$ if and only if $\text{[math]}$ is a prime ideal on $\text{[math]}$ .

Proof. See Exercise 21. ☐

Finally, let $\text{[math]}$ be an ideal on $\text{[math]}$ . Then $\text{[math]}$ is said to be a maximal ideal if for all ideals $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ . One can prove that a prime ideal is maximal (see Exercise 22).

Exercises 7.2

1. Let $\text{[math]}$ where $\text{[math]}$ is nonempty. Let $\text{[math]}$ . Prove that $\text{[math]}$ is a filter on $\text{[math]}$ .

2. Let $\text{[math]}$ be a filter on $\text{[math]}$ . Prove that $\text{[math]}$ is closed under finite intersections. Conclude that $\text{[math]}$ has the finite intersection property.

3. Let $\text{[math]}$ and $\text{[math]}$ where $\text{[math]}$ . Prove that the filter generated by $\text{[math]}$ is not maximal.

4. Let $\text{[math]}$ be a filter on a nonempty set $\text{[math]}$ . Let $\text{[math]}$ . Prove that $\text{[math]}$ is a filter on $\text{[math]}$ .

5. Suppose that $\text{[math]}$ is an infinite set, and let $\text{[math]}$ be a cofinite subset of $\text{[math]}$ . Prove the following two items:

(a) If $\text{[math]}$ , then $\text{[math]}$ is a cofinite subset of $\text{[math]}$ .

(b) If $\text{[math]}$ is a cofinite subset of $\text{[math]}$ , then $\text{[math]}$ is a cofinite subset of $\text{[math]}$ .

6. Let $\text{[math]}$ be the filter of cofinite subsets of $\text{[math]}$ . Show that $\text{[math]}$ is not an ultrafilter.

7. Prove Lemma 7.2.4(2).

8. Prove Lemma 7.2.4(3).

9. Let $\text{[math]}$ be an infinite set and let $\text{[math]}$ be the filter of all cofinite subsets of $\text{[math]}$ . Suppose $\text{[math]}$ is a filter on $\text{[math]}$ such that $\text{[math]}$ .

(a) Prove that every $\text{[math]}$ is infinite.

(b) Prove that $\text{[math]}$ is nonprincipal.

10. Let $\text{[math]}$ be a nonempty set of filters on $\text{[math]}$ . Prove that $\text{[math]}$ is a filter on $\text{[math]}$ .

11. Let $\text{[math]}$ be filter on $\text{[math]}$ and let $\text{[math]}$ .

(a) Prove that if $\text{[math]}$ , then $\text{[math]}$ for all $\text{[math]}$ .

(b) Suppose that $\text{[math]}$ is an ultrafilter on $\text{[math]}$ and $\text{[math]}$ . Conclude that $\text{[math]}$ is the principal filter on $\text{[math]}$ generated by $\text{[math]}$ .

12. Let $\text{[math]}$ be an ultrafilter on $\text{[math]}$ .

(a) Suppose there is a finite set in $\text{[math]}$ . Prove that $\text{[math]}$ for some $\text{[math]}$ .

(b) Conclude that if $\text{[math]}$ is nonprincipal, then every $\text{[math]}$ is infinite.

13. Show that $\text{[math]}$ , whenever $\text{[math]}$ is an ultrafilter on $\text{[math]}$ .

14. Let $\text{[math]}$ be a filter on $\text{[math]}$ . Let $\text{[math]}$ . Note that $\text{[math]}$ . Consider the partially ordered set $\text{[math]}$ .

(a) Let $\text{[math]}$ be a chain. Prove that $\text{[math]}$ and that $\text{[math]}$ is an upper bound for $\text{[math]}$ .

(b) Show, via Corollary 7.1.6, that $\text{[math]}$ has a maximal element $\text{[math]}$ such that $\text{[math]}$ .

15. Let $\text{[math]}$ be a filter on $\text{[math]}$ . Prove that $\text{[math]}$ is an ultrafilter if and only if $\text{[math]}$ is maximal.

16. Let $\text{[math]}$ be a filter on $\text{[math]}$ . Let $\text{[math]}$ . Define the relation $\text{[math]}$ on $\text{[math]}$ by

for all $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ . Prove that $\text{[math]}$ is an equivalence relation on $\text{[math]}$ .

17. Let $\text{[math]}$ be an ultrafilter on $\text{[math]}$ . Let $\text{[math]}$ . Suppose that $\text{[math]}$ is a total preorder on $\text{[math]}$ . Define the relation $\text{[math]}$ on $\text{[math]}$ by

for all $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ . Prove that $\text{[math]}$ is total preorder on $\text{[math]}$ .

18. Let $\text{[math]}$ be an ultrafilter on $\text{[math]}$ and let $\text{[math]}$ . Define the set

Prove that $\text{[math]}$ is an ultrafilter on $\text{[math]}$ .

19. Prove Theorem 7.2.11(1).

20. Prove Theorem 7.2.11(2).

21. Prove Theorem 7.2.13.

22. Suppose $\text{[math]}$ is a prime ideal on $\text{[math]}$ . Prove that $\text{[math]}$ is a maximal ideal.

Exercise Notes: For Exercise 6, find a set $\text{[math]}$ and a set $\text{[math]}$ that violate Lemma 7.2.4(1). For Exercise 12(a), let $\text{[math]}$ be a finite set such that for all $\text{[math]}$ , if $\text{[math]}$ is finite then $\text{[math]}$ . Using Lemma 7.2.4(1), deduce that $\text{[math]}$ is a singleton. For Exercise 12(b), use Exercise 11. For Exercise 18, see Exercise 9 on page 68.

7.3 Well-Ordering Theorem

The following theorem is due to Ernst Zermelo and states that every set can be well-ordered. Therefore, the powerful principle of transfinite recursion can be applied to any set.

Well-Ordering Theorem 7.3.1 (AC). Each set has a well-ordering.

Proof. Assume the axiom of choice. Let $\text{[math]}$ be a set. We shall use Zorn’s Lemma to prove that there is a well-ordering on $\text{[math]}$ . Let $\text{[math]}$ be the following set:

(Theorem 2.1.3 implies that $\text{[math]}$ is a set). Define the continuation relation $\text{[math]}$ on $\text{[math]}$ by

: (7.8)

where $\text{[math]}$ and $\text{[math]}$ in (7.8)(ii) are arbitrary. The relationship $\text{[math]}$ is illustrated by the following diagram (7.9) where the order $\text{[math]}$ continues the order $\text{[math]}$ ; that is, the order $\text{[math]}$ can only add new elements that are greater than all of the elements ordered by $\text{[math]}$ (see Exercise 3):

: (7.9)

The structure $\text{[math]}$ is a partially ordered set (see Exercise 4). Let $\text{[math]}$ be a chain. Thus, for all $\text{[math]}$ and $\text{[math]}$ , either $\text{[math]}$ or $\text{[math]}$ . Now let $\text{[math]}$ be the relation $\text{[math]}$ with field $\text{[math]}$ , which is a subset of $\text{[math]}$ .

Claim 1. $\text{[math]}$ is a total order on its field.

Proof. Exercise 18 on page 76 implies that $\text{[math]}$ is a partial order on its field. To show that $\text{[math]}$ is a total order, let $\text{[math]}$ and $\text{[math]}$ be in the field of $\text{[math]}$ . Thus, $\text{[math]}$ and $\text{[math]}$ for some $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ . Since $\text{[math]}$ is a chain, it follows from (7.8) that either $\text{[math]}$ or $\text{[math]}$ . Without loss of generality, let us assume that $\text{[math]}$ . Hence, $\text{[math]}$ and $\text{[math]}$ . As $\text{[math]}$ is a total order, we see that either $\text{[math]}$ or $\text{[math]}$ . Since $\text{[math]}$ , we conclude that either $\text{[math]}$ or $\text{[math]}$ . Therefore, $\text{[math]}$ is a total order. (Claim 1) ☐

Claim 2. $\text{[math]}$ is a well-ordering on its field.

Proof. Suppose that $\text{[math]}$ is nonempty. So let $\text{[math]}$ . Hence, ( $\text{[math]}$ ) $\text{[math]}$ for some $\text{[math]}$ . We now show that $\text{[math]}$ . Since $\text{[math]}$ , we see that $\text{[math]}$ . Assume $\text{[math]}$ . So $\text{[math]}$ . Thus, $\text{[math]}$ for some $\text{[math]}$ . We must verify that $\text{[math]}$ . Since $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ is a chain, we have either $\text{[math]}$ or $\text{[math]}$ .

CASE 1: $\text{[math]}$ . So (7.8)(ii) holds. We know that $\text{[math]}$ . Since $\text{[math]}$ by ( $\text{[math]}$ ), we have that $\text{[math]}$ because $\text{[math]}$ is reflexive. Thus, $\text{[math]}$ and $\text{[math]}$ . From (7.8)(ii), we conclude that $\text{[math]}$ , and so $\text{[math]}$ .

CASE 2: $\text{[math]}$ . Item (i) of (7.8) implies that $\text{[math]}$ . Because $\text{[math]}$ , we infer that $\text{[math]}$ , and therefore, $\text{[math]}$ .

So $\text{[math]}$ . Thus, ( $\text{[math]}$ ) $\text{[math]}$ . Since $\text{[math]}$ , the set $\text{[math]}$ is nonempty. As $\text{[math]}$ is a well-ordering, there is a $\text{[math]}$ -least element $\text{[math]}$ . Because $\text{[math]}$ , ( $\text{[math]}$ ) implies that $\text{[math]}$ is the $\text{[math]}$ -least element in $\text{[math]}$ . So $\text{[math]}$ is a well-ordering on its field. (Claim 2) ☐

Claim 3. $\text{[math]}$ is in $\text{[math]}$ and $\text{[math]}$ is an upper bound for $\text{[math]}$ .

Proof. Claim 2 implies that $\text{[math]}$ is in $\text{[math]}$ . Let $\text{[math]}$ . We prove that $\text{[math]}$ . Clearly, $\text{[math]}$ . Thus, (i) of (7.8) holds. For (ii), suppose that $\text{[math]}$ and $\text{[math]}$ . Since $\text{[math]}$ , there is a $\text{[math]}$ such that $\text{[math]}$ . As $\text{[math]}$ is a chain, we have either $\text{[math]}$ or $\text{[math]}$ . The arguments used in case 1 and case 2 of the proof of Claim 2 show that $\text{[math]}$ . Therefore, $\text{[math]}$ . (Claim 3) ☐

By Zorn’s Lemma, there exists a maximal element $\text{[math]}$ in $\text{[math]}$ . Hence, $\text{[math]}$ is a well-ordering on a set $\text{[math]}$ and $\text{[math]}$ for all $\text{[math]}$ . We now prove that $\text{[math]}$ . Suppose, for a contradiction, that there is an $\text{[math]}$ such that $\text{[math]}$ . Let $\text{[math]}$ . One can easily show (see Exercise 5) that $\text{[math]}$ is a well-ordering on $\text{[math]}$ and therefore, $\text{[math]}$ . In addition, one can also show that $\text{[math]}$ , which contradicts the maximality of $\text{[math]}$ . Hence, $\text{[math]}$ and $\text{[math]}$ is a well-ordering on $\text{[math]}$ . (Theorem)

The proof of Theorem 7.3.1 now shows that the axiom of choice implies that every set can be well-ordered. Moreover, in Exercise 1 you are asked to show that the well-ordering theorem implies the axiom of choice. Another proof of Theorem 7.3.1 is outlined in Exercise 15 on page 194. This alternative proof depends on the replacement axiom.

Exercises 7.3

1. Let $\text{[math]}$ be an indexed function such that $\text{[math]}$ for all $\text{[math]}$ . By Theorem 7.3.1, the set $\text{[math]}$ has a well-ordering $\text{[math]}$ . Define a function $\text{[math]}$ such that $\text{[math]}$ and $\text{[math]}$ . Thus, $\text{[math]}$ is a choice function.

2. Let $\text{[math]}$ be a total order on $\text{[math]}$ . For each $\text{[math]}$ , let $\text{[math]}$ . Suppose that for every $\text{[math]}$ and $\text{[math]}$ , if $\text{[math]}$ is nonempty, then $\text{[math]}$ has a $\text{[math]}$ -least element. Prove that $\text{[math]}$ is a well-ordering on $\text{[math]}$ .

3. Let $\text{[math]}$ be a well-ordering on $\text{[math]}$ and let $\text{[math]}$ be a well-ordering on $\text{[math]}$ . Suppose that (i) $\text{[math]}$ and (ii) whenever $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ .

(a) Prove that $\text{[math]}$ .

(b) Prove that $\text{[math]}$ .

4. Let $\text{[math]}$ be the relation defined on $\text{[math]}$ in the proof of Theorem 7.3.1. Prove that $\text{[math]}$ is a partial ordering on $\text{[math]}$ .