5 On the Size of Sets

5
On the Size of Sets

The size of a finite set can be measured simply by counting; for example, the size of the set $\text{[math]}$ is $\text{[math]}$ because it has $\text{[math]}$ elements, and the size of the sets $\text{[math]}$ and $\text{[math]}$ is $\text{[math]}$ . Clearly, the size of $\text{[math]}$ is bigger than the size of $\text{[math]}$ . Moreover, the sets $\text{[math]}$ and $\text{[math]}$ have the same size. Can the concept of “size” be extended to infinite sets? Is there a way, which does not involve counting, of showing that two sets have the same size? Georg Cantor was the first mathematician to seriously address and answer these questions. Cantor found a way to measure the size of any infinite set. He first observed that two sets $\text{[math]}$ and $\text{[math]}$ have the same size if there is a one-to-one correspondence between $\text{[math]}$ and $\text{[math]}$ , that is, there is a way of evenly matching the elements in $\text{[math]}$ with the elements in $\text{[math]}$ . In other words, Cantor observed that $\text{[math]}$ and $\text{[math]}$ have the same size if there is a bijection $\text{[math]}$ .

The arrow diagram in Figure 5.1 represents a bijection. As a result, we can use this bijection to construct the following one-to-one correspondence (5.1) between the sets $\text{[math]}$ and $\text{[math]}$ :

: (5.1)

Hence, the function $\text{[math]}$ allows us to set up a pairing between the elements in $\text{[math]}$ and the elements in $\text{[math]}$ such that each element in $\text{[math]}$ is matched with exactly one element in $\text{[math]}$ , and each element in $\text{[math]}$ is thereby matched with exactly one element in $\text{[math]}$ . Cantor observed that we can now conclude, without counting, that the sets $\text{[math]}$ and $\text{[math]}$ have the same size.

Figure 5.1. Arrow diagram of a bijection

For another illustration, let $\text{[math]}$ , and let $\text{[math]}$ be defined by $\text{[math]}$ . As $\text{[math]}$ is a bijection, we obtain the following one-to-one correspondence between the set $\text{[math]}$ of natural numbers and the set $\text{[math]}$ of even natural numbers:

Therefore, each natural number $\text{[math]}$ corresponds to the even number $\text{[math]}$ , and each even natural number $\text{[math]}$ is thereby matched with $\text{[math]}$ . The bijection $\text{[math]}$ specifies a one-to-one match-up between the elements in $\text{[math]}$ and the elements in $\text{[math]}$ . Cantor concluded that the sets $\text{[math]}$ and $\text{[math]}$ have the same size.

After discovering how to determine if two infinite sets have the same size, Cantor proved that the set $\text{[math]}$ of rational numbers has the same size as the set $\text{[math]}$ of natural numbers. As a result, Cantor then conjectured that the set of real numbers also has the same size as $\text{[math]}$ . It came as a complete surprise to Georg Cantor when, in 1874, he discovered that these two infinite sets have different sizes. In fact, Cantor showed that the set of real numbers is much larger than the set of natural numbers. This unexpected result would have an enormous impact on the future of mathematics.

When Cantor first presented his new research on the size of infinite sets, some of his contemporaries actually refused to acknowledge his discoveries. Moreover, Henri Poincaré referred to Cantor’s work as a “grave disease” that would infect mathematics. Nevertheless, Cantor and his important ideas would eventually be recognized. In 1904, the Royal Society presented Cantor with its prestigious Sylvester Medal for his “brilliant” mathematical research. David Hilbert, a very influential mathematician, described Cantor’s work as

the finest product of mathematical genius and one of the supreme achievements of purely intellectual human activity.

In this chapter, we shall investigate Cantor’s early work in set theory. First, we will formally define and examine the notion of a finite set, and then we will classify sets into two categories: sets whose elements can be enumerated in a sequence indexed by the natural numbers (countable sets) and those sets for which it is impossible to so enumerate all of their elements (uncountable sets). We will also examine Cantor’s fundamental definitions and theorems on the cardinality (size) of sets.

5.1 Finite Sets

A set is infinite, of course, if it is not finite. Moreover, a set is finite if it has at most $\text{[math]}$ many elements for some natural number $\text{[math]}$ . The next definition is just a mathematical rewording of this notion.

Definition 5.1.1. A set $\text{[math]}$ is finite if and only if there is a one-to-one function $\text{[math]}$ for some natural number $\text{[math]}$ .

It follows, vacuously, that the empty set is finite. Now that we have a formal definition of a finite set, we can now use the Well-Ordering Principle 4.4.13 to precisely define the notion of the “number of elements” in a finite set.

Definition 5.1.2. Suppose that $\text{[math]}$ is a finite set. Let $\text{[math]}$ be the least natural number such that there is a one-to-one function $\text{[math]}$ . Then $\text{[math]}$ is the number of elements in the set $\text{[math]}$ , and we write $\text{[math]}$ .

In particular, we have that $\text{[math]}$ (see Remark 3.3.7 and the paragraph just prior to Definition 3.3.17).

Theorem 5.1.3. Let $\text{[math]}$ be finite and let $\text{[math]}$ . If $\text{[math]}$ is one-to-one, then $\text{[math]}$ is onto $\text{[math]}$ .

Proof. Let $\text{[math]}$ be a finite set. If $\text{[math]}$ , then $\text{[math]}$ and any function $\text{[math]}$ is vacuously onto $\text{[math]}$ . So now assume that $\text{[math]}$ . Let $\text{[math]}$ and let $\text{[math]}$ be one-to-one. Suppose, to the contrary, that $\text{[math]}$ is not onto $\text{[math]}$ . Let $\text{[math]}$ be so that $\text{[math]}$ . Because $\text{[math]}$ , there is an $\text{[math]}$ such that $\text{[math]}$ . Since $\text{[math]}$ , we have either $\text{[math]}$ or $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ and $\text{[math]}$ is one-to-one. As $\text{[math]}$ , we conclude that $\text{[math]}$ , which is a contradiction. If $\text{[math]}$ , then define the function $\text{[math]}$ by

Since $\text{[math]}$ is one-to-one, it follows that $\text{[math]}$ is also one-to-one. Moreover, because $\text{[math]}$ , we conclude that $\text{[math]}$ , which is again a contradiction. ☐

Corollary 5.1.4. If $\text{[math]}$ is finite and $\text{[math]}$ , then there is a bijection $\text{[math]}$ .

Proof. Suppose that $\text{[math]}$ is finite and let $\text{[math]}$ . By Definition 5.1.2 there exists a one-to-one function $\text{[math]}$ . Theorem 5.1.3 implies that $\text{[math]}$ is a bijection. ☐

Theorem 5.1.5. Let $\text{[math]}$ be one-to-one where $\text{[math]}$ is a finite set. Then $\text{[math]}$ is onto $\text{[math]}$ .

Proof. Let $\text{[math]}$ be one-to-one where $\text{[math]}$ is finite. Let $\text{[math]}$ be such that $\text{[math]}$ . By Definition 5.1.2, let $\text{[math]}$ be one-to-one. Theorems 3.3.19 and 5.1.3 imply that $\text{[math]}$ is a bijection. To prove that $\text{[math]}$ is onto $\text{[math]}$ , let $\text{[math]}$ . Since $\text{[math]}$ , there exists an $\text{[math]}$ such that $\text{[math]}$ . So $\text{[math]}$ , and thus, $\text{[math]}$ as $\text{[math]}$ is one-to-one. Hence, $\text{[math]}$ is onto $\text{[math]}$ . ☐

Corollary 5.1.6. Let $\text{[math]}$ be one-to-one and not onto $\text{[math]}$ . Then $\text{[math]}$ is infinite.

The following theorem confirms that two finite sets have the same number of elements if and only if there exists a one-to-one correspondence between the two sets.

Theorem 5.1.7. Let $\text{[math]}$ and $\text{[math]}$ be finite sets. Then there is a bijection $\text{[math]}$ if and only if $\text{[math]}$ .

Proof. See Exercise 4. ☐

Recall that $\text{[math]}$ . Since the identity function from $\text{[math]}$ to $\text{[math]}$ is one-to-one, we see from Definition 5.1.2 that $\text{[math]}$ .

Theorem 5.1.8. For all natural numbers $\text{[math]}$ , we have that $\text{[math]}$ .

Corollary 5.1.9 (Pigeonhole Principle). Let $\text{[math]}$ and $\text{[math]}$ be natural numbers and let $\text{[math]}$ be a function. If $\text{[math]}$ , then $\text{[math]}$ is not one-to-one.

Theorem 5.1.10. The set $\text{[math]}$ is an infinite set.

Proof. Suppose $\text{[math]}$ is finite. Thus, there is a one-to-one function $\text{[math]}$ for some $\text{[math]}$ . Since $\text{[math]}$ is one-to-one, the restriction $\text{[math]}$ is also one-to-one, and this contradicts Corollary 5.1.9. ☐

Corollary 5.1.11. If $\text{[math]}$ is one-to-one, then $\text{[math]}$ is an infinite set.

Proof. See Exercise 21. ☐

The pigeonhole principle implies a “dual” version involving surjections.

Lemma 5.1.12. If $\text{[math]}$ and $\text{[math]}$ where $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ is not onto $\text{[math]}$ .

