Chapter 7 Infinite Sets230
(b)Prove that ifC is a countable set andDis infinite, then there is a bijection
betweenDandC[D.
Problem 7.18.
Letf0;1gbe the set of finite binary sequences,f0;1g!be the set of infinite
binary sequences, andF be the set of sequences inf0;1g!that contain only a
finite number of occurrences of 1 ’s.
(a)Describe a simple surjective function fromf0;1gtoF.(b)The setFWWDf0;1g! Fconsists of all the infinite binary sequences with
infinitelymany 1 ’s. Use the previous problem part to prove thatFis uncountable.
Hint:We know thatf0;1gis countable andf0;1g!is not.
Problem 7.19.
Letf0;1g!be the set of infinite binary strings, and letB f0;1g!be the set of
infinite binary strings containing infinitely many occurrences of 1’s. Prove thatB
is uncountable. (We have already shown thatf0;1g!is uncountable.)
Hint:Define a suitable function fromf0;1g!toB.
Problem 7.20.
A real number is calledquadraticwhen it is a root of a degree two polynomial with
integer coefficients. Explain why there are only countably many quadratic reals.
Problem 7.21.
Describe which of the following sets have bijections between them:
Z(integers); R(real numbers);
C(complex numbers); Q(rational numbers);
pow.Z/(all subsets of integers); pow.;/;
pow.pow.;//; f0;1g(finite binary sequences);
f0;1g!(infinite binary sequences) fT;Fg(truth values)
pow.fT;Fg/; pow.f0;1g!/