Mathematics for Computer Science

7.4. Does All This Really Work? 229

is one that has infinitely many occurrences of nonzero digits. LetLbe the set of
all such long sequences. Describe a bijection fromLto the half-open real interval
.0;1ç.

Hint:Put a decimal point at the beginning of the sequence.

(c)Describe a surjective function fromLtoL^2 that involves alternating digits
from two long sequences.Hint:The surjection need not be total.

(d)Prove the following lemma and use it to conclude that there is a bijection from
L^2 to.0;1ç^2.
Lemma 7.4.1.LetAandBbe nonempty sets. If there is a bijection fromAtoB,
then there is also a bijection fromAAtoBB.

(e)Conclude from the previous parts that there is a surjection from.0;1çto.0;1ç^2.
Then appeal to the Schroder-Bernstein Theorem to show that there is actually a ̈
bijection from.0;1çto.0;1ç^2.

(f)Complete the proof that there is a bijection from.0;1çtoŒ0; 1 /^2.

Exam Problems

Problem 7.15.
Prove that ifA 0 ;A 1 ;:::;An;:::is an infinite sequence of countable sets, then so
is 1
[

nD 0

An

Problem 7.16.
LetAandBbe countably infinite sets:

ADfa 0 ;a 1 ;a 2 ;a 3 ;:::g

BDfb 0 ;b 1 ;b 2 ;b 3 ;:::g

Show that their product,AB, is also a countable set by showing how to list
the elements ofAB. You need only show enough of the initial terms in your
sequence to make the pattern clear—a half dozen or so terms usually suffice.

Problem 7.17. (a)Prove that ifAandBare countable sets, then so isA[B.