Proof. Let $\text{[math]}$ where $\text{[math]}$ and $\text{[math]}$ are natural numbers. Suppose, to the contrary, that $\text{[math]}$ is onto $\text{[math]}$ . We can therefore define the function $\text{[math]}$ by

: (5.2)

We now show that $\text{[math]}$ is one-to-one. Let $\text{[math]}$ and $\text{[math]}$ be such that $\text{[math]}$ . Hence, $\text{[math]}$ . By the definition (5.2) of $\text{[math]}$ , we have that $\text{[math]}$ . So $\text{[math]}$ is one-to-one, which contradicts Corollary 5.1.9, because $\text{[math]}$ . ☐

Theorem 5.1.13. If $\text{[math]}$ is finite and $\text{[math]}$ is onto $\text{[math]}$ , then $\text{[math]}$ is one-to-one.

Proof. Let $\text{[math]}$ be finite and $\text{[math]}$ be onto $\text{[math]}$ . Also, let $\text{[math]}$ be such that $\text{[math]}$ . Assume $\text{[math]}$ where $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ . So $\text{[math]}$ and $\text{[math]}$ for some $\text{[math]}$ . Let $\text{[math]}$ . Thus, $\text{[math]}$ (see Exercise 13) and $\text{[math]}$ is onto $\text{[math]}$ . Since $\text{[math]}$ and $\text{[math]}$ , there is a function $\text{[math]}$ that is onto $\text{[math]}$ (see Exercise 14), contradicting Lemma 5.1.12, as $\text{[math]}$ . Therefore, $\text{[math]}$ is one-to-one. ☐

Theorem 5.1.14. If $\text{[math]}$ is a finite set, then $\text{[math]}$ is finite.

Proof. We will use proof by induction. Let

If $\text{[math]}$ , then $\text{[math]}$ and $\text{[math]}$ is finite. Hence, $\text{[math]}$ . Let $\text{[math]}$ . To prove that $\text{[math]}$ , let $\text{[math]}$ be such that $\text{[math]}$ . So $\text{[math]}$ is nonempty. Let $\text{[math]}$ . Thus, $\text{[math]}$ (see Exercise 13). As $\text{[math]}$ , we conclude that $\text{[math]}$ is finite. By Corollary 5.1.4, there exists a bijection $\text{[math]}$ where $\text{[math]}$ . Define $\text{[math]}$ by

: (5.3)

To prove that $\text{[math]}$ is one-to-one, suppose that $\text{[math]}$ with $\text{[math]}$ and $\text{[math]}$ . Thus, $\text{[math]}$ for some $\text{[math]}$ . There are two cases to consider: $\text{[math]}$ and $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ and $\text{[math]}$ , by (5.3). Because $\text{[math]}$ , we conclude that $\text{[math]}$ . So $\text{[math]}$ since $\text{[math]}$ is one-to-one. If $\text{[math]}$ , then (5.3) implies that $\text{[math]}$ and $\text{[math]}$ . As $\text{[math]}$ , (5.3) asserts that $\text{[math]}$ . So $\text{[math]}$ . Hence, $\text{[math]}$ because $\text{[math]}$ is one-to-one. It therefore follows that $\text{[math]}$ . Since $\text{[math]}$ is one-to-one and $\text{[math]}$ , we have that $\text{[math]}$ is finite. Thus, $\text{[math]}$ and the proof is complete. ☐

Exercises 5.1

1. In our proof of Theorem 5.1.3, under the case that $\text{[math]}$ , we did not show that the function $\text{[math]}$ is one-to-one. Complete the proof by proving that $\text{[math]}$ is one-to-one.

2. Suppose that the set $\text{[math]}$ is finite and $\text{[math]}$ . Prove that $\text{[math]}$ is finite.

3. Let $\text{[math]}$ and $\text{[math]}$ be two finite sets, and let $\text{[math]}$ be one-to-one. Prove that $\text{[math]}$ .

4. Using Exercise 3 and Corollary 5.1.4, prove Theorem 5.1.7.

5. Let $\text{[math]}$ and let $\text{[math]}$ . Prove that $\text{[math]}$ is finite.

6. Let $\text{[math]}$ be finite and let $\text{[math]}$ . Prove that $\text{[math]}$ , for some $\text{[math]}$ .

7. Suppose that $\text{[math]}$ is a bijection, where $\text{[math]}$ . Prove that $\text{[math]}$ .

8. Let $\text{[math]}$ be defined by $\text{[math]}$ . Prove that $\text{[math]}$ is one-to-one. Prove that if $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ .

9. Prove that $\text{[math]}$ defined by $\text{[math]}$ is one-to-one and is onto $\text{[math]}$ . Prove that if $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ .

10. Prove there exists a one-to-one function $\text{[math]}$ that is onto $\text{[math]}$ .

11. Suppose that $\text{[math]}$ and $\text{[math]}$ are disjoint finite sets. Prove that $\text{[math]}$ is finite.

12. Let $\text{[math]}$ be an infinite set and $\text{[math]}$ be a finite set. Prove that $\text{[math]}$ is infinite.

13. Let $\text{[math]}$ . Suppose that $\text{[math]}$ and $\text{[math]}$ . Prove that $\text{[math]}$ .

14. Suppose that $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ is onto $\text{[math]}$ where $\text{[math]}$ and $\text{[math]}$ . Show that there is a function $\text{[math]}$ that is onto $\text{[math]}$ .

15. Suppose that $\text{[math]}$ and $\text{[math]}$ are finite sets. Prove that $\text{[math]}$ is finite.

16. Let $\text{[math]}$ . Suppose that $\text{[math]}$ is onto $\text{[math]}$ . Prove that $\text{[math]}$ is finite.

17. Let $\text{[math]}$ be a finite set. Prove that there exists an $\text{[math]}$ that is onto $\text{[math]}$ for some $\text{[math]}$ .

18. Suppose that $\text{[math]}$ is onto $\text{[math]}$ where $\text{[math]}$ is finite. Prove that $\text{[math]}$ is finite.

19. Let $\text{[math]}$ and $\text{[math]}$ be such that $\text{[math]}$ is finite for all $\text{[math]}$ . Prove, by induction, that $\text{[math]}$ is finite. [Use Exercise 15 in the inductive step.]

20. Suppose that $\text{[math]}$ and $\text{[math]}$ are finite sets. Prove that $\text{[math]}$ is finite.

21. Prove Corollary 5.1.11.

22. Let $\text{[math]}$ be an indexed function where $\text{[math]}$ is a finite set and $\text{[math]}$ for all $\text{[math]}$ . Without using the axiom of choice, prove by induction on $\text{[math]}$ that there is an indexed function $\text{[math]}$ such that $\text{[math]}$ for all $\text{[math]}$ .

23. Using Exercise 7, modify the proof of Theorem 5.1.14 to show that if $\text{[math]}$ , then $\text{[math]}$ .

Exercise Notes: For Exercise 6, apply Exercise 18 on page 109. For Exercise 7, use Theorems 5.1.7 and 5.1.8. For Exercise 9, if $\text{[math]}$ , then $\text{[math]}$ (see Theorems 4.1.6 and 4.1.10). To prove $\text{[math]}$ is onto $\text{[math]}$ , apply Theorem 4.4.13 to prove that for all $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ for some $\text{[math]}$ and $\text{[math]}$ . Note: if $\text{[math]}$ , then $\text{[math]}$ . For Exercise 10, use Exercise 9. For Exercise 12, apply Exercise 11. For Exercise 16, let $\text{[math]}$ for $\text{[math]}$ . Since $\text{[math]}$ is onto $\text{[math]}$ , each the set $\text{[math]}$ is nonempty and has a least element. For Exercise 17, use Corollary 5.1.4. For Exercise 18, apply Exercises 16–17. For Exercise 20, apply Exercise 9. For Exercise 21, recall Theorem 3.3.19. For Exercise 22, the result is true vacuously if $\text{[math]}$ . For Exercise 23, note that if $\text{[math]}$ , then Exercise 12 on page 108 and Theorem 4.4.11(1) imply that $\text{[math]}$ for a $\text{[math]}$ .

5.2 Countable Sets

Recall that $\text{[math]}$ is the set of natural numbers. A set is countable if it has the same size as some subset of $\text{[math]}$ . In other words, a set is countable if there is a one-to-one correspondence between the set and a subset of $\text{[math]}$ . Our next definition captures this concept in mathematical terms.

Definition 5.2.1. A set $\text{[math]}$ is countable if and only if there exists a one-to-one function $\text{[math]}$ .

So by Definition 5.1.1, every finite set is countable (as $\text{[math]}$ , for all $\text{[math]}$ ). Every subset $\text{[math]}$ of $\text{[math]}$ is also countable, since the identity function $\text{[math]}$ is one-to-one, where $\text{[math]}$ for all $\text{[math]}$ . Thus, in particular, the set of natural numbers $\text{[math]}$ is countable. One can also show that the set of integers and the set of rational numbers are countable (see Exercises 4 and 5). We will prove in Section 5.3 that the set of real numbers is not countable.

Definition 5.2.2. A set $\text{[math]}$ is countably infinite if it is countable and infinite.

