Chapter 7 Infinite Sets228
(d)Show that for each type of path, eitherthef-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.
Problem 7.12. (a)Prove that if a nonempty set,C, is countable, then there is a
totalsurjective functionfWN!C.
(b)Conversely, suppose thatNsurj D, that is, there is a not necessarily total
surjective functionf WND. Prove thatDis countable.
Homework Problems
Problem 7.13.
Prove that ifAis an infinite set andBis a countably infinite set that has no elements
in common withA, then
Abij.A[B/:
Reminder: You may assume any of the results from class, MITx, or the text as long
as you state them explicitly.
Problem 7.14.
In this problem you will prove a fact that may surprise you—or make you even
more convinced that set theory is nonsense: the half-open unit interval is actually
the “same size” as the nonnegative quadrant of the real plane!^6 Namely, there is a
bijection from.0;1çtoŒ0; 1 /Œ0; 1 /.
(a)Describe a bijection from.0;1çtoŒ0; 1 /.Hint:1=xalmost works.
(b)An infinite sequence of the decimal digitsf 0 ; 1 ;:::; 9 gwill be calledlongif
it does not end with all 0’s. An equivalent way to say this is that a long sequence
(^6) The half-open unit interval,.0;1ç, isfr 2 Rj0 < r 1 g. Similarly,Œ0; 1 /WWDfr 2 Rjr 0 g.