Discrete Mathematics - Mathematics 210 - Fall 2010

(I don't know yet which of the following problems will be graded by our grader.)

1. Let S be the set of all words of infinite length that only use the letters a and b (e.g., aabaabaabaab... is such a word). Use a diagonalization argument to show S is uncountable.
2. Prove that the set of all rational numbers is countable by appropriately modifying the proof given in Example 20 (p. 159).
3. Let S be the set of all words of finite length that only use the letters a and b (e.g., abb, and bbbbab are such words). Prove S is countable by using a "listing method" as in Example 20 (p. 159).
4. What is wrong with the following "proof" that the set Z of all integers is uncountable? Indicate exactly which step(s) is(are) wrong, and why.
   1. Suppose, toward contradiction, that Z is countable.
   2. Then, since Z is not finite, it must be denumerable, by definition of "countable".
   3. So there is a bijection f : N --> Z, by definition of "denumerable".
   4. For all i in N, let x_i = f(i).  (x_i is "x sub i")
   5. Let y be the natural number whose ith digit from the right is 1+ the ith digit of x_i from the right, except that if the ith digit of x_i is 9, we choose 8 for the ith digit of y.
   6. Then y is different from x_i since they differ in at least one digit, namely in their ith digits.
   7. So y is not equal to any of the numbers x_i.
   8. So y is not in the range of f.
   9. So f is not onto.
   10. But this contradicts step iii.
   11. So Z is uncountable.
5. True or false: if S and T are denumerable sets, then there exists a bijection from S to T. Prove your answer.
6. True or false: if S is a countable set and T is an uncountable set, then there exists no bijection from S to T. Prove your answer.