For example, the set $\text{[math]}$ is countably infinite as it is countable and infinite by Theorem 5.1.10. When one can prove that a set is countable and it is clear that it is infinite, then we can conclude that the set is countably infinite.

Theorem 5.2.3. Suppose that $\text{[math]}$ and $\text{[math]}$ are sets where $\text{[math]}$ is countable. If there is an injection $\text{[math]}$ , then $\text{[math]}$ is countable.

Proof. Let $\text{[math]}$ and $\text{[math]}$ be sets where $\text{[math]}$ is countable. Let $\text{[math]}$ be one-to-one. We shall prove that $\text{[math]}$ is countable. Since $\text{[math]}$ is countable, there is a one-to-one function $\text{[math]}$ . Thus, by Theorem 3.3.19, $\text{[math]}$ is an injection. We conclude that $\text{[math]}$ is countable. ☐

Theorem 5.2.4. If $\text{[math]}$ is a countable set and $\text{[math]}$ , then $\text{[math]}$ is countable.

Proof. Assume that $\text{[math]}$ is a countable set and $\text{[math]}$ . Let $\text{[math]}$ be the identity function, that is, $\text{[math]}$ for all $\text{[math]}$ . Since $\text{[math]}$ is one-to-one, Theorem 5.2.3 implies that $\text{[math]}$ is countable. ☐

Theorem 5.2.5. If $\text{[math]}$ and $\text{[math]}$ are countable sets, then $\text{[math]}$ is countable.

Proof. Let $\text{[math]}$ and $\text{[math]}$ be countable. So there are one-to-one functions $\text{[math]}$ and $\text{[math]}$ . Now define the function $\text{[math]}$ by

: (5.4)

for each $\text{[math]}$ . We prove that $\text{[math]}$ is one-to-one. Let $\text{[math]}$ and $\text{[math]}$ be in $\text{[math]}$ and assume $\text{[math]}$ . We shall prove that $\text{[math]}$ . First, because $\text{[math]}$ , we cannot have $\text{[math]}$ and $\text{[math]}$ . To see this, suppose that $\text{[math]}$ and $\text{[math]}$ . So, as $\text{[math]}$ , we infer that $\text{[math]}$ from (5.4); but this is impossible because a natural number cannot be both even and odd. Similarly, we cannot have $\text{[math]}$ and $\text{[math]}$ . Hence, either $\text{[math]}$ and $\text{[math]}$ are both in $\text{[math]}$ , or they are both in $\text{[math]}$ . If $\text{[math]}$ and $\text{[math]}$ are in $\text{[math]}$ , then $\text{[math]}$ . Thus, $\text{[math]}$ and so $\text{[math]}$ , because $\text{[math]}$ is one-to-one. If $\text{[math]}$ and $\text{[math]}$ are in $\text{[math]}$ , then $\text{[math]}$ . We conclude that $\text{[math]}$ . Since $\text{[math]}$ is one-to-one, we have $\text{[math]}$ . Therefore, $\text{[math]}$ is one-to-one and $\text{[math]}$ is countable. ☐

One can prove by mathematical induction, using Theorem 5.2.5, that a finite union of countable sets is also countable. We will not do this here, because we will soon prove a more general result (see Corollary 5.2.10).

Our next result demonstrates that every countably infinite set can be put into a one-to-one correspondence with the set of natural numbers.

Theorem 5.2.6. If $\text{[math]}$ is countably infinite, then there is a bijection $\text{[math]}$ .

Proof. Let $\text{[math]}$ be a countably infinite set. Thus, there exists a one-to-one function $\text{[math]}$ . Since $\text{[math]}$ is not finite, the range of $\text{[math]}$ must be an infinite subset of $\text{[math]}$ . Let $\text{[math]}$ . So $\text{[math]}$ is a bijection. Hence, $\text{[math]}$ is also a bijection, via Theorem 3.3.18. Because $\text{[math]}$ is an infinite set of natural numbers, there is a bijection $\text{[math]}$ by Exercise 13. Let $\text{[math]}$ . Theorems 3.3.19 and 3.3.20 now imply that $\text{[math]}$ is a bijection. ☐

Corollary 5.2.7. A set $\text{[math]}$ is countably infinite if and only if there is a bijection $\text{[math]}$ .

Proof. If $\text{[math]}$ is countably infinite, then Theorem 5.2.6 implies that there exists a bijection $\text{[math]}$ . Conversely, suppose that $\text{[math]}$ is a bijection. Since $\text{[math]}$ is one-to-one, $\text{[math]}$ is infinite by Corollary 5.1.11. As $\text{[math]}$ is onto $\text{[math]}$ , Theorem 3.3.18 asserts the existence of the inverse function $\text{[math]}$ that is one-to-one. Hence, $\text{[math]}$ is countable and infinite. ☐

Theorem 5.2.8. If $\text{[math]}$ is a countably infinite set, then there exists an enumeration $\text{[math]}$ of all the elements in $\text{[math]}$ such that each element in $\text{[math]}$ appears in this enumeration exactly once.

Proof. Assume that $\text{[math]}$ is countably infinite. Thus, by Theorem 5.2.6, there is a bijection $\text{[math]}$ . For each $\text{[math]}$ , let $\text{[math]}$ . Since $\text{[math]}$ is one-to-one and onto $\text{[math]}$ , it follows that the enumeration $\text{[math]}$ lists every element in $\text{[math]}$ exactly once. ☐

Theorem 5.2.8 implies that each countably infinite set is also denumerable; that is, we can list the elements of a denumerable set in the same way that we list the natural numbers, namely, $\text{[math]}$ . We will soon show that it is impossible to list all of the real numbers in such a manner. In other words, $\text{[math]}$ is not denumerable.

Theorem 5.2.9 (AC). If $\text{[math]}$ is such that $\text{[math]}$ is countable for each $\text{[math]}$ , then $\text{[math]}$ is countable.

Proof. Suppose that $\text{[math]}$ is a set of countable sets. Because each $\text{[math]}$ is countable, the axiom of choice implies that for every $\text{[math]}$ there is a one-to-one function $\text{[math]}$ . In other words, by the axiom of choice, there is a choice function $\text{[math]}$ for the indexed function $\text{[math]}$ where each $\text{[math]}$ is the set of all the one-to-one functions of the form $\text{[math]}$ .

Now let $\text{[math]}$ be a one-to-one function (see Exercise 9, page 116). Define the function $\text{[math]}$ by

for all $\text{[math]}$ . To prove that $\text{[math]}$ is one-to-one, assume that $\text{[math]}$ where $\text{[math]}$ and $\text{[math]}$ are in $\text{[math]}$ . Let $\text{[math]}$ be the least natural number such that $\text{[math]}$ , and also let $\text{[math]}$ be the least such that $\text{[math]}$ . Since $\text{[math]}$ , we have $\text{[math]}$ . Because $\text{[math]}$ is one-to-one, it follows that $\text{[math]}$ and $\text{[math]}$ . Thus, $\text{[math]}$ and so $\text{[math]}$ , as $\text{[math]}$ is one-to-one. Therefore, $\text{[math]}$ is one-to-one and $\text{[math]}$ is countable. ☐

We can now prove that a countable union of countable sets is also countable. Therefore, countable sets can be used to construct many more countable sets.

Corollary 5.2.10 (AC). Let $\text{[math]}$ be countable and suppose that each $\text{[math]}$ is also countable. Then $\text{[math]}$ is countable.

Proof. Let $\text{[math]}$ be as in the statement of the corollary. Thus, there is a one-to-one function $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ is countable. So assume $\text{[math]}$ and let $\text{[math]}$ be fixed. Consider the indexed set $\text{[math]}$ defined by

for each $\text{[math]}$ . Therefore, $\text{[math]}$ is countable for every $\text{[math]}$ , and $\text{[math]}$ . Theorem 5.2.9 now implies that $\text{[math]}$ is countable. ☐

Since a finite set is countable, Corollary 5.2.10 implies that a finite union of countable sets is also countable.

Corollary 5.2.11 (AC). If the indexed set $\text{[math]}$ is such that $\text{[math]}$ is countable and $\text{[math]}$ is countable for each $\text{[math]}$ , then $\text{[math]}$ is countable.

Let $\text{[math]}$ be a set and let $\text{[math]}$ be a natural number. Recalling Definition 3.3.6, we have that $\text{[math]}$ . The set $\text{[math]}$ can be viewed as the set of all sequences of elements in $\text{[math]}$ of length $\text{[math]}$ .

Theorem 5.2.12. Let $\text{[math]}$ be a countable set. Then $\text{[math]}$ is countable, for all $\text{[math]}$ .

Proof. Let $\text{[math]}$ be countable. Thus, there is a one-to-one function $\text{[math]}$ . Let $\text{[math]}$ . We shall prove that $\text{[math]}$ is inductive. Since $\text{[math]}$ (see Remark 3.3.7), the set $\text{[math]}$ is countable. Thus, $\text{[math]}$ . Let $\text{[math]}$ . Therefore, $\text{[math]}$ is countable. So let $\text{[math]}$ be one-to-one. By Exercise 9 on page 116, there is a one-to-one function $\text{[math]}$ . Define $\text{[math]}$ by

