Countable Sets

Section 9.2 Countable Sets

Beginning Activity Beginning Activity 1: Introduction to Infinite Sets
A4 US

In Section 9.1, we defined a finite set to be the empty set or a set

A

such that

A \approx 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 ≉ 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 $D^{+}$ be the set of all odd natural numbers. In Beginning Activity 1 from Section 9.1, we proved that $N \approx D^{+} .$

🔗

(a)

Use this to explain carefully why $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 Task 9.2.c of Progress Check 9.2, we proved that $(0, 1) \approx (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.

🔗

Beginning Activity Beginning Activity 2: A Function from $N$ to $Z$
A4 US

🔗

In this activity, we will define and explore a function

f : N \to Z .

We will start by defining

f (n)

for the first few natural numbers

n .

\begin{aligned} f (1) & = 0 \\ f (2) & = 1 & f (3) & = - 1 \\ f (4) & = 2 & f (5) & = - 2 \\ f (6) & = 3 & f (7) & = - 3 \end{aligned}

🔗

Notice that if we list the outputs of

f

in the order

f (1), f (2), f (3), \dots,

we create the following list of integers:

0, 1, - 1, 2, - 2, 3, - 3, \dots .

We can also illustrate the outputs of this function with the following diagram:

1	2	3	4	5	6	7	8	9	10	$\dots$
$↓$	$↓$	$↓$	$↓$	$↓$	$↓$	$↓$	$↓$	$↓$	$↓$	$\dots$
0	1	$- 1$	2	$- 2$	3	$- 3$	4	$- 4$	5	$\dots$

🔗

Figure 9.10. A Function from

N

Z

🔗

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 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 Exercise 3 and Exercise 4 to complete the following: Define $f : N \to Z,$ where

f (n) = {\begin{matrix} ? ? if n is even \\ ? ? if n is odd . \end{matrix}

🔗

6.

Use the formula in Exercise 5 to

🔗

(a)

Calculate $f (1)$ through $f (10) .$ Are these results consistent with the pattern exhibited at the start of this 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 number systems such as

N,

Z,

and

Q .

🔗

Subsection Infinite Sets

🔗

In Beginning Activity 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 Restated.

🔗

If a set

A

is equivalent to one of its proper subsets, then

A

is infinite.

🔗

In Beginning Activity 1, we used Corollary 9.8 to prove that

The set of natural numbers, $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 contradiction. This is illustrated in the next theorem.

🔗

Theorem 9.11.

Let $A$ and $B$ be sets.

If $A$ is infinite and $A \approx B,$ then $B$ is infinite.
If $A$ is infinite and $A \subseteq B,$ then $B$ is infinite.

🔗

Proof.

We will prove Item 1. The proof of Item 2 is Exercise 3.

To prove Item 1, we use a proof by contradiction and assume that $A$ is an infinite set, $A \approx B,$ and $B$ is not infinite. That is, $B$ is a finite set. Since $A \approx B$ and $B$ is finite, Theorem 9.3 on Theorem 9.3 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 \approx B,$ then $B$ is infinite.

🔗

Progress Check 9.12. Examples of Infinite Sets.

🔗

(a)

In Beginning Activity 1, we used Corollary 9.8 to prove that $N$ is an infinite set. Now use this and Theorem 9.11 to explain why our standard number systems $(Z, Q, and R)$ are infinite sets. Also, explain why the set of all positive rational numbers, $Q^{+},$ and the set of all positive real numbers, $R^{+},$ are infinite sets.

Solution.

The set of natural numbers $N$ is a subset of $Z,$ $Q,$ and $R .$ Since $N$ is an infinite set, we can use Item 2 of Theorem 9.11 to conclude that $Z,$ $Q,$ and $R$ are infinite sets.

🔗

(b)

Let $D^{+}$ be the set of all odd natural numbers. In Exercise 2 of Beginning Activity 1, we proved that $D^{+} \approx N .$ Use Theorem 9.11 to explain why $D^{+}$ is an infinite set.

Solution.

Use Item 1 of Theorem 9.11.

🔗

(c)

Prove that the set $E^{+}$ of all even natural numbers is an infinite set.

Solution.

Prove that $E^{+} \approx N$ and use Item 1 of Theorem 9.11.

🔗

Subsection Countably Infinite Sets

🔗

In Section 9.1, we used the set

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

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

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

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

N .

🔗

Definition.

The cardinality of $N$ is denoted by $ℵ_{0} .$ The symbol $ℵ$ 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

card (N) = ℵ_{0}

and say that the cardinality of $N$ is “aleph naught.”

🔗

Defintion.

A set $A$ is countably infinite provided that $A \approx N .$ In this case, we write

card (A) = ℵ_{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.13. Examples of Countably Infinite Sets.

🔗

(a)

In Beginning Activity 1 from Section 9.1, we proved that $N \approx D^{+},$ where $D^{+}$ is the set of all odd natural numbers. Explain why $card (D^{+}) = ℵ_{0} .$

Solution.

Use the definition of a countably infinite set.

🔗

(b)

Use a result from Progress Check 9.12 to explain why $card (E^{+}) = ℵ_{0} .$

Solution.

Since $E^{+} \approx N,$ we can conclude that $card (E^{+}) = ℵ_{0} .$

🔗

(c)

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 N

that can be used to prove that $S \approx N$ and, hence, that $card (S) = ℵ_{0} .$

Solution.

One function that can be used is $f : S \to N$ defined by $f (m) = \sqrt{m}$ for all $m \in S .$

🔗

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

N \approx Z

was explored in Beginning Activity 2.

🔗

Theorem 9.14.

The set $Z$ of integers is countably infinite, and so $card (Z) = ℵ_{0} .$

🔗

Proof.

To prove that $N \approx Z,$ we will use the following function: $f : N \to Z,$ where

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

From our work in Beginning Activity 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) \leq 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 Z .$

If $y > 0,$ then $2 y \in N,$ and

$f (2 y) = \frac{2 y}{2} = y .$
If $y \leq 0,$ then $- 2 y \geq 0$ and $1 - 2 y$ is an odd natural number. Hence,

$f (1 - 2 y) = \frac{1 - (1 - 2 y)}{2} = \frac{2 y}{2} = y .$

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

To prove that $f$ is an injection, we let $m, n \in 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) implies that \frac{m}{2} = \frac{n}{2}$

and hence that $m = n .$
If both $m$ and $n$ are odd, then

$f (m) = f (n) implies that \frac{1 - m}{2} = \frac{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, $N \approx Z .$ Hence, $Z$ is countably infinite and $card (Z) = ℵ_{0} .$

🔗

The result in Theorem 9.14 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

N

and

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 $N_{k},$ where $k \in N,$ are examples of sets that are countable and finite.
The sets $N,$ $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.

🔗

Subsection 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

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 = \frac{1}{3}

and

b = \frac{1}{2},

we can use

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

🔗

as a rational number between

a

and

b .

We can then repeat this process to find a rational number between

\frac{5}{12}

and

\frac{1}{2} .

🔗

So we will now let

a

and

b

be any two rational numbers with

a < b

and let

c_{1} = \frac{a + b}{2} .

We then see that

\begin{aligned} c_{1} - a & = \frac{a + b}{2} - a & b - c_{1} & = b - \frac{a + b}{2} \\ = \frac{a + b}{2} - \frac{2 a}{2} & = \frac{2 b}{2} - \frac{a + b}{2} \\ = \frac{b - a}{2} & = \frac{b - a}{2} \end{aligned}

🔗

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} = \frac{c_{1} + b}{2}

and proving that

c_{1} < c_{2} < b .

In fact, for each natural number, we can define

c_{k + 1} = \frac{c_{k} + b}{2}

🔗

and obtain the result that

a < c_{1} < c_{2} < \dots < c_{n} < \dots < b

and this proves that the set

{c_{k} ∣ k \in 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 14.

🔗

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

\frac{1}{10000} .

This might suggest that the set

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.15.

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.16.

Figure 9.16. Counting the Positive Rational Numbers

The top row in Figure 9.16 represents the numerator of the rational number, and the left column represents the denominator. We follow the arrows in Figure 9.16 to define $f : N \to 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 \frac{1}{1}) .$ So $f (1) = \frac{1}{1} .$
We next use those fractions in which the sum of the numerator and denominator is 3. So $f (2) = \frac{2}{1}$ and $f (3) = \frac{1}{2} .$
We next use those fractions in which the sum of the numerator and denominator is 4. So $f (4) = \frac{1}{3},$ $f (5) = \frac{3}{1} .$ We skipped $\frac{2}{2}$ since $\frac{2}{2} = \frac{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, $N \approx Q^{+}$ and $card (Q^{+}) = ℵ_{0} .$

🔗

Note: For another proof of Theorem 9.15, see Activity 51.

🔗

Since

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.

🔗

Subsection Countably Infinite Sets

🔗

Theorem 9.17.

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 : 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 : N \to A \cup {x}$ by

g (n) = {\begin{cases} x & if n = 1 \\ f (n - 1) & 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} \approx N$ and hence, $A \cup {x}$ is countably infinite.

🔗

Theorem 9.18.

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.

🔗

Theorem 9.18 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.20 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.14). In fact, if

A = {a_{1}, a_{2}, a_{3}, \dots}

and

B = {b_{1}, b_{2}, b_{3}, \dots},

then we can use the following diagram to help define a bijection from

N

A \cup B .

1	2	3	4	5	6	7	8	9	10	$\dots$
$↓$	$↓$	$↓$	$↓$	$↓$	$↓$	$↓$	$↓$	$↓$	$↓$	$\dots$
$a_{1}$	$b_{1}$	$a_{2}$	$b_{2}$	$a_{3}$	$b_{3}$	$a_{4}$	$b_{4}$	$a_{5}$	$b_{5}$	$\dots$

🔗

Figure 9.19. A Function from

N

A \cup B

🔗

Theorem 9.20.

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 : N \to A$ and $g : N \to B$ be bijections. Define $h : N \to A \cup B$ by

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

It is left as Exercise 6 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 negative rational numbers, we can use the results in Theorem 9.15, Theorem 9.17, and Theorem 9.20 to prove the following theorem.

🔗

Theorem 9.21.

The set $Q$ of all rational numbers is countably infinite.

🔗

Proof.

Exercise 7.

🔗

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

N

is countable. For an infinite subset

B

N,

the idea of the proof is to define a function

g : 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 : N \to B$ is included in the proof of Theorem 9.22.

🔗

Theorem 9.22.

Every subset of the natural numbers is countable.

🔗

Proof.

Let $B$ be a subset of $N .$ If $B$ is finite, then $B$ is countable. So we next assume that $B$ is infinite. We will next give a recursive definition of a function $g : 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 N,$ the set $B - {g (1), g (2), \dots, g (n)}$ is not empty since $B$ is infinite. Define $g (n + 1)$ to be the smallest natural number in $B - {g (1), g (2), \dots, g (n)} .$

The proof that the function $g$ is a bijection is Exercise 11.

🔗

Corollary 9.23.

Every subset of a countable set is countable.

🔗

Proof.

Exercise 12.

🔗

Exercises Exercises

🔗

1.

State whether each of the following is true or false.

🔗

(a)

If a set $A$ is countably infinite, then $A$ is infinite.

Answer.

True.

🔗

(b)

If a set $A$ is countably infinite, then $A$ is countable.

Answer.

True.

🔗

(c)

If a set $A$ is uncountable, then $A$ is not countably infinite.

Answer.

True.

🔗

(d)

If $A \approx N_{k}$ for some $k \in N,$ then $A$ is not countable.

Answer.

False.

🔗

2.

Prove that each of the following sets is countably infinite.

🔗

(a)

The set $F^{+}$ of all natural numbers that are multiples of 5

Answer.

Prove that the function $f : N \to F^{+}$ defined by $f (n) = 5 n$ for all $n \in N$ is a bijection.

🔗

(b)

The set $F$ of all integers that are multiples of 5

🔗

(c)

${\frac{1}{2^{k}} | k \in N}$

🔗

(d)

${n \in Z ∣ n \geq - 10}$

🔗

(e)

$N - {4, 5, 6}$

Answer.

One way is to define $f : N \to N - {4, 5, 6}$ by

f (n) = {\begin{cases} n & if n = 1, n = 2, or n = 3 \\ f (n + 3) & if n \geq 4 . \end{cases}

and then prove that the function $f$ is a bijection. It is also possible to use Corollary 9.23 to conclude that $N - {4, 5, 6}$ is countable, but it must also be proved that $N - {4, 5, 6}$ cannot be finite. To do this, assume that $N - {4, 5, 6}$ is finite and then prove that $N$ is finite, which is a contradiction.

🔗

(f)

${m \in Z ∣ m \equiv 2 (\mod 3)}$

Answer.

Let $A = {m \in Z ∣ m \equiv 2 (\mod 3)} = {3 k + 2 ∣ k \in Z} .$ Prove that the function $f : Z \to A$ is a bijection, where $f (x) = 3 x + 2$ for all $x \in Z .$ This proves that $Z \approx A$ and hence, $N \approx A .$

🔗

3.

Prove Item 2 of Theorem 9.11.

Hint.

Let $A$ and $B$ be sets. If $A$ is infinite and $A \subseteq B,$ then $B$ is infinite.

Answer.

For each $n \in N,$ let $P (n)$ be “If $card (B) = n,$ then $A \cup B$ is a countably infinite set.”

Note that if $card (B) = k + 1$ and $x \in B,$ then $card (B - {x}) = k .$ Apply the inductive assumption to $B - {x} .$

🔗

4.

Complete the proof of Theorem 9.17 by proving the following: Let $A$ be a countably infinite set and $x \notin A .$ If $f : N \to A$ is a bijection, then $g$ is a bijection, where $g : N \to A \cup {x}$ by

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

🔗

5.

Prove Theorem 9.18.

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.17 is the basis step.

🔗

6.

Complete the proof of Theorem 9.20 by proving the following: Let $A$ and $B$ be disjoint countably infinite sets and let $f : N \to A$ and $g : N \to B$ be bijections. Define $h : N \to A \cup B$ by

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

Then the function $h$ is a bijection.

Answer.

Let $m, n \in N$ and assume that $h (n) = h (m) .$ Then since $A$ and $B$ are disjoint, either $h (n)$ and $h (m)$ are both in $A$ or are both in $B .$ If they are both in $A,$ then both $m$ and $n$ are odd and

f (\frac{n + 1}{2}) = h (n) = h (m) = f (\frac{m + 1}{2}) .

Since $f$ is an injection, this implies that $\frac{n + 1}{2} = \frac{m + 1}{2}$ and hence that $n = m .$ Similary, if both $h (n)$ and $h (m)$ are in $B,$ then $m$ and $n$ are even and $g (\frac{n}{2}) = g (\frac{m}{2}),$ and since $g$ is an injection, $\frac{n}{2} = \frac{m}{2}$ and $n = m .$ Therefore, $h$ is an injection.

Now let $y \in A \cup B .$ There are only two cases to consider: $y \in A$ or $y \in B .$ If $y \in A,$ then since $f$ is a surjection, there exists an $m \in N$ such that $f (m) = y .$ Let $n = 2 m - 1 .$ Then $n$ is an odd natural number, $m = \frac{n + 1}{2},$ and

h (n) = f (\frac{n + 1}{2}) = f (m) = y .

Now assume $y \in B$ and use the fact that $g$ is a surjection to help prove that there exists a natural number $n$ such that $h (n) = y .$ We can then conclude that $h$ is a surjection.

🔗

7.

Prove Theorem 9.21.

The set $Q$ of all rational numbers is countable.

Hint.

Use Theorem 9.17 and Theorem 9.20.

Answer.

By Theorem 9.15, the set $Q^{+}$ of positive rational numbers is countably infinite. So by Theorem 9.17, $Q^{+} \cup {0}$ is countably infinite. Now prove that the set $Q^{-}$ of all negative rational numbers is countably infinite and then use Theorem 9.20 to prove that $Q$ is countably infinite.

🔗

8.

Prove that if $A$ is countably infinite and $B$ is finite, then $A - B$ is countably infinite.

Answer.

Since $A - B \subseteq A,$ the set $A - B$ is countable. Now assume $A - B$ is finite and show that this leads to a contradiction.

🔗

9.

Define $f : N \times N \to N$ as follows: For each $(m, n) \in N \times N,$

f (m, n) = 2^{m - 1} (2 n - 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 N,$ then $y = 2^{k} x,$ where $x$ is an odd natural number and $k$ is a non-negative integer. This is actually a consequence of the Fundamental Theorem of Arithmetic, Theorem 8.17. [See Exercise 13 in Section 8.2.]

🔗

(c)

Prove that $N \times N \approx N$ and hence that $card (N \times N) = ℵ_{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.22 by proving that the function $g$ defined in the proof is a bijection from $N$ to $B .$

Hint.

To prove that $g$ is an injection, it might be easier to prove that for all $r, s \in N,$ if $r \neq s,$ then $g (r) \neq 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), \dots, g (s - 1)} .$ To prove that $g$ is a surjection, let $b \in B$ and notice that for some $k \in N,$ there will be $k$ natural numbers in $B$ that are less than $b .$

🔗

12.

Prove Corollary 9.23, 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 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.23 to prove that the set of all rational numbers between 0 and 1 is countably infinite.

🔗

14.

Let $a, b \in Q$ with $a < b .$ In The Set of Positive Rational Numbers, we proved that $c = \frac{a + b}{2}$ is a rational number and that $a < c < b,$ which proves that here is a rational number between any two (unequal) rational numbers.

🔗

(a)

Now let $c_{1} = \frac{a + b}{2},$ and define $c_{2} = \frac{c_{1} + b}{2} .$ Prove that $c_{1} < c_{2} < b$ and hence, that $a < c_{1} < c_{2} < b .$

🔗

(b)

For each $k \in N,$ define

c_{k + 1} = \frac{c_{k} + b}{2} .

Prove that for each $k \in N,$ $a < c_{k} < c_{k + 1} < b .$ Use this to explain why the set ${c_{k} ∣ k \in N}$ is an infinite set where each element is a rational number between $a$ and $b .$

🔗

Activity 51. Another Proof that $Q^{+}$ Is Countable.

For this activity, it may be helpful to use the Fundamental Theorem of Arithmetic (see Theorem 8.17. Let $Q^{+}$ be the set of positive rational numbers. Every positive rational number has a unique representation as a fraction $\frac{m}{n},$ where $m$ and $n$ are relatively prime natural numbers. We will now define a function $f : Q^{+} \to N$ as follows:

If $x \in Q^{+}$ and $x = \frac{m}{n},$ where $m, n \in N,$ $n \neq 1$ and $gcd (m, n) = 1,$ we write

\begin{aligned} m & = p_{1}^{α_{1}} p_{2}^{α_{2}} \dots p_{r}^{α_{r}}, and \\ n & = q_{1}^{β_{1}} q_{2}^{β_{2}} \dots q_{s}^{β_{s}}, \end{aligned}

where $p_{1},$ $p_{2},$ …, $p_{r}$ are distinct prime numbers, $q_{1},$ $q_{2},$ …, $q_{s}$ are distinct prime numbers, and $α_{1},$ $α_{2},$ …, $α_{r}$ and $β_{1},$ $β_{2},$ …, $β_{s}$ are natural numbers. We also write $1 = 2^{0}$ when $m = 1 .$ We then define

f (x) = p_{1}^{2 α_{1}} p_{2}^{2 α_{2}} \dots p_{r}^{2 α_{r}} q_{1}^{2 β_{1} - 1} q_{2}^{2 β_{2} - 1} \dots q_{s}^{2 β_{s} - 1} .

If $x = \frac{m}{1},$ then we define $f (x) = p_{1}^{2 α_{1}} p_{2}^{2 α_{2}} \dots p_{r}^{2 α_{r}} = m^{2} .$

🔗

(a)

Determine $f (\frac{2}{3}),$ $f (\frac{5}{6}),$ $f (6),$ $f (\frac{12}{25}),$ $f (\frac{375}{392}),$ and $f (\frac{2^{3} \cdot 11^{3}}{3 \cdot 5^{4}}) .$

🔗

(b)

If possible, find $x \in Q^{+}$ such that $f (x) = 100 .$

🔗

(c)

If possible, find $x \in Q^{+}$ such that $f (x) = 12 .$

🔗

(d)

If possible, find $x \in 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?

Section 9.2 Countable Sets

Beginning Activity Beginning Activity 1: Introduction to Infinite Sets A4US

1.

2.

(a)

(b)

3.

(a)

(b)

Beginning Activity Beginning Activity 2: A Function from N to Z A4US

1.

2.

3.

4.

5.

6.

(a)

(b)

(c)

Subsection Infinite Sets

Corollary 9.8 Restated.

Theorem 9.11.

Proof.

Progress Check 9.12. Examples of Infinite Sets.

(a)

(b)

(c)

Subsection Countably Infinite Sets

Definition.

Defintion.

Progress Check 9.13. Examples of Countably Infinite Sets.

(a)

(b)

(c)

Theorem 9.14.

Proof.

Subsection The Set of Positive Rational Numbers

Theorem 9.15.

Proof.

Subsection Countably Infinite Sets

Theorem 9.17.

Proof.

Theorem 9.18.

Proof.

Theorem 9.20.

Proof.

Theorem 9.21.

Proof.

Theorem 9.22.

Proof.

Corollary 9.23.

Proof.

Exercises Exercises

1.

(a)

(b)

(c)

(d)

2.

(a)

(b)

(c)

(d)

(e)

(f)

3.

4.

5.

6.

7.

8.

9.

(a)

(b)

(c)

10.

11.

12.

13.

14.

Beginning Activity Beginning Activity 1: Introduction to Infinite Sets
A4 US

Beginning Activity Beginning Activity 2: A Function from $N$ to $Z$
A4 US

Activity 51. Another Proof that $Q^{+}$ Is Countable.