Let S = {0, 1}.

(a) Let F1 be the set of all functions f : S ! IN.

For example, the function f that has f(0) = 92873 and f(1) = 908 is one element of

F1.

Is F1 countable? Prove your answer is correct.

(b) Let F2 be the set of all functions f : IN ! S.

For example, the function f defined by f(n) = n mod 2 for all n 2 IN is one element

of F2.

Is F2 countable? Prove your answer is correct.