Mathematics for Computer Science

Chapter 7 Infinite Sets224

Problem 7.2.
Show that the setf0;1gof finite binary strings is countable.

Problem 7.3.
Describe an example of twouncountable setsAandBsuch that there is no bijec-
tion betweenAandB.

Problem 7.4.
Prove that if there is a total injective (Œ 1 out; 1 inç) relation fromS!N, then
Sis countable.

Problem 7.5.
For each of the following sets, indicate whether it is finite, countably infinite, or
uncountable.

1. The set of solutions to the equationx^3 xD0:1.


2. The set of natural numbersN.


3. The set of rational numbersQ.


4. The set of real numbersR.


5. The set of integersZ.


6. The set of complex numbersC.


7. The set of words in the English language no more than 20 characters long.


8. The powerset of the set of all possible bijections fromf1;2;:::;10gto itself.


9. An infinite setSwith the property that there exists a total surjective function
   f WN!S.


10. A setA[BwhereAis countable andBis uncountable.

Problem 7.6.
Circlethe correct completions (there may be more than one)
AstrictNIFF...