5.5. Does All This Really Work? 109
(b)An infinite sequence of the decimal digitsf 0 ; 1 ;:::; 9 gwill be calledlongif
it has infinitely many occurrences of some digit other than 0. 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. aHint: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 5.5.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çand
.0;1ç^2. Then appeal to the Schroder-Bernstein Theorem to show that there is actu- ̈
ally a bijection from.0;1çand.0;1ç^2.
(f)Complete the proof that there is a bijection from.0;1çtoŒ0; 1 /^2.Problem 5.13.
LetŒN! f1;2;3gçbe the set of all sequences containing only the numbers 1, 2,
and 3, for example,
.1;1;1;1:::/;
.2;2;2;2:::/;
.3;2;1;3:::/:For any sequence,s, letsŒmçbe itsmth element.
Prove thatŒN!f1;2;3gçis uncountable.
Hint:Suppose there was a list
LDsequence 0 ;sequence 1 ;sequence 2 ;:::of sequences inŒN!f1;2;3gçand show that there is a “diagonal” sequence diag 2
ŒN!f1;2;3gçthat does not appear in the list. Namely,
diagWWDr.sequence 0 Œ0ç/;r.sequence 1 Œ1ç/;r.sequence 2 Œ2ç/;:::;whererWf1;2;3g!f1;2;3gis some function such thatr.i/¤iforiD1;2;3.