Book of Proof
Page 32
not reduced, and in fact their reduced forms appear in the column headed
by 1. You should examine this table and convince yourself that it contains
all rational numbers in Q.
Countable and Uncountable Sets
225
0
1
−1
2
−2
3
−3
4
−4
5
−5
· · ·
0
1
−1
2
−2
3
−3
4
−4
5
−5
1
1
1
1
1
1
1
1
1
1
1
· · ·
1
−1
2
−2
3
−3
4
−4
5
−5
2
2
3
3
2
2
3
3
2
2
· · ·
1
−1
2
−2
3
−3
4
−4
5
−5
3
3
5
5
4
4
5
5
3
3
· · ·
1
−1
2
−2
3
−3
4
−4
5
−5
4
4
7
7
5
5
7
7
4
4
· · ·
1
−1
2
−2
3
−3
4
−4
5
−5
5
5
9
9
7
7
9
9
6
6
· · ·
1
−1
2
−2
3
−3
4
−4
5
−5
6
6
11
11
8
8
11
11
7
7
· · ·
1
−1
2
−2
3
−3
4
−4
5
−5
7
7
13
13
10
10
13
13
8
8
· · ·
..
.
.
.
.
.
.
.
.
.
.
.
..
..
..
..
..
..
..
..
..
. .
0
Next, draw an infinite path in this array, beginning at 1 and snaking
back and forth as indicated below. Every rational number is on this path.
0
1
−1
2
−2
3
−3
4
−4
5
−5
· · ·
0
1
−1
2
−2
3
−3
4
−4
5
−5
1
1
1
1
1
1
1
1
1
1
1
· · ·
1
−1
2
−2
3
−3
4
−4
5
−5
2
2
3
3
2
2
3
3
2
2
· · ·
1
−1
2
−2
3
−3
4
−4
5
−5
3
3
5
5
4
4
5
5
3
3
· · ·
1
−1
2
−2
3
−3
4
−4
5
−5
4
4
7
7
5
5
7
7
4
4
· · ·
1
−1
2
−2
3
−3
4
−4
5
−5
5
5
9
9
7
7
9
9
6
6
· · ·
1
−1
2
−2
3
−3
4
−4
5
−5
6
6
11
11
8
8
11
11
7
7
· · ·
1
−1
2
−2
3
−3
4
−4
5
−5
7
7
13
13
10
10
13
13
8
8
· · ·
1
−1
2
−2
3
−3
4
−4
5
−5
8
8
15
15
11
11
15
15
9
9
· · ·
1
−1
2
−2
3
−3
4
−4
5
−5
9
9
17
17
13
13
17
17
&nb
sp; 11
11
· · ·
..
.
.
.
.
.
.
.
.
.
.
.
..
..
..
..
..
..
..
..
..
. .
226
Cardinality of Sets
0
Beginning at 1 and following the path, we get an infinite list of all
rational numbers:
1
1
2 2
1 1 1
1 2
2
2
2
2
3
0, 1,
, − , −1, 2, , , − , , , − , , − , − , − , − , −2, 3, , ...
2
2
3 5
3 3 4
4 7
7
5
3
3
2
By Theorem 13.3, it follows that Q is countably infinite, that is, |Q| = |N|.
■
It is also true that the Cartesian product of two countably infinite sets
is itself countably infinite, as our next theorem states.
Theorem 13.5
If A and B are both countably infinite, then so is A × B.
Proof. Suppose A and B are both countably infinite. By Theorem 13.3, we
know we can write A and B in list form as
A
= ©a1, a2, a3, a4, . . . ª,
B
= ©b1, b2, b3, b4, . . . ª.
Figure 13.2 shows how to form an infinite path winding through all of A ×B.
Therefore A × B can be written in list form, so it is countably infinite.
■
B ..
.
.
.
.
.
.
.
.
..
..
..
..
..
..
..
b
(a
7
1, b7) (a2, b7) (a3, b7) (a4, b7) (a5, b7) (a6, b7) (a7, b7) · · ·
b
(a
6
1, b6) (a2, b6) (a3, b6) (a4, b6) (a5, b6) (a6, b6) (a7, b6) · · ·
b
(a
5
1, b5) (a2, b5) (a3, b5) (a4, b5) (a5, b5) (a6, b5) (a7, b5) · · ·
b
(a
4
1, b4) (a2, b4) (a3, b4) (a4, b4) (a5, b4) (a6, b4) (a7, b4) · · ·
b
(a
3
1, b3) (a2, b3) (a3, b3) (a4, b3) (a5, b3) (a6, b3) (a7, b3) · · ·
b
(a
2
1, b2) (a2, b2) (a3, b2) (a4, b2) (a5, b2) (a6, b2) (a7, b2) · · ·
b
(a
1
1, b1) (a2, b1) (a3, b1) (a4, b1) (a5, b1) (a6, b1) (a7, b1) · · ·
a1
a2
a3
a4
a5
a6
a7
· · ·
A
Figure 13.2. A product of two countably infinite sets is countably infinite
Countable and Uncountable Sets
227
As an example of a consequence of this theorem, notice that since Q is
countably infinite, the set Q × Q is also countably infinite.
Recall that the word “corollary” means a result that follows easily from
some other result. We have the following corollary of Theorem 13.5.
Corollary 13.1
Given n countably infinite sets A1, A2, A3, . . . , An, with
n ≥ 2, the Cartesian product A1 × A2 × A3 ×···× An is also countably infinite.
Proof. The proof is by induction on n. For the basis step, notice that when
n = 2 the statement asserts that for countably infinite sets A1 and A2, the
product A1 × A2 is countably infinite, and this is true by Theorem 13.5.
Assume that for k ≥ 2, any product A1 × A2 × A3 × · · · ×Ak of countably
infinite sets is countably infinite. Consider a product A1 × A2 × A3 ×· · ·× Ak+1
of k + 1 countably infinite sets. It is easily confirmed that the function
f : A1 × A2 × A3 × ··· × Ak × Ak+1 −→ (A1 × A2 × A3 × ··· × Ak) × Ak+1
f (x
¢
1, x2, . . . , xk, xk+1)
=
¡(x1, x2,..., xk), xk+1
is bijective, so |A1 × A2 × A3 × · · · × Ak × Ak+1| = |(A1 × A2 × A3 × · · · × Ak) × Ak+1|.
By the induction hypothesis, (A1 × A2 × A3 × · · · × Ak) × Ak+1 is a product of
two countably infinite sets, so it is countably infinite by Theorem 13.5. As
noted above, A1 × A2 × A3 × · · · × Ak × Ak+1 has the same cardinality, so it too
is countably infinite.
■
Theorem 13.6
If A and B are both countably infinite, then A ∪ B is
countably infinite.
Proof. Suppose A and B are both countably infinite. By Theorem 13.3, we
know we can write A and B in list form as
A
= ©a1, a2, a3, a4, . . . ª,
B
= ©b1, b2, b3, b4, . . . ª.
We can “shuffle” A and B into one infinite list for A ∪ B as follows.
A ∪ B = ©a1, b1, a2, b2, a3, b3, a4, b4,...ª.
(We agree not to list an element twice if it belongs to both A and B.)
Therefore, by Theorem 13.3, it follows that A ∪ B is countably infinite.
■
228
Cardinality of Sets
Exercises for Section 13.2
1. Prove that the set A = ©ln(n) : n ∈ Nª ⊆ R is countably infinite.
2. Prove that the set A = ©(m, n) ∈ N × N : m ≤ nª is countably infinite.
3. Prove that the set A = ©(5n,−3n) : n ∈ Zª is countably infinite.
4. Prove that the set of all irrational numbers is uncountable. (Suggestion:
Consider proof by contradiction using Theorems 13.4 and 13.6.)
5. Prove or disprove: There exists a countably infinite subset of the set of irrational
numbers.
6. Prove or disprove: There exists a bijective function f : Q → R.
7. Prove or disprove: The set Q100 is countably infinite.
8. Prove or disprove: The set Z × Q is countably infinite.
9.
©
Prove or disprove: The set 0, 1ª × N is countably infinite.
p
10.
2
Prove or disprove: The set A = ©
: n
n
∈ Nª countably infinite.
11. Describe a partition of N that divides N into eight countably infinite subsets.
12. Describe a partition of N that divides N into ℵ0 countably infinite subsets.
13. Prove or disprove: If A = {X ⊆ N : X is finite}, then |A| = ℵ0.
14. Suppose A = ©(m, n) ∈ N × R : n = π mª. Is it true that |N| = |A|?
15. Theorem 13.5 implies that N × N is countably infinite. Construct an alternate
proof of this fact by showing that the function ϕ : N × N → N defined as ϕ(m, n) =
2n−1(2m − 1) is bijective.
13.3 Comparing Cardinalities
At this point we know that there are at least two different kinds of infinity.
On one hand, there are countably infinite sets such as N, of cardinality ℵ0.
Then there is the uncountable set R. Are there other kinds of infinit
y
beyond these two kinds? The answer is “yes,” but to see why we first need
to introduce some new definitions and theorems.
Our first task will be to formulate a definition for what we mean by
|A| < |B|. Of course if A and B are finite we know exactly what this means:
|A| < |B| means that when the elements of A and B are counted, A is found
to have fewer elements than B. But this process breaks down if A or B is
infinite, for then the elements can’t be counted.
The language of functions helps us overcome this difficulty. Notice
that for finite sets A and B it is intuitively clear that |A| < |B| if and only
if there exists an injective function f : A → B but there are no surjective
functions f : A → B. The following diagram illustrates this:
Comparing Cardinalities
229
A
B
f
a
0
b
1
c
2
d
3
4
We will use this idea to define what is meant by |A| < |B| and |A| ≤ |B|. For
emphasis, the following definition also restates what is meant by |A| = |B|.
Definition 13.4
Suppose A and B are sets.
(1) |A| = |B| means there is a bijection A → B.
(2) |A| < |B| means there is an injection A → B, but no surjection A → B.
(3) |A| ≤ |B| means |A| < |B| or |A| = |B|.
For example, consider N and R. The function f : N → R defined as f (n) = n
1
is clearly injective, but it is not surjective because given the element 2 ∈ R,
we have f (n) 6= 12 for every n ∈ N. In fact, Theorem 13.2 of Section 13.1
asserts that there is no surjection N → R. Definition 13.4 yields
|N| < |R|.
(13.1)
Said differently, ℵ0 < |R|.
Is there a set X for which |R| < |X |? The answer is “yes,” and the next
theorem explains why. It implies |R| < |P(R)|. (Recall that P(A) denotes
the power set of A.)
Theorem 13.7
If A is any set, then |A| < |P(A)|.
Proof. Before beginning the proof, we remark that this statement is obvious
if A is finite, for then |A| < 2|A| = |P(A)|. But our proof must apply to all
sets A, both finite and infinite, so it must use Definition 13.4.
We prove the theorem with direct proof. Let A be an arbitrary set.
According to Definition 13.4, to prove |A| < |P(A)| we must show that there
is an injection f : A → P(A), but no surjection f : A → P(A).
To see that there is an injection f : A → P(A), define f by the rule
f (x) = ©xª. In words, f sends any element x of A to the one-element set
©xª ∈ P(A). Then f : A → P(A) is injective, as follows. Suppose f (x) = f (y).
©
©
©
Then xª = © yª. Now, the only way that xª and
yª can be equal is if x = y,
so it follows that x = y. Thus f is injective.
Next we need to show that there exists no surjection f : A → P(A).
Suppose for the sake of contradiction that there does exist a surjection
230
Cardinality of Sets
f : A → P(A). Notice that for any element x ∈ A, we have f (x) ∈ P(A), so
f (x) is a subset of A. Thus f is a function that sends elements of A to
subsets of A. It follows that for any x ∈ A, either x is an element of the
subset f (x) or it is not. Using this idea, define the following subset B of A:
B = ©x ∈ A : x ∉ f (x)ª ⊆ A.
Now since B ⊆ A we have B ∈ P(A), and since f is surjective there is an
a ∈ A for which f (a) = B. Now, either a ∈ B or a ∉ B. We will consider these
two cases separately, and show that each leads to a contradiction.