What about this thread?
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.
p.s. ! means arrow to
What about this thread?
(a) There is a one-to-one correspondence between the set of functions from S to and the set of pairs of natural numbers . Now, it is a standard result that there is a one-to-one correspondence between and : see Cantor pairing function, this proof, and this proof that the set of rational numbers is countable.
(b) It is an equally standard result that this set is uncountable: see, for example, Cantor diagonal argument.