for all $\text{[math]}$ . We will now prove that $\text{[math]}$ is one-to-one, and thus conclude that $\text{[math]}$ is countable. Let $\text{[math]}$ and $\text{[math]}$ . Assume that $\text{[math]}$ . Therefore,

Because $\text{[math]}$ is one-to-one, we conclude that

Since $\text{[math]}$ and $\text{[math]}$ are one-to-one, we infer that $\text{[math]}$ and $\text{[math]}$ . Thus, by Lemma 3.3.5, $\text{[math]}$ . So $\text{[math]}$ is one-to-one. Therefore, $\text{[math]}$ . ☐

By applying Theorem 2.1.3, one can show that the following class is a set:

So for every function $\text{[math]}$ , where $\text{[math]}$ , we have that $\text{[math]}$ . Clearly,

: (5.5)

Theorem 5.2.13 (AC). Let $\text{[math]}$ be a countable set. Then $\text{[math]}$ is countable.

Proof. If $\text{[math]}$ is countable, Theorem 5.2.12 asserts that $\text{[math]}$ is countable, for every $\text{[math]}$ . Equation (5.5) and Theorem 5.2.9 thus imply that $\text{[math]}$ is countable. ☐

Corollary 5.2.14 (AC). If $\text{[math]}$ is countable, then the set of all finite subsets of $\text{[math]}$ is also countable.

Proof. Let $\text{[math]}$ be set of all finite subsets of $\text{[math]}$ . Define the function $\text{[math]}$ by $\text{[math]}$ . Exercise 17 on page 116 implies that $\text{[math]}$ is onto $\text{[math]}$ . Hence, $\text{[math]}$ is countable by Theorem 5.2.13 and Exercise 10. ☐

Remark 5.2.15. With a little more work, one can prove Theorem 5.2.13 (and Corollary 5.2.14) without appealing to the axiom of choice. We outline two such proofs below. The first proof is inspired by the proof of Theorem 5.2.12, and the second proof applies the fundamental theorem of arithmetic (see [1, Theorem 4.7.7]).

1. Suppose that $\text{[math]}$ and $\text{[math]}$ are one-to-one functions. By the Recursion Theorem 4.2.1, one obtains the indexed function $\text{[math]}$ , where $\text{[math]}$ for all $\text{[math]}$ , such that

(1) $\text{[math]}$ (recall that $\text{[math]}$ );

(2) $\text{[math]}$ for all $\text{[math]}$ .

One can prove that each $\text{[math]}$ is one-to-one by induction. Clearly, $\text{[math]}$ is one-to-one. In the inductive step, one applies the argument used in the proof of Theorem 5.2.12. One now “glues the functions $\text{[math]}$ together” by defining $\text{[math]}$ by

One can now prove that $\text{[math]}$ is one-to-one and thus, $\text{[math]}$ is countable.

2. Let $\text{[math]}$ be one-to-one. One must first prove that $\text{[math]}$ is countable. To do this, define $\text{[math]}$ by

where $\text{[math]}$ is the $\text{[math]}$ -th prime. By the fundamental theorem of arithmetic, the function $\text{[math]}$ is one-to-one. Hence, $\text{[math]}$ is countable. Since $\text{[math]}$ , define $\text{[math]}$ by $\text{[math]}$ . Therefore, if $\text{[math]}$ , then $\text{[math]}$ (see Theorem 3.3.10). As $\text{[math]}$ is one-to-one, it follows that $\text{[math]}$ is one-to-one. Therefore, because $\text{[math]}$ is countable, Theorem 5.2.3 implies that $\text{[math]}$ is countable.

Exercises 5.2

1. Let $\text{[math]}$ and let $\text{[math]}$ . Define a bijection $\text{[math]}$ , and define a bijection $\text{[math]}$ .

2. Let $\text{[math]}$ and $\text{[math]}$ be as in Exercise 1. Define an injection $\text{[math]}$ .

3. Show that the set of negative integers $\text{[math]}$ is countable.

4. Conclude from Exercise 3 that set of integers $\text{[math]}$ is countable.

5. Let $\text{[math]}$ be one-to-one (see Exercise 9 on page 116). Using $\text{[math]}$ , show that the set of positive rational numbers $\text{[math]}$ is countable. Conclude that the set of negative rational numbers $\text{[math]}$ is countable and the set $\text{[math]}$ is countable.

6. Let $\text{[math]}$ and $\text{[math]}$ be two countably infinite sets. Prove that there exists a bijection $\text{[math]}$ .

7. Let $\text{[math]}$ and $\text{[math]}$ be countable sets. Prove that $\text{[math]}$ is countable.

8. Let $\text{[math]}$ be a set. Suppose that $\text{[math]}$ is onto $\text{[math]}$ . Prove that $\text{[math]}$ is countable.

9. Let $\text{[math]}$ be a nonempty countable set. Prove that there exists an $\text{[math]}$ that is onto $\text{[math]}$ .

10. Suppose that $\text{[math]}$ is onto $\text{[math]}$ where $\text{[math]}$ is countable. Prove that $\text{[math]}$ is also countable.

11. (AC) Let $\text{[math]}$ be an infinite set and let $\text{[math]}$ . By Theorem 3.3.24, there exists a function $\text{[math]}$ such that $\text{[math]}$ for all $\text{[math]}$ . One can show (see Theorem 6.2.3) that there is a function $\text{[math]}$ such that

Prove that $\text{[math]}$ is one-to-one.

12. Let $\text{[math]}$ be a finite set. Prove that $\text{[math]}$ is finite, for all $\text{[math]}$ .

13. Let $\text{[math]}$ be infinite and $\text{[math]}$ be the least element in $\text{[math]}$ . Define $\text{[math]}$ by

By the recursion theorem, there is a function $\text{[math]}$ such that

(1) $\text{[math]}$ ,

(2) $\text{[math]}$ , for all $\text{[math]}$ .

Show that $\text{[math]}$ for each $\text{[math]}$ . Conclude, from Exercise 14 on page 108, that $\text{[math]}$ is an increasing, one-to-one function. Prove that for each $\text{[math]}$ there is an $\text{[math]}$ so that $\text{[math]}$ . Prove that $\text{[math]}$ and that $\text{[math]}$ is a bijection.

14. Let $\text{[math]}$ be the set of polynomials in $\text{[math]}$ with integer coefficients, that is,

Define a surjection $\text{[math]}$ . Now show that $\text{[math]}$ is countable.

15. A real number $\text{[math]}$ is said to be algebraic if $\text{[math]}$ for some $\text{[math]}$ (see Exercise 14). For $\text{[math]}$ , let $\text{[math]}$ . Since a polynomial in $\text{[math]}$ has only finitely many roots, each set $\text{[math]}$ is finite. Let $\text{[math]}$ be the set of all algebraic numbers, that is, $\text{[math]}$ . Prove that $\text{[math]}$ is countable.

Exercise Notes: For Exercise 5, first assume each $\text{[math]}$ is in reduced form. For Exercise 6, first review the three Theorems 3.3.18–3.3.20. For Exercise 8, let $\text{[math]}$ for each $\text{[math]}$ . Because $\text{[math]}$ is onto $\text{[math]}$ , each $\text{[math]}$ is nonempty and has a least element. For Exercise 10, use Exercises 8–9. For Exercise 12, modify the proof of Theorem 5.2.12. For Exercise 13, show that for every $\text{[math]}$ and $\text{[math]}$ , if $\text{[math]}$ , then $\text{[math]}$ . Now use induction. To prove that $\text{[math]}$ , one can apply Theorem 4.4.13. For Exercise 14, apply Theorem 5.2.13 with Exercises 4 and 10. For Exercise 15, use Exercise 14 and Corollary 5.2.11.

5.3 Uncountable Sets

In Section 5.2, we established the existence of many countable sets. One might begin to believe that all sets are countable. Are there sets that are not countable? We will soon prove that such sets exist. First, we identify a slightly easier way to say that a set is “not countable.”

Definition 5.3.1. A set $\text{[math]}$ is uncountable if it is not countable, that is, if there is no one-to-one function $\text{[math]}$ .

Cantor was the first mathematician to prove that an uncountable set exists. In his proof, Cantor introduced a new and powerful proof technique that is often identified as a Cantor’s diagonal argument. This argument has had a profound influence on mathematics ever since its introduction. In particular, diagonal arguments now frequently appear in mathematical logic and in computability theory. The proof of our next theorem illustrates Cantor’s diagonal argument.

Theorem 5.3.2. Let $\text{[math]}$ be the set of all the functions $\text{[math]}$ . Then $\text{[math]}$ is uncountable.

Proof. Let $\text{[math]}$ be as stated in the theorem. We will prove that $\text{[math]}$ is uncountable. Suppose, for a contradiction, that the set $\text{[math]}$ is countable. Because $\text{[math]}$ is infinite (see Exercise 8), Theorem 5.2.8 implies that there is an enumeration

: (5.6)

of all the functions in $\text{[math]}$ ; that is, every function in $\text{[math]}$ appears in the list (5.6). Define the function $\text{[math]}$ by

: (5.7)

