Mathematics for Computer Science

Chapter 7 Infinite Sets212

More Countable and Uncountable Sets

Once we have a few sets we know are countable or uncountable, we can get lots
more examples using Lemma 7.1.3. In particular, we can appeal to the following
immediate corollary of the Lemma:

Corollary 7.1.14.

(a) IfUis an uncountable set andAsurjU, thenAis uncountable.

(b) IfCis a countable set andCsurjA, thenAis countable.

For example, now that we know that the setf0;1g!of infinite bit strings is un-
countable, it’s a small step to conclude that

Corollary 7.1.15.The setRof real numbers is uncountable.

To prove this, think about the infinite decimal expansion of a real number:

p

2 D1:4142:::;

5 D5:000:::;

1=10D0:1000:::;

1=3D0:333:::;

1=9D0:111:::;

4

1

99

D4:010101::::

Let’s map any real numberrto the infinite bit stringb.r/equal to the sequence
of bits in the decimal expansion ofr, starting at the decimal point. If the decimal
expansion ofrhappens to contain a digit other than 0 or 1, leaveb.r/undefined.
For example,

b.5/D000:::;

b.1=10/D1000:::;

b.1=9/D111:::;

b.4

1

99

/D010101:::

b.

p

2/;b.1=3/are undefined: