9.2: Countable Sets

Preview Activity \(\PageIndex{1}\): Introduction to Infinite Sets

In Section 9.1, we defined a finite set to be the empty set or a set \(A\) such that \(A \thickapprox \mathbb{N}_k\) for some natural number \(k\). We also defined an infinite set to be a set that is not finite, but the question now is, “How do we know if a set is infinite?” One way to determine if a set is an infinite set is to use Corollary 9.8, which states that a finite set is not equivalent to any of its subsets. We can write this as a conditional statement as follows:

If \(A\) is a finite set, then \(A\) is not equivalent to any of its proper subsets. or more formally as

For each set \(A\), if \(A\) is a finite set, then for each proper subset \(B\) of \(A\), \(A \not\thickapprox B\).

1. Write the contrapositive of the preceding conditional statement. Then explain how this statement can be used to determine if a set is infinite.
2. Let DC be the set of all odd natural numbers. In Preview Activity \(\PageIndex{1}\) from Section 9.1, we proved that \(\mathbb{N} \thickapprox D^{+}\).

   (a) Use this to explain carefully why \(\mathbb{N}\) is an infinite set.
   (b) Is \(D^{+}\) a finite set or an infinite set? Explain carefully how you know.

3. Let \(b\) be a positive real number. Let (0, 1) and \((0, b)\) be the open intervals from 0 to 1 and 0 to \(b\), respectively. In Part (3) of Progress Check 9.2 (on page 454), we proved that \((0, 1) \thickapprox (0, b)\).

   (a) Use a value for \(b\) where \(0 < b < 1\) to explain why (0, 1) is an infinite set.
   (b) Use a value for \(b\) where \(b > 1\) to explain why \((0, b)\) is an infinite set.

Preview Activity \(\PageIndex{2}\): A Function from \(\mathbb{N}\) to \(\mathbb{Z}\)

In this preview activity, we will define and explore a function \(f: \mathbb{N} \to \mathbb{Z}\). We will start by defining \(f(n)\) for the first few natural numbers \(n\).

Notice that if we list the outputs of \(f\) in the order \(f(1)\), \(f(2)\), \(f(3)\), ..., we create the following list of integers: 0, 1, -1, 2, -2, 3, -3, ... . We can also illustrate the outputs of this function with the following diagram:

1. If the pattern suggested by the function values we have defined continues, what are \(f(11)\) and \(f(12)\)? What is \(f(n)\) for \(n\) from 13 to 16?
2. If the pattern of outputs continues, does the function \(f\) appear to be an injection? Does \(f\) appear to be a surjection? (Formal proofs are not required.)
   
   We will now attempt to determine a formula for \(f(n)\), where \(n \in \mathbb{N}\). We will actually determine two formulas: one for when \(n\) is even and one for when \(n\) is odd.
3. Look at the pattern of the values of \(f(n)\) when \(n\) is even. What appears to be a formula for \(f(n)\) when \(n\) is even?
4. Look at the pattern of the values of \(f(n)\) when n is odd. What appears to be a formula for \(f(n)\) when \(n\) is odd?
5. Use the work in Part (3) and Part (4) to complete the following: Define \(f: \mathbb{N} \to \mathbb{Z}\), where
   \[f(n) = \begin{cases} ?? & \text{ if \(n\) is even} \\ ?? & \text{ if \(n\) is odd.} \end{cases}\]
6. Use the formula in Part (5) to (a) Calculate \(f(1)\) through \(f(10)\). Are these results consistent with the pattern exhibited at the beginning of this preview activity?
   (b) Calculate \(f(1000)\) and \(f(1001)\).
   (c) Determine the value of \(n\) so that \(f(n) = 1000\).

In this section, we will describe several infinite sets and define the cardinal number for so-called countable sets. Most of our examples will be subsets of some of our standard numbers systems such as \(\mathbb{N}\), \(\mathbb{Z}\), and \(\mathbb{Q}\).

Infinite Sets

In Preview Activity \(\PageIndex{1}\), we saw how to use Corollary 9.8 to prove that a set is infinite. This corollary implies that if A is a finite set, then A is not equivalent to any of its proper subsets. By writing the contrapositive of this conditional statement, we can restate Corollary 9.8 in the following form:

Corollary 9.8