for each $\text{[math]}$ . As $\text{[math]}$ , we see that $\text{[math]}$ . Since every function in $\text{[math]}$ is in the list (5.6), we conclude that the function $\text{[math]}$ appears in this list. Hence, there is an $\text{[math]}$ such that $\text{[math]}$ . Therefore, $\text{[math]}$ for all $\text{[math]}$ . So, in particular, ( $\text{[math]}$ ) $\text{[math]}$ . Since $\text{[math]}$ , either $\text{[math]}$ or $\text{[math]}$ . If $\text{[math]}$ , then $\text{[math]}$ by (5.7). Thus, ( $\text{[math]}$ ) implies that $\text{[math]}$ , a contradiction. If $\text{[math]}$ , then $\text{[math]}$ by (5.7). Again, ( $\text{[math]}$ ) implies that $\text{[math]}$ , which is a contradiction. Therefore, $\text{[math]}$ is uncountable. ☐

Where is the diagonal?

Are you wondering why the technique used in the proof of Theorem 5.3.2 is referred to as a diagonal argument? To answer this inquiry, we shall now revisit this proof. Given a function $\text{[math]}$ , there is a way of writing the values of $\text{[math]}$ as an infinite sequence of terms from the set $\text{[math]}$ . For example, suppose $\text{[math]}$ if $\text{[math]}$ is even and $\text{[math]}$ if $\text{[math]}$ is odd. So

and we can represent $\text{[math]}$ as follows: $\text{[math]}$ . Furthermore, if $\text{[math]}$ is represented by

then $\text{[math]}$ . Consider the list (5.6) of all the functions in $\text{[math]}$ . Let us represent each $\text{[math]}$ in this list as an infinite sequence; that is, let

Using this notation, we can rewrite the list of functions (5.6) in the following vertical form:

In the proof of Theorem 5.3.2, a function $\text{[math]}$ was defined so that $\text{[math]}$ is not equal to any function in the list (5.8). This is done by going down this list and assigning a value to $\text{[math]}$ that is different from the diagonal value $\text{[math]}$ for each $\text{[math]}$ appearing in (5.8). To illustrate this idea, let us give some specific values to the entries that can appear in the diagonal of (5.8). Suppose $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ . Thus, (5.8) becomes

We have put the function $\text{[math]}$ below the infinite list (5.9) where the values of $\text{[math]}$ are determined by applying definition (5.7), in the proof of Theorem 5.3.2. For example, to evaluate $\text{[math]}$ we see that $\text{[math]}$ , and so $\text{[math]}$ by (5.7). Thus, $\text{[math]}$ , and we are thereby assured that $\text{[math]}$ . Now we evaluate $\text{[math]}$ . Since $\text{[math]}$ , we obtain the value $\text{[math]}$ . Hence, $\text{[math]}$ and $\text{[math]}$ . Again, because $\text{[math]}$ , we conclude that $\text{[math]}$ and $\text{[math]}$ . Continuing in this manner we construct a function $\text{[math]}$ that is different from every function in the list (5.9). This is the clever diagonal argument that Cantor introduced to mathematics.

Theorem 5.3.3. Let $\text{[math]}$ and $\text{[math]}$ be sets. If $\text{[math]}$ is uncountable and $\text{[math]}$ is a one-to-one function, then $\text{[math]}$ is uncountable.

Proof. Let $\text{[math]}$ be an uncountable set, and let $\text{[math]}$ be a one-to-one function. Suppose, for a contradiction, that $\text{[math]}$ is countable. Since $\text{[math]}$ is one-to-one, Theorem 5.2.3 thus implies that $\text{[math]}$ is a countable set, contradicting the fact that $\text{[math]}$ is uncountable. Therefore, $\text{[math]}$ is uncountable. ☐

Before proving our next lemma, we make a simple observation. Whenever $\text{[math]}$ , we have that $\text{[math]}$ for all $\text{[math]}$ . We can thus use $\text{[math]}$ to define a real number by means of an infinite decimal expansion. Let $\text{[math]}$ for each $\text{[math]}$ . Then we have the real number given by $\text{[math]}$ . For example, suppose that $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , then

Decimal expansions that possess only the digits 0 and/or 1 are, in fact, unique; that is, if a real number has a decimal expansion consisting of 0’s and/or 1’s, then it has only one such expansion.

Lemma 5.3.4. There is a one-to-one function $\text{[math]}$ .

Proof. Let $\text{[math]}$ . For each $\text{[math]}$ let us define $\text{[math]}$ $\text{[math]}$ , for all $\text{[math]}$ . So $\text{[math]}$ for every $\text{[math]}$ . Define the function $\text{[math]}$ by

: (5.10)

for each $\text{[math]}$ . Let $\text{[math]}$ and $\text{[math]}$ be functions in $\text{[math]}$ . Assume $\text{[math]}$ . We shall prove that $\text{[math]}$ . Because $\text{[math]}$ , we conclude from (5.10) that

Since such decimal expansions are unique, we have that $\text{[math]}$ for all $\text{[math]}$ . Hence, $\text{[math]}$ for all $\text{[math]}$ , by $\text{[math]}$ . Thus, $\text{[math]}$ and $\text{[math]}$ is one-to-one. ☐

We can now present and prove Cantor’s classic theorem.

Theorem 5.3.5 (Cantor). The set of real numbers $\text{[math]}$ is uncountable.

Proof. By Lemma 5.3.4, let $\text{[math]}$ be one-to-one. By Theorem 5.3.2, $\text{[math]}$ is uncountable. So Theorem 5.3.3 implies that $\text{[math]}$ is uncountable. ☐

Exercises 5.3

1. Let $\text{[math]}$ be uncountable. Prove that $\text{[math]}$ is uncountable for any nonempty set $\text{[math]}$ .

2. Let $\text{[math]}$ be uncountable and $\text{[math]}$ be countable. Prove that $\text{[math]}$ is uncountable.

3. Prove that the set of irrational numbers $\text{[math]}$ is uncountable.

4. Suppose that $\text{[math]}$ is uncountable and $\text{[math]}$ . Prove that $\text{[math]}$ is uncountable.

5. Prove that $\text{[math]}$ is uncountable.

6. Suppose that $\text{[math]}$ is uncountable. Prove that $\text{[math]}$ is uncountable.

7. Let $\text{[math]}$ . Prove that if $\text{[math]}$ is uncountable, then $\text{[math]}$ is uncountable.

8. Let $\text{[math]}$ be as in Theorem 5.3.2, and let ( $\text{[math]}$ ) $\text{[math]}$ be a finite list of functions in $\text{[math]}$ . Using the argument in the proof of Theorem 5.3.2, define a new function $\text{[math]}$ that is not in the list ( $\text{[math]}$ ). Conclude that $\text{[math]}$ is infinite.

9. Suppose that someone claims that the set of real numbers in the interval $\text{[math]}$ is countable and that all of these real numbers can be enumerated as in (5.11), where each such real number is represented by an infinite decimal expansion:

You must show that this claim is false. Using Cantor’s diagonal argument, define a decimal expansion for a real number $\text{[math]}$ in $\text{[math]}$ that does not appear in the list (5.11). In order to ensure uniqueness, your expansion $\text{[math]}$ should not contain the digits 0 or 9. Identify the first four digits in the decimal expansion of $\text{[math]}$ . Prove that $\text{[math]}$ for all $\text{[math]}$ .

10. Let $\text{[math]}$ . Theorem 5.2.4 and Exercise 5 on page 123 imply that $\text{[math]}$ is countable. We can thus enumerate all of the elements in $\text{[math]}$ in a list ( $\text{[math]}$ ) $\text{[math]}$ , by Theorem 5.2.8. Since each of these rational numbers has an infinite decimal expansion $\text{[math]}$ , one can define a real number $\text{[math]}$ that is not in the list ( $\text{[math]}$ ) just as in Exercise 9. Is $\text{[math]}$ a rational number? Justify your answer.

11. A real number that is not algebraic is said to be a transcendental number (see page 124, Exercise 15). Let $\text{[math]}$ be the set of all transcendental numbers. Show that $\text{[math]}$ is uncountable.

Exercise Notes: For Exercise 3, apply Exercise 5 on page 123 and Exercise 2. For Exercise 9, if the decimal expansion of $\text{[math]}$ does not contain a 0 or 9, then $\text{[math]}$ will have a unique decimal representation. Thus, if the decimal expansions of $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ have different digits in at least one decimal place, then $\text{[math]}$ . For Exercise 11, use Exercise 15 on page 124 and Exercise 2.

5.4 Cardinality

In set theory, the cardinality of a set is a measure of how many elements are in the set. The set $\text{[math]}$ has 11 elements, and so the cardinality of $\text{[math]}$ is 11. Thus, $\text{[math]}$ (see Definition 5.1.2). The cardinality of an infinite set $\text{[math]}$ will also be denoted by $\text{[math]}$ . In this section, we shall present Cantor’s method for measuring the size of an infinite set without the use of numbers. There are infinite sets, as we will see, where one of these sets has cardinality much larger than that of some other infinite set. Therefore, it is possible for one infinite set to have “many more” elements than another infinite set.

What does it mean to say that two sets have the same cardinality, that is, the same size? Cantor discovered a mathematically precise and simple answer to this question.

Definition 5.4.1. For sets $\text{[math]}$ and $\text{[math]}$ , we say that $\text{[math]}$ has the same cardinality as $\text{[math]}$ , denoted by $\text{[math]}$ , if there is a bijection $\text{[math]}$ .

