[3 ] (14 pts.) Countable vs. Uncountable a. (4 pts.) Prove that Z20 is countable by constructing a bijection f : Z20 N. Hint: When we say "construct a blah." it never suffices to just define the blah. You have to also prove that the thing is a blah. In this case, don't just define f. Also show that f is a well-defined function (it maps every element a e A to some be B), . f is onto, and . / is one-to-one (using the contrapositive of the definition as we did in Lectures 5 & 6). Even when we don't say "and prove f is a bijection" this should be considered implicit in the word "construct." b. (8 pta.) Suppose you have an infinite grid labelled by the integer pairs (r, y) where z. y c Z. Consider any path that starts at the origin (0.0) and on each step either moves one unit left (L), right (R). up (U), down (D), or stops. For example, the diagram on the left shows 14 different paths from (0, 0) to (4, 4). The diagram on the right shows an infinite spiral that starts as R. U. L. L. D. D. .. .. Prove that B = set of all such paths is uncountable infinite by using a diagonalization argu- ment similar to that in Lecture 6 and Tutorial 3. c. (2 pis.) Suppose you tried to use the same diagonalization argument from b. but on set A C B of paths that must stop at some point. So in our diagrams above, the infinite spiral path on the right would no longer be part of A, while all the path on the left would still be in A. Point out the precise place in your proof that no longer holds in b. but allowed you to continue your proof in b. Explain why it no longer holds