If a set \(A\) is equivalent to one of its proper subsets, then \(A\) is infinite.

In Preview Activity \(\PageIndex{1}\), we used Corollary 9.8 to prove that

• The set of natural numbers, \(\mathbb{N}\), is an infinite set.
• The open interval (0, 1) is an infinite set.

Although Corollary 9.8 provides one way to prove that a set is infinite, it is sometimes more convenient to use a proof by contradiction to prove that a set is infinite. The idea is to use results from Section 9.1 about finite sets to help obtain a contra- diction. This is illustrated in the next theorem.

Theorem 9.10.

Let \(A\) and \(B\) be sets.

1. If \(A\) is infinite and \(A \thickapprox B\), then \(B\) is infinite.
2. If \(A\) is infinite and \(A \subseteq B\), then \(B\) is infinite.

Proof

We will prove part (1). The proof of part (2) is exercise (3) on page 473.

To prove part (1), we use a proof by contradiction and assume that A is an infinite set, \(A \thickapprox B\), and \(B\) is not infinite. That is, \(B\) is a finite set. Since \(A \thickapprox B\) and \(B\) is finite, Theorem 9.3 on page 455 implies that \(A\) is a finite set. This is a contradiction to the assumption that \(A\) is infinite. We have therefore proved that if \(A\) is infinite and \(A \thickapprox B\), then \(B\) is infinite.

Progress Check 9.11 (Examples of Infinite Sets)

1. In Preview Activity \(\PageIndex{1}\), we used Corollary 9.8 to prove that \(\mathbb{N}\) is an infinite set. Now use this and Theorem 9.10 to explain why our standard number systems (\(\mathbb{Z}\), \(\mathbb{Q}\), and \(\mathbb{R}\)) are infinite sets. Also, explain why the set of all positive rational numbers, \(\mathbb{Q}^{+}\), and the set of all positive real numbers, \(\mathbb{R}^{+}\), are infinite sets.
2. Let \(D^{+}\) be the set of all odd natural numbers. In Part (2) of Preview Activity \(\PageIndex{1}\), we proved that \(D^{+} \thickapprox \mathbb{N}\). Use Theorem 9.10 to explain why \(D^{+}\) is an infinite set.
3. Prove that the set \(E^{+}\) of all even natural numbers is an infinite set.

Answer

Add texts here. Do not delete this text first.

Countably Infinite Sets

In Section 9.1, we used the set \(\mathbb{N}_k\) as the standard set with cardinality \(k\) in the sense that a set is finite if and only if it is equivalent to \(\mathbb{N}_k\). In a similar manner, we will use some infinite sets as standard sets for certain infinite cardinal numbers. The first set we will use is \(\mathbb{N}\).

We will formally define what it means to say the elements of a set can be “counted” using the natural numbers. The elements of a finite set can be “counted” by defining a bijection (one-to-one correspondence) between the set and \(\mathbb{N}_k\) for some natural number \(k\). We will be able to “count” the elements of an infinite set if we can define a one-to-one correspondence between the set and \(\mathbb{N}\).

Definition

The cardinality of \(\mathbb{N}\) is denoted by \(\aleph_0\). The symbol \(\aleph\) is the first letter of the Hebrew alphabet, aleph. The subscript 0 is often read as “naught” (or sometimes as “zero” or “null”). So we write

\(\text{card}(\mathbb{N}) = \aleph_0\)

and say that the cardinality of \(\mathbb{N}\) is “aleph naught.”

Definition

A set \(A\) is countably infinite provided that \(A \thickapprox \mathbb{N}\). In this case, we write

\(\text{card}(A) = \aleph_0\)

A set that is countably infinite is sometimes called a denumerable set. A set is countable provided that it is finite or countably infinite. An infinite set that is not countably infinite is called an uncountable set.

progress check 9.12. (examples of countably infinite sets)

1. In Preview Activity \(\PageIndex{1}\) from Section 9.1, we proved that \(\mathbb{N} \thickapprox D^{+}\), where \(D^{+}\) is the set of all odd natural numbers. Explain why \(\text{card}(D^{+}) = \aleph_0\).
2. Use a result from Progress Check 9.11 to explain why \(\text{card}(E^{+}) = \aleph_0\).
3. At this point, if we wish to prove a set \(S\) is countably infinite, we must find a bijection between the set \(S\) and some set that is known to be countably infinite.

   Let \(S\) be the set of all natural numbers that are perfect squares. Define a function

   \[f: S \to \mathbb{N}\]
   that can be used to prove that \(S \thickapprox \mathbb{N}\) and, hence, that \(\text{card}(S) = \aleph_0\).