Remark 5.4.2. The expression $\text{[math]}$ looks like an equation; however, the assertion $\text{[math]}$ should be viewed only as an abbreviation for the statement “ $\text{[math]}$ has the same cardinality as $\text{[math]}$ .” In other words, $\text{[math]}$ means that “there is a function $\text{[math]}$ that is one-to-one and onto $\text{[math]}$ .” When $\text{[math]}$ and $\text{[math]}$ are finite sets, Theorem 5.1.7 implies that $\text{[math]}$ if and only if $\text{[math]}$ .

The relationship $\text{[math]}$ , given in Definition 5.4.1, is reflexive, symmetric, and transitive (see Exercises 4–5).

Theorem 5.4.3. Let $\text{[math]}$ be a set. Then $\text{[math]}$ .

Proof. For each $\text{[math]}$ , define $\text{[math]}$ by $\text{[math]}$ . Define the function $\text{[math]}$ by $\text{[math]}$ for each $\text{[math]}$ . Then $\text{[math]}$ is one-to-one and onto $\text{[math]}$ (see Exercise 10). ☐

Corollary 5.4.4. $\text{[math]}$ .

Theorem 5.4.5. If $\text{[math]}$ , then $\text{[math]}$ .

Proof. Suppose that $\text{[math]}$ . Thus, there is a bijection $\text{[math]}$ . Consider the function $\text{[math]}$ defined by $\text{[math]}$ for every $\text{[math]}$ . Exercise 15 on page 68 shows that $\text{[math]}$ is one-to-one. To show that $\text{[math]}$ is onto $\text{[math]}$ , assume that $\text{[math]}$ . Let $\text{[math]}$ . Since $\text{[math]}$ is onto $\text{[math]}$ , Exercise 13 on page 68 shows that $\text{[math]}$ . Therefore, $\text{[math]}$ is a bijection. ☐

Theorem 5.4.5 shows that the power set operation “preserves” cardinality. Our next theorem identifies three other such operations.

Theorem 5.4.6. Suppose that $\text{[math]}$ and $\text{[math]}$ .

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

(2) $\text{[math]}$ .

(3) $\text{[math]}$ .

Proof. Assume that $\text{[math]}$ and $\text{[math]}$ . Let $\text{[math]}$ and $\text{[math]}$ be bijections.

(1) Assume $\text{[math]}$ and $\text{[math]}$ . Let $\text{[math]}$ be defined by

Since $\text{[math]}$ , it follows that $\text{[math]}$ is a function; that is, $\text{[math]}$ is single-valued. As $\text{[math]}$ and $\text{[math]}$ are bijections, $\text{[math]}$ is a bijection because $\text{[math]}$ .

(2) Define $\text{[math]}$ by $\text{[math]}$ . Then $\text{[math]}$ is a bijection from $\text{[math]}$ to $\text{[math]}$ (see Exercise 19).

(3) We have that $\text{[math]}$ and $\text{[math]}$ are bijections. Let $\text{[math]}$ . Thus, $\text{[math]}$ . Observe that $\text{[math]}$ . Define $\text{[math]}$ by

for each $\text{[math]}$ . To prove that $\text{[math]}$ is one-to-one, let $\text{[math]}$ and $\text{[math]}$ . Assume that $\text{[math]}$ . Thus, $\text{[math]}$ for all $\text{[math]}$ . Hence,

(see Remark 3.3.11 on page 61). Since $\text{[math]}$ is one-to-one, we conclude that

: (5.12)

We now show that $\text{[math]}$ for all $\text{[math]}$ . Let $\text{[math]}$ . Thus, $\text{[math]}$ . Letting $\text{[math]}$ in (5.12), we obtain $\text{[math]}$ since $\text{[math]}$ by Theorem 3.3.18. So $\text{[math]}$ , and hence, $\text{[math]}$ is one-to-one. To prove that $\text{[math]}$ is onto $\text{[math]}$ , let $\text{[math]}$ . Then $\text{[math]}$ and $\text{[math]}$ (see Exercise 20). Therefore, the function $\text{[math]}$ is a bijection. ☐

In a similar manner, one can prove the next theorem (see Exercises 23–25).

Theorem 5.4.7. For all sets $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ , we have the following:

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

(2) $\text{[math]}$ .

(3) $\text{[math]}$ .

The proofs of our next two corollaries apply Theorems 5.4.6 and 5.4.7.

Corollary 5.4.8. $\text{[math]}$ .

Proof. Let $\text{[math]}$ . It is easy to show that ( $\text{[math]}$ ) $\text{[math]}$ . Thus,

Therefore, $\text{[math]}$ (see Exercise 5). ☐

Corollary 5.4.9. $\text{[math]}$ .

Proof. Theorems 5.2.5 and 5.2.6 imply that ( $\text{[math]}$ ) $\text{[math]}$ . Note that $\text{[math]}$ . We prove that $\text{[math]}$ as follows:

Therefore, $\text{[math]}$ . ☐

Using our cardinality notation, we will now restate some of the results that were previously established about two countably infinite sets.

Theorem 5.4.10 (Cantor). $\text{[math]}$ and $\text{[math]}$ .

Proof. Exercises 4 and 5 on page 123 imply that $\text{[math]}$ and $\text{[math]}$ are countably infinite. By Theorem 5.2.6, there are bijections $\text{[math]}$ and $\text{[math]}$ . Therefore, $\text{[math]}$ and $\text{[math]}$ . ☐

What does it mean to say that one set has smaller cardinality than another set? Cantor found a simple answer to this question as well.

Definition 5.4.11. A set $\text{[math]}$ has cardinality strictly less than that of a set $\text{[math]}$ , denoted by $\text{[math]}$ , if there is a one-to-one function $\text{[math]}$ and there is no function $\text{[math]}$ that is both one-to-one and onto $\text{[math]}$ .

Theorem 5.4.12 (Cantor). $\text{[math]}$ .

Proof. Let $\text{[math]}$ be defined by $\text{[math]}$ . This function is one-to-one. We now show that there is no function $\text{[math]}$ that is one-to-one and onto $\text{[math]}$ . Suppose, for a contradiction, there is such a bijection $\text{[math]}$ . Hence, $\text{[math]}$ is one-to-one by Theorem 3.3.18, and therefore, $\text{[math]}$ is countable. This contradicts Theorem 5.3.5. Thus, $\text{[math]}$ . ☐

After proving Theorem 5.4.12, Cantor asked the following question: Is there a set of real numbers whose cardinality is strictly between the cardinality of $\text{[math]}$ and the cardinality of $\text{[math]}$ ? In 1878, Georg Cantor announced a conjecture that is now called the continuum hypothesis.

Continuum Hypothesis. There is no set $\text{[math]}$ such that $\text{[math]}$ .

The continuum hypothesis proclaims that every set of real numbers is either countable or has the same cardinality as the set $\text{[math]}$ . Cantor struggled to resolve this conjecture, without success, for much of his career. The problem persisted and became one of the most important unsolved mathematical problems of the twentieth century. It was only after Cantor’s death that it was shown to be an unsolvable problem. The contributions of Kurt Gödel in 1940 and Paul Cohen in 1963 showed that the continuum hypothesis cannot be proven or refuted using the axioms in $\text{[math]}$ .

Recall that for every set $\text{[math]}$ , the power set $\text{[math]}$ is the set of all subsets of $\text{[math]}$ . For example, if $\text{[math]}$ , then $\text{[math]}$ and observe that $\text{[math]}$ (see Definition 5.1.2). In fact, one can prove that if $\text{[math]}$ is a finite set with $\text{[math]}$ many elements, then $\text{[math]}$ has $\text{[math]}$ many elements (see Exercise 23, page 116). Thus, $\text{[math]}$ whenever $\text{[math]}$ is a finite set; however, what happens when the set $\text{[math]}$ is infinite? Georg Cantor answered this intriguing question as well, using his diagonal argument.

Theorem 5.4.13 (Cantor). Let $\text{[math]}$ be any set. Then $\text{[math]}$ .

Proof. Let $\text{[math]}$ be a set. Let $\text{[math]}$ be defined by $\text{[math]}$ for all $\text{[math]}$ . It is easy to show that $\text{[math]}$ is one-to-one. We must show that there is no one-to-one function $\text{[math]}$ that is also onto $\text{[math]}$ . Suppose, for a contradiction, that there exists a bijection $\text{[math]}$ . Observe that $\text{[math]}$ for all $\text{[math]}$ . Let $\text{[math]}$ . Clearly, $\text{[math]}$ and thus, $\text{[math]}$ . As $\text{[math]}$ is onto $\text{[math]}$ , there is an $\text{[math]}$ such that $\text{[math]}$ . There are two cases to consider, namely, either $\text{[math]}$ or $\text{[math]}$ . If $\text{[math]}$ , then the definition of $\text{[math]}$ implies that $\text{[math]}$ . Since $\text{[math]}$ , we have that $\text{[math]}$ , which is a contradiction. If $\text{[math]}$ , then the definition of $\text{[math]}$ implies that $\text{[math]}$ . Because $\text{[math]}$ , we conclude that $\text{[math]}$ , which is again a contradiction. Thus, there is no bijection $\text{[math]}$ . Therefore, $\text{[math]}$ . ☐

