Mathematics for Computer Science

Chapter 5 Infinite Sets106

thef-arrows define a bijection between theAandBelements on the path, or

theg-arrows define a bijection betweenBandAelements on the path, or

both sets of arrows define bijections.

For which kinds of paths do both sets of arrows define bijections?

(e)Explain how to piece these bijections together to prove thatAandBare the
same size.

Homework Problems

Problem 5.7.
Prove that ifAis an infinite set andCis a countable set, then

AbijA[C:

Hint:See Problem 5.3.

Exam Problems

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

nD 0

An

Problem 5.9.
Let A and B denote two 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.

Problems for Section 5.3

Problem 5.10.
There are lots of different sizes of infinite sets. For example, starting with the
infinite set,N, of nonnegative integers, we can build the infinite sequence of sets

NstrictP.N/strictP.P.N//strictP.P.P.N///strict::::