Answer

Add texts here. Do not delete this text first.

The fact that the set of integers is a countably infinite set is important enough to be called a theorem. The function we will use to establish that \(\mathbb{N} \thickapprox \mathbb{Z}\) was explored in Preview Activity \(\PageIndex{2}\).

Theorem 9.13

The set \(\mathbb{Z}\) of integers is countably infinite, and so \(\text{card}(\mathbb{Z}) = \aleph_0\)

Proof

To prove that \(\mathbb{N} \thickapprox \mathbb{Z}\), we will use the following funciton: \(f: \mathbb{N} \to \mathbb{Z}\), where

\(f(n) = \begin{cases} \dfrac{n}{2} & \text{ if \(n\) is even} \\ \dfrac{1 - n}{2} & \text{ if \(n\) is odd.} \end{cases}\)

From our work in Preview Activity \(\PageIndex{2}\), it appears that if n is an even natural number, then \(f(n) > 0\), and if \(n\) is an odd natural number, then \(f(n) \le 0\). So it seems reasonable to use cases to prove that \(f\) is a surjection and that \(f\) is an injection. To prove that \(f\) is a surjection, we let \(y \in \mathbb{Z}\).

• If \(y > 0\), then \(2y \in \mathbb{N}\), and
  \[f(2y) = \dfrac{2y}{2} = y.\]
• If \(y \le 0\), then \(-2y \ge 0\) and \(1 - 2y\) is an odd natural number. Hence,
  \[f(1-2y) = \dfrac{1 - (1 - 2y)}{2} = \dfrac{2y}{2} = y.\]

These two cases prove that if \(y \in \mathbb{Z}\), then there exists an \(n \in \mathbb{N}\) such that \(f(n) = y\). Hence, \(f\) is a surjection.

To prove that \(f\) is an injection, we let \(m, n \in \mathbb{N}\) and assume that \(f(m) = f(n)\). First note that if one of \(m\) and \(n\) is odd and the other is even, then one of \(f(m)\) and \(f(n)\) is positive and the other is less than or equal to 0. So if \(f(m) = f(n)\), then both \(m\) and \(n\) must be even or both \(m\) and \(n\) must be odd.

• If both \(m\) and \(n\) are even, then
  \[f(m) = f(n) \text{ implies that } \dfrac{m}{2} = \dfrac{n}{2}\]
  and hence that \(m = n\).
• If both \(m\) and \(n\) are odd, then
  \[f(m) = f(n) \text{ implies that } \dfrac{1 - m}{2} = \dfrac{1 - n}{2}.\]
  From this, we conclude that \(1 - m = 1 - n\) and hence that \(m = n\). This proves that if \(f(m) = f(n)\), then \(m = n\) and hence that \(f\) is an injection.

Since \(f\) is both a surjection and an injection, we see that \(f\) is a bijection and, therefore, \(\mathbb{N} \thickapprox \mathbb{Z}\). Hence, \(\mathbb{Z}\) is countably infinite and \(\text{card}(\mathbb{Z}) = \aleph_0\).

The result in Theorem 9.13 can seem a bit surprising. It exhibits one of the distinctions between finite and infinite sets. If we add elements to a finite set, we will increase its size in the sense that the new set will have a greater cardinality than the old set. However, with infinite sets, we can add elements and the new set may still have the same cardinality as the original set. For example, there is a one-to-one correspondence between the elements of the sets \(\mathbb{N}\) and \(\mathbb{Z}\). We say that these sets have the same cardinality.

Following is a summary of some of the main examples dealing with the cardinality of sets that we have explored.

• The sets \(\mathbb{N}_k\), where \(k \in \mathbb{N}\), are examples of sets that are countable and finite.
• The sets \(\mathbb{N}\), \(\mathbb{Z}\), the set of all odd natural numbers, and the set of all even natural numbers are examples of sets that are countable and countably infinite.
• We have not yet proved that any set is uncountable.