Definition 5.4.14. Let $\text{[math]}$ and $\text{[math]}$ be sets. Then $\text{[math]}$ has cardinality less than or equal to $\text{[math]}$ , denoted by $\text{[math]}$ , if there is an injection $\text{[math]}$ .

Theorem 5.4.15. If $\text{[math]}$ , then $\text{[math]}$ .

Proof. Assume $\text{[math]}$ . So there is a one-to-one function $\text{[math]}$ . Define $\text{[math]}$ by $\text{[math]}$ for all $\text{[math]}$ . Exercise 15 on page 68 shows that $\text{[math]}$ is one-to-one. Therefore, $\text{[math]}$ . ☐

Theorem 5.4.15 shows that the power set operation “preserves inequality,” and its proof involves only a slight modification of the proof of Theorem 5.4.5. The following theorem identifies other set operations that also “preserve” the notion of inequality given by Definition 5.4.14. The proof can be obtained by appropriately modifying the proof of Theorem 5.4.6 (see Exercises 28–30).

Theorem 5.4.16. Suppose that $\text{[math]}$ and $\text{[math]}$ .

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

(2) $\text{[math]}$ .

(3) $\text{[math]}$ if $\text{[math]}$ is nonempty.

We will soon present the Schröder–Bernstein Theorem, which is very useful for proving many results about cardinality. The theorem states that if there are functions $\text{[math]}$ and $\text{[math]}$ that are both one-to-one, then there exists a function $\text{[math]}$ that is one-to-one and onto $\text{[math]}$ . The theorem sounds very reasonable; however, a proof that does not depend on the axiom of choice was seen as quite challenging and even eluded the brilliant Georg Cantor.

The following lemma, illustrated in Figure 5.2, will be used in our proof of the Schröder–Bernstein Theorem.

Figure 5.2. Illustration of Lemma 5.4.17 where $\text{[math]}$ satisfies $\text{[math]}$

Lemma 5.4.17. Let $\text{[math]}$ and $\text{[math]}$ be functions. Then there exists an $\text{[math]}$ that satisfies the identity

: (5.13)

Proof. Let $\text{[math]}$ and $\text{[math]}$ . Define the function $\text{[math]}$ by

Therefore, by the definition of $\text{[math]}$ , for each $\text{[math]}$ we have that $\text{[math]}$ and ( $\text{[math]}$ ) $\text{[math]}$ . So, if a set $\text{[math]}$ satisfies $\text{[math]}$ , then ( $\text{[math]}$ ) would imply that the set $\text{[math]}$ satisfies $\text{[math]}$ , and thus, (5.13) holds.

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

Proof. See Exercise 32. (Claim 1) ☐

Consider the set $\text{[math]}$ . Since $\text{[math]}$ , we see that $\text{[math]}$ , and so $\text{[math]}$ is nonempty. Let $\text{[math]}$ . Clearly, $\text{[math]}$ and $\text{[math]}$ .

Claim 2. $\text{[math]}$ .

Proof. Let $\text{[math]}$ . Because $\text{[math]}$ , we see that $\text{[math]}$ . So, $\text{[math]}$ by Claim 1. Since $\text{[math]}$ , we infer that $\text{[math]}$ . Thus, $\text{[math]}$ for every $\text{[math]}$ . Hence, $\text{[math]}$ ; that is, $\text{[math]}$ . We now prove that $\text{[math]}$ . As $\text{[math]}$ , Claim 1 implies that $\text{[math]}$ . So $\text{[math]}$ . Thus, $\text{[math]}$ ; that is, $\text{[math]}$ . Therefore, $\text{[math]}$ . (Claim 2) ☐

Since $\text{[math]}$ , we conclude that $\text{[math]}$ satisfies (5.13). (Lemma) ☐

Figure 5.2 depicts the set $\text{[math]}$ in Lemma 5.4.17 and the identity (5.13). This figure may also help the reader to better understand the proof of the following theorem, which is named for Ernst Schröder and Felix Bernstein. The proof depends only on (at most) the first seven Zermelo–Fraenkel axioms.

Theorem 5.4.18 (Schröder–Bernstein). Let $\text{[math]}$ and $\text{[math]}$ be any two sets. Suppose that $\text{[math]}$ and $\text{[math]}$ . Then $\text{[math]}$ .

Proof. Assume that $\text{[math]}$ and $\text{[math]}$ . So, there are one-to-one functions $\text{[math]}$ and $\text{[math]}$ . By Lemma 5.4.17, there is an $\text{[math]}$ (see Figure 5.2) satisfying

: (5.14)

Since $\text{[math]}$ is one-to-one, Theorems 3.2.7 and 3.3.15 imply that $\text{[math]}$ is a one-to-one function such that $\text{[math]}$ . As $\text{[math]}$ , Equation (5.14) implies that $\text{[math]}$ . Define the function $\text{[math]}$ by

: (5.15)

We will soon prove that $\text{[math]}$ is one-to-one and onto $\text{[math]}$ .

Claim 1. $\text{[math]}$ .

Proof. Clearly, $\text{[math]}$ . Since $\text{[math]}$ is one-to-one, Exercise 5 on page 68 implies that $\text{[math]}$ . Thus, by (5.14), we have that $\text{[math]}$ . (Claim 1) ☐

Claim 2. The function $\text{[math]}$ is one-to-one.

Proof. Let $\text{[math]}$ and $\text{[math]}$ . Assume that $\text{[math]}$ . The definition (5.15) of $\text{[math]}$ yields three key cases: (1) $\text{[math]}$ and $\text{[math]}$ are both in $\text{[math]}$ , (2) $\text{[math]}$ and $\text{[math]}$ are both in $\text{[math]}$ , or (3) $\text{[math]}$ and $\text{[math]}$ . The argument in case (3) will cover the fourth case: $\text{[math]}$ and $\text{[math]}$ .

(1) If $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ by (5.15). Therefore, $\text{[math]}$ because $\text{[math]}$ is one-to-one.

(2) If $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ by (5.15). Since the function $\text{[math]}$ is one-to-one, we have $\text{[math]}$ .

(3) If $\text{[math]}$ and $\text{[math]}$ , then we obtain $\text{[math]}$ . Thus, $\text{[math]}$ . Claim 1 implies that $\text{[math]}$ . Therefore, case (3) is impossible. (Claim 2) ☐

Claim 3. The function $\text{[math]}$ is onto $\text{[math]}$ .

Proof. Let $\text{[math]}$ . Hence, either (1) $\text{[math]}$ or (2) $\text{[math]}$ . We consider these two cases as follows:

(1) If $\text{[math]}$ , then $\text{[math]}$ for some $\text{[math]}$ . From the definition (5.15) of $\text{[math]}$ , it follows that $\text{[math]}$ .

(2) If $\text{[math]}$ , then (5.14) implies that $\text{[math]}$ . Thus, ( $\text{[math]}$ ) $\text{[math]}$ for some $\text{[math]}$ . By applying the function $\text{[math]}$ to both sides of ( $\text{[math]}$ ), we obtain $\text{[math]}$ . Therefore, $\text{[math]}$ as $\text{[math]}$ . (Claim 3) ☐

Since $\text{[math]}$ is a bijection, we see that $\text{[math]}$ .(Theorem) ☐

Given sets $\text{[math]}$ and $\text{[math]}$ , sometimes one can easily define one-to-one functions $\text{[math]}$ and $\text{[math]}$ ; yet it may be very difficult to specify a one-to-one function from $\text{[math]}$ onto $\text{[math]}$ . In this situation, one can apply the Schröder–Bernstein Theorem to conclude that such a function does exist and thereby conclude that $\text{[math]}$ and $\text{[math]}$ have the same cardinality.

Lemma 5.4.19. Let $\text{[math]}$ be the set of rational numbers and let $\text{[math]}$ be the set of real numbers. Then $\text{[math]}$ .

Proof. For $\text{[math]}$ , let $\text{[math]}$ . Let $\text{[math]}$ be defined by $\text{[math]}$ for each $\text{[math]}$ . To prove that $\text{[math]}$ is one-to-one, let $\text{[math]}$ and $\text{[math]}$ . Assume that $\text{[math]}$ . We shall prove that $\text{[math]}$ . Assume, for a contradiction, that $\text{[math]}$ . Without loss of generality, we can assume that $\text{[math]}$ . Since the rational numbers are dense in $\text{[math]}$ , there is a $\text{[math]}$ such that $\text{[math]}$ . Thus, $\text{[math]}$ and $\text{[math]}$ . Therefore, $\text{[math]}$ , which is a contradiction. So $\text{[math]}$ and $\text{[math]}$ is one-to-one. ☐

Theorem 5.4.20. $\text{[math]}$ .

Proof. By Theorem 5.4.10, we have that $\text{[math]}$ . Hence, by Theorem 5.4.5, we see that $\text{[math]}$ . Lemma 5.4.19 allows us to now conclude that $\text{[math]}$ . Moreover, Corollary 5.4.4 states that $\text{[math]}$ , and Lemma 5.3.4 implies that $\text{[math]}$ . Thus, $\text{[math]}$ . Therefore, by the Schröder–Bernstein Theorem 5.4.18, we have that $\text{[math]}$ . ☐

Our next corollary shows that the real line $\text{[math]}$ has the same cardinality as the plane $\text{[math]}$ .

