exists a bijection f : A → B. If no such bijection exists, then |A| 6= |B|.
Example 13.2
This example shows that |N| = |Z|. To see why this is true,
notice that the following table describes a bijection f : N → Z.
n
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
. . .
f (n)
0
1
−1
2
−2
3
−3
4
−4
5
−5
6
−6
7
−7
. . .
Notice that f is described in such a way that it is both injective and
surjective. Every integer appears exactly once on the infinitely long second
row. Thus, according to the table, given any b ∈ Z there is some natural
number n with f (n) = b, so f is surjective. It is injective because the way
the table is constructed forces f (m) 6= f (n) whenever m 6= n. Because of this
bijection f : N → Z, we must conclude from Definition 13.1 that |N| = |Z|.
Example 13.2 may seem slightly unsettling. On one hand it makes
sense that |N| = |Z| because N and Z are both infinite, so their cardinalities
are both “infinity.” On the other hand, Z may seem twice as large as
Sets with Equal Cardinalities
219
N because Z has all the negative integers as well as the positive ones.
Definition 13.1 settles the issue. Because the bijection f : N → Z matches
up N with Z, it follows that |N| = |Z|. We summarize this with a theorem.
Theorem 13.1
There exists a bijection f : N → Z. Therefore |N| = |Z|.
The fact that N and Z have the same cardinality might prompt us
compare the cardinalities of other infinite sets. How, for example, do N
and R compare? Let’s turn our attention to this.
In fact, |N| 6= |R|. This was first recognized by Georg Cantor (1845–1918),
who devised an ingenious argument to show that there are no surjective
functions f : N → R. (This in turn implies that there can be no bijections
f : N → R, so |N| 6= |R| by Definition 13.1.)
We now describe Cantor’s argument for why there are no surjections
f : N → R. We will reason informally, rather than writing out an exact proof.
Take any arbitrary function f : N → R. Here’s why f can’t be surjective:
Imagine making a table for f , where values of n in N are in the left-
hand column and the corresponding values f (n) are on the right. The
first few entries might look something as follows. In this table, the real
numbers f (n) are written with all their decimal places trailing off to the
right. Thus, even though f (1) happens to be the real number 0.4, we write
it as 0.40000000 . . . ., etc.
n
f (n)
1
0 . 4 0 0 0 0 0 0 0 0 0 0 0 0 0. . .
2
8 . 5 0 0 6 0 7 0 8 6 6 6 9 0 0. . .
3
7 . 5 0 5 0 0 9 4 0 0 4 4 1 0 1. . .
4
5 . 5 0 7 0 4 0 0 8 0 4 8 0 5 0. . .
5
6 . 9 0 0 2 6 0 0 0 0 0 0 5 0 6. . .
6
6 . 8 2 8 0 9 5 8 2 0 5 0 0 2 0. . .
7
6 . 5 0 5 0 5 5 5 0 6 5 5 8 0 8. . .
8
8 . 7 2 0 8 0 6 4 0 0 0 0 4 4 8. . .
9
0 . 5 5 0 0 0 0 8 8 8 8 0 0 7 7. . .
10
0 . 5 0 0 2 0 7 2 2 0 7 8 0 5 1. . .
11
2 . 9 0 0 0 0 8 8 0 0 0 0 9 0 0. . .
12
6 . 5 0 2 8 0 0 0 8 0 0 9 6 7 1. . .
13
8 . 8 9 0 0 8 0 2 4 0 0 8 0 5 0. . .
14
8 . 5 0 0 0 8 7 4 2 0 8 0 2 2 6. . .
..
.
.
..
220
Cardinality of Sets
There is a diagonal shaded band in the table. For each n ∈ N, this band
covers the nth decimal place of f (n):
The 1st decimal place of f (1) is the 1st entry on the diagonal.
The 2nd decimal place of f (2) is the 2nd entry on the diagonal.
The 3rd decimal place of f (3) is the 3rd entry on the diagonal.
The 4th decimal place of f (4) is the 4th entry on the diagonal, etc.
The diagonal helps us construct a number b ∈ R that is unequal to any f (n).
Just let the nth decimal place of b differ from the nth entry of the diagonal.
Then the nth decimal place of b differs from the nth decimal place of f (n).
In order to be definite, define b to be the positive number less than 1 whose
nth decimal place is 0 if the nth decimal place of f (n) is not 0, and whose
nth decimal place is 1 if the nth decimal place of f (n) equals 0. Thus, for
the function f illustrated in the above table, we have
b = 0.01010001001000...
and b has been defined so that, for any n ∈ N, its nth decimal place is
unequal to the nth decimal place of f (n). Therefore f (n) 6= b for every
natural number n, meaning f is not surjective.
Since this argument applies to any function f : N → R (not just the one
in the above example) we conclude that there exist no bijections f : N → R,
so |N| 6= |R| by Definition 13.1. We summarize this as a theorem.
Theorem 13.2
There exists no bijection f : N → R. Therefore |N| 6= |R|.
This is our first indication of how there are different kinds of infinities.
Both N and R are infinite sets, yet |N| 6= |R|. We will continue to develop
this theme throughout this chapter. The next example shows that the
intervals (0, ∞) and (0, 1) on R have the same cardinality.
P
1
1
f (x)
∞
x
−1
0
Figure 13.1. A bijection f : (0,∞) → (0,1)
Sets with Equal Cardinalities
221
Example 13.3
Show that |(0, ∞)| = |(0, 1)|.
To accomplish this, we need to show that there is a bijection f : (0, ∞) → (0, 1).
We describe this function geometrically. Consider the interval (0, ∞) as the
positive x-axis of R2. Let the interval (0, 1) be on the y-axis as illustrated
in Figure 13.1, so that (0, ∞) and (0, 1) are perpendicular to each other.
The figure also shows a point P = (−1, 1). Define f (x) to be the point on
(0, 1) where the line from P to x ∈ (0,∞) intersects the y-axis. By similar
triangles, we have
1
f (x)
=
,
x + 1
x
and therefore
x
f (x) =
.
x + 1
If it is not clear from the figure that f : (0, ∞) → (0, 1) is bijective, then you
can verify it using the techniques from Section 12.2. (Exercise 16, below.)
It is important to note that equality of cardinalities is an equivalence
relation on sets: it is reflexive, symmetric and transitive. Let us confirm
this. Given a set A, the identity function A → A is a bijection, so |A| = |A|.
(This is the reflexive property.) For the symmetric property, if |A| = |B|,
then there is a bijection f : A → B, and its inverse is a bijection f −1 : B → A,
so |B| = |A|. For transitivity, suppose |A| = |B| and |B| = |C|. Then there
are bijections f : A → B and g : B → C. The composition g ◦ f : A → C is a
bijection (Theorem 12.2), so |A| = |C|.
The transitive property can be useful. If, in trying to show two sets A
and C have the same cardinality, we can produce a third set B for which
|A| = |B| and |B| = |C|, then transitivity assures us that indeed |A| = |C|.
The next example uses this idea.
Example 13.4
Show that |R| = |(0, 1)|.
Because of the bijection g : R → (0, ∞) where g(x) = 2x, we have |R| = |(0, ∞)|.
Also, Example 13.3 shows that |(0, ∞)| = |(0, 1)|. Therefore |R| = |(0, 1)|.
So far in this chapter we have declared that two sets have “the same
cardinality” if there is a bijection between them. They have “different
cardinalities” if there exists no bijection between them. Using this idea,
we showed that |Z| = |N| 6= |R| = |(0, ∞)| = |(0, 1)|. So, we have a means of
determining when two sets have the same or different cardinalities. But
we have neatly avoided saying exactly what cardinality is. For example,
we can say that |Z| = |N|, but what exactly is |Z|, or |N|? What exactly are
these things that are equal? Certainly not numbers, for they are too big.
222
Cardinality of Sets
And saying they are “infinity” is not accurate, because we now know that
there are different types of infinity. So just what kind of mathematical
entity is |Z|? In general, given a set X , exactly what is its cardinality |X |?
This is a lot like asking what a number is. A number, say 5, is an
abstraction, not a physical thing. Early in life we instinctively grouped
together certain sets of things (five apples, five oranges, etc.) and conceived
of 5 as the thing common to all such sets. In a very real sense, the number
5 is an abstraction of the fact that any two of these sets can be matched
up via a bijection. That is, it can be identified with a certain equivalence
class of sets under the " has the same cardinality as" relation. (Recall that
this is an equivalence relation.) This is easy to grasp because our sense of
numeric quantity is so innate. But in exactly the same way we can say
that the cardinality of a set X is what is common to all sets that can be
matched to X via a bijection. This may be harder to grasp, but it is really
no different from the idea of the magnitude of a (finite) number.
In fact, we could be concrete and define |X | to be the equivalence class of
all sets whose cardinality is the same as that of X . This has the advantage
of giving an explicit meaning to |X |. But there is no harm in taking the
intuitive approach and just interpreting the cardinality |X | of a set X to
be a measure the “size” of X . The point of this section is that we have a
means of deciding whether two sets have the same size or different sizes.
Exercises for Section 13.1
A. Show that the two given sets have equal cardinality by describing a bijection
from one to the other. Describe your bijection with a formula (not as a table).
p
1. R
2
and (0, ∞)
6. N and S = ©
: n
n
∈ Nª
p
2. R and ( 2,∞)
7. Z and S = ©..., 1 , 1 , 1 ,1,2,4,8,16,...ª
8 4 2
3. R and (0,1)
8. Z and S = ©x ∈ R : sin x = 1ª
4.
9. ©0, 1ª
The set of even integers and
× N and N
the set of odd integers
10. ©0, 1ª × N and Z
5. A = ©3k : k ∈ Zª and B = ©7k : k ∈ Zª
11. [0, 1] and (0,1)
12. N and Z (Suggestion: use Exercise 18 of Section 12.2.)
13. P(N) and P(Z) (Suggestion: use Exercise 12, above.)
14. N × N
©
and (n, m) ∈ N × N : n ≤ mª
B. Answer the following questions concerning bijections from this section.
15. Find a formula for the bijection f in Example 13.2 (page 218).
16. Verify that the function f in Example 13.3 is a bijection.
Countable and Uncountable Sets
223
13.2 Countable and Uncountable Sets
Let’s summarize the main points from the previous section.
1. |A| = |B| if and only if there exists a bijection A → B.
2. |N| = |Z| because there exists a bijection N → Z.
3. |N| 6= |R| because there exists no bijection N → R.
Thus, even though N, Z and R are all infinite sets, their cardinalities
are not all the same. The sets N and Z have the same cardinality, but
R’s cardinality is different from that of both the other sets. This means
infinite sets can have different sizes. We now make some definitions to
put words and symbols to this phenomenon.
In a certain sense you can count the elements of N; you can count its
elements off as 1, 2, 3, 4, . . ., but you’d have to continue this process forever
to count the whole set. Thus we will call N a countably infinite set, and
the same term is used for any set whose cardinality equals that of N.
Definition 13.2
Suppose A is a set. Then A is countably infinite if
|N| = |A|, that is, if there exists a bijection N → A. The set A is uncountable
if A is infinite and |N| 6= |A|, that is, if A is infinite and there exists no
bijection N → A.
Thus Z is countably infinite but R is uncountable. This section deals
mainly with countably infinite sets. Uncountable sets are treated later.
If A is countably infinite, then |N| = |A|, so there is a bijection f : N → A.
You can think of f as “counting” the elements of A. The first element of A
is f (1), followed by f (2), then f (3) and so on. It makes sense to think of a
countably infinite set as the smallest type of infinite set, because if the
counting process stopped, the set would be finite, not infinite; a countably
infinite set has the fewest elements that a set can have and still be infinite.
It is common to reserve the special symbol ℵ0 to stand for the cardinality
of countably infinite sets.
Definition 13.3
The cardinality of the natural numbers is denoted as ℵ0.
That is, |N| = ℵ0. Thus any countably infinite set has cardinality ℵ0.
(The symbol ℵ is the first letter in the Hebrew alphabet, and is pronounced
“aleph.” The symbol ℵ0 is pronounced “aleph naught.”) The summary of
facts at the beginning of this section shows |Z| = ℵ0 and |R| 6= ℵ0.
Example 13.5
Let E = ©2k : k ∈ Zª be the set of even integers. The function
f : Z → E defined as f (n) = 2n is easily seen to be a bijection, so we have
|Z| = |E|. Thus, as |N| = |Z| = |E|, the set E is countably infinite and |E| = ℵ0.
224
Cardinality of Sets
Here is a significant
fact: The elements of any countably infinite set A
can be written in an infinitely long list a1, a2, a3, a4, . . . that begins with some
element a1 ∈ A and includes every element of A. For example, the set E in
the above example can be written in list form as 0, 2, −2, 4, −4, 6, −6, 8, −8, . . .
The reason that this can be done is as follows. Since A is countably infinite,
Definition 13.2 says there is a bijection f : N → A. This allows us to list
out the set A as an infinite list f (1), f (2), f (3), f (4), . . . Conversely, if the
elements of A can be written in list form as a1, a2, a3, . . ., then the function
f : N → A defined as f (n) = an is a bijection, so A is countably infinite. We
summarize this as follows.
Theorem 13.3
A set A is countably infinite if and only if its elements
can be arranged in an infinite list a1, a2, a3, a4, . . .
As an example of how this theorem might be used, let P denote the set
of all prime numbers. Since we can list its elements as 2, 3, 5, 7, 11, 13, . . ., it
follows that the set P is countably infinite.
As another consequence of Theorem 13.3, note that we can interpret the
fact that the set R is not countably infinite as meaning that it is impossible
to write out all the elements of R in an infinite list. (After all, we tried to
do that in the table on page 219, and failed!)
This raises a question. Is it also impossible to write out all the elements
of Q in an infinite list? In other words, is the set Q of rational numbers
countably infinite or uncountable? If you start plotting the rational num-
bers on the number line, they seem to mostly fill up R. Sure, some numbers
p
such as
2, π and e will not be plotted, but the dots representing rational
numbers seem to predominate. We might thus expect Q to be uncountable.
However, it is a surprising fact that Q is countable. The proof presented
below arranges all the rational numbers in an infinitely long list.
Theorem 13.4
The set Q of rational numbers is countably infinite.
Proof. To prove this, we just need to show how to write the set Q in list
form. Begin by arranging all rational numbers in an infinite array. This is
done by making the following chart. The top row has a list of all integers,
beginning with 0, then alternating signs as they increase. Each column
headed by an integer k contains all the fractions (in reduced form) with
numerator k. For example, the column headed by 2 contains the fractions
2 , 2 , 2 , 2 ,...
2
2
2
1 3 5 7
, and so on. It does not contain 2 , 4 , 6 , etc., because those are
Book of Proof Page 31