The Set of Positive Rational Numbers

If we expect to find an uncountable set in our usual number systems, the rational numbers might be the place to start looking. One of the main differences between the set of rational numbers and the integers is that given any integer m, there is a next integer, namely \(m + 1\). This is not true for the set of rational numbers. We know that \(\mathbb{Q}\) is closed under division (by nonzero rational numbers) and we will see that this property implies that given any two rational numbers, we can also find a rational number between them. In fact, between any two rational numbers, we can find infinitely many rational numbers. It is this property that may lead us to believe that there are “more” rational numbers than there are integers.

The basic idea will be to “go half way” between two rational numbers. For example, if we use \(a = \dfrac{1}{3}\) and \(b = \dfrac{1}{2}\), we can use

\(\dfrac{a + b}{2} = \dfrac{1}{2} (\dfrac{1}{3} + \dfrac{1}{2}) = \dfrac{5}{12}\)

as a rational number between \(a\) and \(b\). We can then repeat this process to find a rational number between \(\dfrac{5}{12}\) and \(\dfrac{1}{2}\).

So we will now let \(a\) and \(b\) be any two rational numbers with \(a < b\) and let \(c_1 = \dfrac{a + b}{2}\). We then see that

Since \(b > a\), we see that \(b - a > 0\) and so the previous equations show that \(c_1 - a > 0\) and \(b - c_1 > 0\). We can then conclude that \(a < c_1 < b\).

We can now repeat this process by using \(c_2 = \dfrac{c_1 + b}{2}\) and proving that \(c_1 < c_2 < b\), In fact, for each natural number, we can define

\(c_{k + 1} = \dfrac{c_k + b}{2}\)