Corollary 5.4.21. $\text{[math]}$ .

Proof. By Corollary 5.4.9, $\text{[math]}$ . Thus, $\text{[math]}$ by Theorem 5.4.20 and Theorem 5.4.6(2). ☐

Theorem 5.4.20 allows us to reformulate the continuum hypothesis:

For every infinite set $\text{[math]}$ , Theorem 5.4.13 asserts that $\text{[math]}$ . So CH can be viewed is a special case of the Generalized Continuum Hypothesis (GCH):

The combined work of Kurt Gödel and Paul Cohen also shows that the GCH cannot be proven or refuted using the axioms in $\text{[math]}$ .

Exercises 5.4

1. Let $\text{[math]}$ and let $\text{[math]}$ . Prove that $\text{[math]}$ .

2. Prove that $\text{[math]}$ .

3. Let $\text{[math]}$ and $\text{[math]}$ be countably infinite sets. Prove that $\text{[math]}$ . Conclude that $\text{[math]}$ .

4. Let $\text{[math]}$ and $\text{[math]}$ be sets. Prove that $\text{[math]}$ , and prove that if $\text{[math]}$ , then $\text{[math]}$ .

5. Prove that if $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ .

6. Prove that if $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ .

7. Let $\text{[math]}$ be countable. Prove that if $\text{[math]}$ , then $\text{[math]}$ is countable.

8. Let $\text{[math]}$ be uncountable. Prove that if $\text{[math]}$ , then $\text{[math]}$ is uncountable.

9. Prove that if $\text{[math]}$ and $\text{[math]}$ , then $\text{[math]}$ .

10. Prove that the function $\text{[math]}$ in the proof of Theorem 5.4.3 is a bijection.

11. Prove that the set $\text{[math]}$ is uncountable.

12. Using Theorem 5.4.18, prove that $\text{[math]}$ , where $\text{[math]}$ .

13. Let $\text{[math]}$ , and let $\text{[math]}$ be the function given by

The function $\text{[math]}$ is one-to-one. The proof of Theorem 5.4.13 shows that $\text{[math]}$ is not onto $\text{[math]}$ because the subset of $\text{[math]}$ defined by $\text{[math]}$ is not in the range of $\text{[math]}$ . Evaluate the set $\text{[math]}$ .

14. Let $\text{[math]}$ be onto $\text{[math]}$ , and let $\text{[math]}$ . Show that $\text{[math]}$ .

15. Suppose $\text{[math]}$ and $\text{[math]}$ . Prove that $\text{[math]}$ .

16. Suppose $\text{[math]}$ and $\text{[math]}$ . Prove that $\text{[math]}$ .

17. Prove that $\text{[math]}$ .

18. Suppose that $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ . Using Theorem 5.4.18, prove that $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ .

19. Let $\text{[math]}$ and $\text{[math]}$ be bijections. Let $\text{[math]}$ be defined by $\text{[math]}$ for all $\text{[math]}$ . Prove that $\text{[math]}$ is a bijection.

20. Prove that $\text{[math]}$ where the functions $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ are as in the proof of Theorem 5.4.6(3).

21. Recall that $\text{[math]}$ is the set of all functions from $\text{[math]}$ to $\text{[math]}$ (see Definition 3.3.6). Suppose $\text{[math]}$ is nonempty. Let $\text{[math]}$ and $\text{[math]}$ be distinct. Using a diagonal argument, show that there is no function $\text{[math]}$ that is onto $\text{[math]}$ . Now, find a one-to-one function $\text{[math]}$ . Conclude that $\text{[math]}$ .

22. Prove that $\text{[math]}$ . Conclude that $\text{[math]}$ .

23. Prove Theorem 5.4.7(1).

24. Prove Theorem 5.4.7(2).

25. Prove Theorem 5.4.7(3).

26. Using Theorem 5.4.7 and Exercise 3, prove that $\text{[math]}$ Using Exercise 22, show that $\text{[math]}$ and $\text{[math]}$ .

27. Using Theorem 5.4.7 and Corollary 5.4.8, prove that

Conclude, using Exercise 22, that $\text{[math]}$ .

28. Prove Theorem 5.4.16(1).

29. Prove Theorem 5.4.16(2).

30. Prove Theorem 5.4.16(3). Hint: Let $\text{[math]}$ and let $\text{[math]}$ be one-to-one. Define $\text{[math]}$ by

Show that $\text{[math]}$ is a “left inverse for $\text{[math]}$ ”; that is, show that $\text{[math]}$ for all $\text{[math]}$ . Now replace the use of $\text{[math]}$ in the proof of Theorem 5.4.6(3) with the function $\text{[math]}$ and modify the proof appropriately.

31. Let $\text{[math]}$ and $\text{[math]}$ be nonempty sets. Using the axiom of choice, prove that there exists a one-to-one $\text{[math]}$ if and only if there exists a $\text{[math]}$ that is onto $\text{[math]}$ .

32. Let $\text{[math]}$ and $\text{[math]}$ be functions, and let $\text{[math]}$ and $\text{[math]}$ . Prove that if $\text{[math]}$ , then $\text{[math]}$ .

33. Let $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ be as in Lemma 5.4.17. Show that if $\text{[math]}$ , then $\text{[math]}$ is onto $\text{[math]}$ and if $\text{[math]}$ , then $\text{[math]}$ is onto $\text{[math]}$ .

34. Let $\text{[math]}$ . Using Theorem 5.4.18, show that $\text{[math]}$ .

35. Let $\text{[math]}$ and $\text{[math]}$ . The functions $\text{[math]}$ defined by $\text{[math]}$ and $\text{[math]}$ defined by $\text{[math]}$ are both one-to-one. Let $\text{[math]}$ be $\text{[math]}$ . Show that $\text{[math]}$ . Now, using (5.15) as a guide, explicitly define a bijection $\text{[math]}$ .

36. Let $\text{[math]}$ and $\text{[math]}$ be functions. Consider the set $\text{[math]}$ whose elements are defined by the following recursion:

(a) $\text{[math]}$ ,

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

Let $\text{[math]}$ . Prove that if $\text{[math]}$ is one-to-one, then $\text{[math]}$ .

37. Let $\text{[math]}$ and $\text{[math]}$ . Let $\text{[math]}$ be as defined in Exercise 36. Assume $\text{[math]}$ is one-to-one and $\text{[math]}$ satisfies $\text{[math]}$ . Prove $\text{[math]}$ .

38. Let $\text{[math]}$ , $\text{[math]}$ , and $\text{[math]}$ be as in the proof of Lemma 5.4.17. Now assume that $\text{[math]}$ is one-to-one and let $\text{[math]}$ be as in Exercise 36. Prove that $\text{[math]}$ .

39. Let $\text{[math]}$ be a set and let $\text{[math]}$ . Suppose for all $\text{[math]}$ and $\text{[math]}$ in $\text{[math]}$ , we have that $\text{[math]}$ whenever $\text{[math]}$ . Let

and let $\text{[math]}$ . Prove that $\text{[math]}$ . Moreover, suppose that $\text{[math]}$ satisfies $\text{[math]}$ . Prove that $\text{[math]}$ .

Exercise Notes: For Exercise 12, use the inverse tangent function $\text{[math]}$ . For Exercise 21, review the proofs of Theorems 5.3.2 and 5.4.13. For Exercise 22, use Theorem 5.4.18. To show that $\text{[math]}$ , given $\text{[math]}$ , let $\text{[math]}$ be the set $\text{[math]}$ where $\text{[math]}$ is the function in Exercise 9 on page 116. For Exercise 23, if $\text{[math]}$ , then $\text{[math]}$ is in $\text{[math]}$ . For Exercise 24, let $\text{[math]}$ and $\text{[math]}$ . If $\text{[math]}$ , then let $\text{[math]}$ be defined by $\text{[math]}$ and let $\text{[math]}$ satisfy $\text{[math]}$ . For Exercise 25, if $\text{[math]}$ , then let $\text{[math]}$ be defined by $\text{[math]}$ . For Exercise 31, in the implication ( $\text{[math]}$ ), let $\text{[math]}$ be a left inverse for $\text{[math]}$ as in Exercise 30. The implication ( $\text{[math]}$ ) uses the axiom of choice. For Exercise 32, see Exercise 3 on page 36 and Exercise 2 on page 68. For Exercise 34, merge the two infinite decimal expansions, each one not ending with repeating 9’s, into one expansion. Exercise 36 outlines a different proof of Lemma 5.4.17 when $\text{[math]}$ is one-to-one. Use the “double subset” strategy. For Exercise 37, since $\text{[math]}$ is one-to-one, Claim 1 (in the proof of Theorem 5.4.18) implies that $\text{[math]}$ . For Exercise 38, from the proof of Lemma 5.4.17, it follows from Exercise 37 that $\text{[math]}$ . One can show that $\text{[math]}$ and $\text{[math]}$ for all $\text{[math]}$ . For Exercise 39, review the proof of Lemma 5.4.17.

REMARK: Exercises 36, 37, and 39 imply that the set $\text{[math]}$ given in the proof of Lemma 5.4.17 equals the set $\text{[math]}$ in Exercise 36 when $\text{[math]}$ is one-to-one.