150 Chapter 13

mathematical arguments, as I am doing here, and some mathematicians study what set the-

ory can be like without the axiom of choice. In those theories, one cannot say as a general

principle that the countable union of countable sets is countable. Meanwhile, in ordinary

mathematical arguments it is perfectly acceptable to use the axiom of choice whenever it

is convenient, and this axiom is considered to be one of the standard fundamental axioms

of set theory.

We may also generalize theorem 108 in the following way.

Theorem 111. If A is any countable set, then the set A

∗

consisting of all finite sequences

from A is also countable.

Proof. Since A is bijective with a subset of N, which is bijective with the positive integers

N

+

, it suffices for us to prove that (N

+

)

∗

, the set of finite sequences of positive natural

numbers, is countable. Let us associate to any finite sequence s = s

0

s

1

s

2

···s

n

of positive

integers the number 2

s

0

3

s

1

5

s

2

···p

s

n

n

, obtained by placing exponent s

i

on the ith prime p

i

.

This association maps (N

+

)

∗

into N, and the map is one-to-one because of the uniqueness

of the prime factorization of numbers. From any number, we can extract the sequence of

exponents from its prime factorization.

13.3 Uncountability of the real numbers

Let us come now to Cantor’s theorem, shocking and profound, showing that the set of real

numbers is uncountable. There are different sizes of infinity! Although Cantor’s ideas

were controversial in his day, sometimes meeting with stubborn rejection, mathematicians

eventually recognized his enormous accomplishment. In 1925, Hilbert extolled Cantor’s

theory of sets and infinite cardinals, announcing, “No one shall cast us from the paradise

that Cantor has created for us.” Let us see what Hilbert was talking about.

Theorem 112 (Cantor). The set of real numbers R is uncountable. It cannot be put into

one-to-one correspondence with the natural numbers N, and therefore the size of R is a

higher-order infinity than that of N.

Proof. Suppose toward contradiction that R is a countable set, so we can enumerate all the

elements of R as r

1

, r

2

, r

3

, and so on, with r

n

for every natural number n ≥ 1. Every real

number appears as some r

n

on this list. Using the list, we shall now describe a particular

real number z, by specifying its decimal digits

z = 0.d

1

d

2

d

3

···

Specifically, we fix a decimal representation for each of the real numbers r

n

, and we let

d

n

= 1, unless the nth digit of r

n

is 1, in which case we set d

n

= 7. We have now completely

specified the real number z. The main point is that we made the nth digit of z different from

the nth digit of r

n

. (Note that because the digits of z are all either 1 or 7, it has a unique