and obtain the result that \(a < c_1 < c_2 < \cdot\cdot\cdot < c_n < \cdot\cdot\cdot < b\) and this proves that the set \(\{c_k\ |\ k \in \mathbb{N}\) is a countably infinite set where each element is a rational number between \(a\) and \(b\). (A formal proof can be completed using mathematical induction. See Exercise ().

This result is true no matter how close together \(a\) and \(b\) are. For example, we can now conclude that there are infinitely many rational numbers between 0 and \(\dfrac{1}{10000}\) This might suggest that the set \(\mathbb{Q}\) of rational numbers is uncountable. Surprisingly, this is not the case. We start with a proof that the set of positive rational numbers is countable.

Theorem 9.14

The set of positive rational numbers is countably infinite.

Proof

We can write all the positive rational numbers in a two-dimensional array as shown in Figure 9.2. The top row in Figure 9.2 represents the numerator of the rational number, and the left column represents the denominator. We follow the arrows in Figure 9.2 to define \(f: \mathbb{N} \to \mathbb{Q}^{+}\). The idea is to start in the upper left corner of the table and move to successive diagonals as follows:

• We start with all fractions in which the sum of the numerator and denominator is 2 (only \(\dfrac{1}{1}\)). So \(f(1) = \dfrac{1}{1}\).
  
• We next use those fractions in which the sum of the numerator and denominator is 3. So \(f(2) = \dfrac{2}{1}\) and \(f(3) = \dfrac{1}{2}\).
• We next use those fractions in which the sum of the numerator and denominator is 4. So \(f(4) = \dfrac{1}{3}\), \(f(5) = \dfrac{3}{1}\). We skipped \(\dfrac{2}{2}\) since \(\dfrac{2}{2} = \dfrac{1}{1}\). In this way, we will ensure that the function f is a one-to-one function.

We now continue with successive diagonals omitting fractions that are not in lowest terms. This process guarantees that the function \(f\) will be an injection and a surjection. Therefore, \(\mathbb{N} \thickapprox \mathbb{Q}^{+}\) and \(\text{card}(\mathbb{Q}^{+}) = \aleph_0\).

Note: For another proof of Theorem 9.14, see exercise (14) on page 475.

Since \(\mathbb{Q}^{+}\) is countable, it seems reasonable to expect that \(Q\) is countable. We will explore this soon. On the other hand, at this point, it may also seem reasonable to ask,

"Are there any uncountable sets?”

The answer to this question is yes, but we will wait until the next section to prove that certain sets are uncountable. We still have a few more issues to deal with concerning countable sets.

Countably Infinite Sets

Theorem 9.15.

If \(A\) is a countably infinite set, then \(A \cup \{x\}\) is a countably infinite set.

Proof

Let \(A\) be a countably infinite set. Then there exists a bijection \(f: \mathbb{N} \to A\). Since \(x\) is either in \(A\) or not in \(A\), we can consider two cases.

If \(x \in A\), then \(A \cup \{x\} = A\) and \(A \cup \{x\}\) is countably infinite.

If \(x \notin A\), define \(g: \mathbb{N} \to A \cup \{x\}\) by

\(g(n) = \begin{cases} x & \text{ if \(n = 1\)} \\ f(n - 1) & \text{ if \(n > 1\).} \end{cases}\)

The proof that the function \(g\) is a bijection is Exercise (4). Since \(g\) is a bijection, we have proved that \(A \cup \{x\} \thickapprox \mathbb{N}\) and hence, \(A \cup \{x\}\) is a countably infinite set.

Theorem 9.16.

If \(A\) is a countably infinite set and \(B\) is a finite set, then \(A \cup B\) is a countably infinite set.

Proof

Exercise (5) on page 474.

Theorem 9.16 says that if we add a finite number of elements to a countably infinite set, the resulting set is still countably infinite. In other words, the cardinality of the new set is the same as the cardinality of the original set. Finite sets behave very differently in the sense that if we add elements to a finite set, we will change the cardinality. What may even be more surprising is the result in Theorem 9.17 that states that the union of two countably infinite (disjoint) sets is countably infinite. The proof of this result is similar to the proof that the integers are countably infinite (Theorem 9.13). In fact, if \(A = \{a_1, a_2, a_3, ...\}\) and \(B = \{b_1, b_2, b_3, ...\}\), then we can use the following diagram to help define a bijection from \(\mathbb{N}\) to \(A \cup B\).

Theorem 9.17

If \(A\) and \(B\) are disjoint countably infinite sets, then \(A \cup B\) is a countably infinite set.

Proof

Let \(A\) and \(B\) be countably infinite sets and let \(f: \mathbb{N} \to A\) and \(g: \mathbb{N} \to B\) be bijections. Define \(h: \mathbb{N} \to A \cup B\) by

\(h(n) = \begin{cases} f(\dfrac{n + 1}{2}) & \text{ if \(n\) is odd} \\ g(\dfrac{n}{2}) & \text{ if \(n\) is even.} \end{cases}\)

It is left as Exercise (6) on page 474 to prove that the function \(h\) is a bijection.

Since we can write the set of rational numbers Q as the union of the set of nonnegative rational numbers and the set of rational numbers, we can use the results in Theorem 9.14, Theorem 9.15, and Theorem 9.17 to prove the following theorem.

Theorem 9.18.

The set \(\mathbb{Q}\) of all rational numbers is countably infinite.

Proof

Exercise (7) on page 474.

In Section 9.1, we proved that any subset of a finite set is finite (Theorem 9.6). A similar result should be expected for countable sets. We first prove that every subset of \(\mathbb{N}\) is countable. For an infinite subset \(B\) of \(\mathbb{N}\), the idea of the proof is to define a function \(g: \mathbb{N} \to B\) by removing the elements from \(B\) from smallest to the next smallest to the next smallest, and so on. We do this by defining the function \(g\) recursively as follows:

• Let \(g(1)\) be the smallest natural number in \(B\).
• Remove \(g(1)\) from B and let \(g(2)\) be the smallest natural number in \(B - \{g(1)\}\).
• Remove \(g(2)\) and let \(g(3)\) be the smallest natural number in \(B - \{g(1), g(2)\}\).
• We continue this process. The formal recursive definition of \(g: \mathbb{N} \to B\) is included in the proof of Theorem 9.19.

Theorem 9.19.

Every subset of the natural numbers is countable.

Proof

Let \(B\) be a subset of \(\mathbb{N}\). If \(B\) is finte, then \(B\) is countable. So we next assume that \(B\) is infinite. We will next give a recursive definition of a function \(g: \mathbb{N} \to B\) and then prove that \(g\) is a bijection.

• Let \(g(1)\) be the smallest natural number in \(B\).
• For each \(n \in \mathbb{N}\), the set \(B - \{g(1), g(2), ..., g(n)\}\) is not empty since \(B\) is infinte. Define \(g(n + 1)\) to be the smallest natural number in \(B - \{g(1), g(2), ..., g(n)\}\).

The proof that the function g is a bijection is Exercise (11) on page 475.

Corollary 9.20.

Every subset of a countable set is countable.

Proof

Exercise (12) on page 475.

Exercise 9.2

1. State whether each of the following is true or false.
   
   (a) If a set \(A\) is countably infinite, then \(A\) is infinite.
   (b) If a set \(A\) is countably infinite, then \(A\) is countable.
   (c) If a set \(A\) is uncountable, then \(A\) is not countably infinite.
   (d) If \(A \thickapprox \mathbb{N}_k\) for some \(k \in \mathbb{N}\), then \(A\) is not countable.
2. Prove that each of the following sets is countably infinite.
   
   (a) The set \(F^{+}\) of all natural numbers that are multiple of 5
   (b) The set \(F\) of all integers that are multiples of 5
   (c) \(\{\dfrac{1}{2^k}\ |\ k \in \mathbb{N}\}\)
   (d) \{n \in \mathbb{Z}\ |\ n \ge -10\}\)
   (e) \(\mathbb{N} - \{4, 5, 6\}\)
   (f) \(\{m \in \mathbb{Z}\ |\ m \equiv 2\text{ (mod 3)\}\)
3. Prove part (2) of Theorem 9.10.
   Let \(A\) and \(B\) be sets. If \(A\) is infinite and \(A \subseteq B\), then \(B\) is infinite.
4. Complete the proof of Theorem 9.15 by proving the following:
   Let \(A\) be a countably infinite set and \(x \notin A\). If \(f: \mathbb{N} \to A\) is a bijection, then \(g\) is a bijection, where \(g: \mathbb{N} \to A \cup \{x\}\) by
   \[g(n) = \begin{cases} x & \text{ if \(n = 1\)} \\ f(n - 1) & \text{ if \(n > 1\).} \end{cases}\]
5. Prove Theorem 9.16.
   If \(A\) is a countably infinite set and \(B\) is a finite set, then \(A \cup B\) is a countably infinite set.

   Hint: Let card(\(B\)) \(= n\) and use a proof by induction on \(n\). Theorem 9.15 is the basis step.

6. Complete the proof of Theorem 9.17 by proving the following:
   Let \(A\) and \(B\) be disjoint countably infinite sets and let \(f: \mathbb{N} \to A\) and \(g: \mathbb{N} \to B\) be bijections. Define \(h: \mathbb{N} \to A \cup B\) by
   \[h(n) = \begin{cases} f(\dfrac{n + 1}{2} & \text{ if \(n\) is odd} \\ g(\dfrac{n}{2}) & \text{ if \(n\) is even.} \end{cases}\]
   Then the function \(h\) is a bijection.
7. Prove Theorem 9.18.
   The set \(\mathbb{Q}\) of all rational numbers is countable.
   Hint: Use Theorem 9.15 and Theorem 9.17.
8. Prove that if \(A\) is countably infinite and \(B\) is finite, then \(A - B\) is countably infinite.
9. Define \(f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}\) as follows: For each \((m, n) \in \mathbb{N} \times \mathbb{N}\),
   \[f(m, n) = 2^{m-1}(2n - 1).\]
   
   (a) Prove that \(f\) is an injection. Hint: If \(f(m, n) = f(s, t)\), there are three cases to consider: \(m > s\), \(m < s\), and \(m = s\). Use laws of exponents to prove that the first two cases lead to a contradiction.
   (b) Prove that \(f\) is a surjection. Hint: You may use the fact that if \(y \in \mathbb{N}\), then \(y = 2^{k}x\), where \(x\) is an odd natural number and \(k\) is a nonnegative integer. This is actually a consequence of the Fundamental Theorem of Arithmetic, Theorem 8.15. [See Exercise (13) in Section 8.2.]
   (c) Prove that \(\mathbb{N} \times \mathbb{N}\thickapprox \mathbb{N}\) and hence that card\((\mathbb{N} \times \mathbb{N}) = \aleph_{0}\).
10. Use Exercise (9) to prove that if \(A\) and \(B\) are countably infinite sets, then \(A \times B\) is a countably infinite set.
11. Complete the proof of Theorem 9.19 by proving that the function \(g\) defined in the proof is a bijection from \(\mathbb{N}\) to \(B\).

    Hint: To prove that \(g\) is an injection, it might be easier to prove that for all \(r, s \in \mathbb{N}\), if \(r \ne s\), then \(g(r) \ne g(s)\). To do this, we may assume that \(r < s\) since one of the two numbers must be less than the other. Then notice that \(g(r) \in \{g(1), g(2), ..., g(s - 1)\}\).

    To prove that \(g\) is a surjection, let \(b \in B\) and notice that for some \(k \in \mathbb{N}\), there will be \(k\) natural numbers in \(B\) that are less than \(b\).

12. Prove Corollary 9.20, which states that every subset of a countable set is countable.

    Hint: Let \(S\) be a countable set and assume that \(A \subseteq S\). There are two cases: \(A\) is finite or \(A\) is infinite. If \(A\) is infinite, let \(f: S \to \mathbb{N}\) be a bijection and define \(g: A \to f(A)\) by \(g(x) = f(x)\), for each \(x \in A\).

13. Use Corollary 9.20 to prove that the set of all rational numbers between 0 and 1 is countably infinite.
    
    Explorations and Activities
14. Another Proof that \(\mathbb{Q}^{+}\) Is Countable. For this activity, it may be helpful to use the Fundamental Theorem of Arithmetic (see Theorem 8.15 on page 432). Let \(\mathbb{Q}^{+}\) be the set of positive rational numbers. Every positive rational number has a unique representation as a fraction \(\dfrac{m}{n}\), where \(m\) and \(n\) are relatively prime natural numbers. We will now define a function \(f: \mathbb{Q}^{+} \to \mathbb{N}\) as follows:
    
    If \(x \in \mathbb{Q}^{+}\) and \(x = \dfrac{m}{n}\), where \(m, n \in \mathbb{N}\), \(n \ne 1\) and gcd\((m, n) = 1\), we write
    \[\begin{array} {rcl} {m} &= & {p_{1}^{\alpha_1} p_{2}^{\alpha_2} \cdot\cdot\cdot p_{r}^{\alpha_r},\text{ and}} \\ {n} &= & {q_{1}^{\beta_1} q_{2}^{\beta_2} \cdot\cdot\cdot q_{s}^{\beta_s},} \end{array}\]
    where \(p_{1}, p_{2}, ..., p_{r}\) are distinct prime numbers, \(q_{1}, q_{2}, ..., q_{s}\) are distinct prime numbers, and \(\alpha_{1}, \alpha_{2}, ..., \alpha_{r}\) and \(\beta_{1}, \beta_{2}, ..., \beta_{s}\) are natural numbers.
    We also write \(1 = 2^{0}\) when \(m = 1\). We then define
    \[f(x) = p_{1}^{2\alpha_1} p_{2}^{2\alpha_2} \cdot\cdot\cdot p_{r}^{2\alpha_r} q_{1}^{2\beta_1 - 1} q_{2}^{2\beta_2 - 1} \cdot\cdot\cdot q_{s}^{2\beta_s - 1}.\]
    If \(x = \dfrac{m}{1}\), then we define \(f(x) = p_{1}^{2\alpha_1} p_{2}^{2\alpha_2} \cdot\cdot\cdot p_{r}^{2\alpha_r} = m^2\).
    
    (a) Determine \(f(\dfrac{2}{3})\), \(f(\dfrac{5}{6})\), \(f(6)\), \(f(\dfrac{12}{25})\), \(f(\dfrac{375}{392})\), and \(f(\dfrac{2^3 \cdot 11^3}{3 \cdot 5^4})\).
    (b) If possible, find \(x \in \mathbb{Q}^{+}\) such that \(f(x) = 100\).
    (c) If possible, find \(x \in \mathbb{Q}^{+}\) such that \(f(x) = 12\).
    (d) If possible, find \(x \in \mathbb{Q}^{+}\) such that \(f(x) = 2^8 \cdot 3^5 \cdot 13 \cdot 17^2\).
    (e) Prove that the function \(f\) is an injection.
    (f) Prove that the function \(f\) is a surjection.
    (g) What has been proved?

Answer

Add texts here. Do not delete this text first.