# Math Help - countability of languages

1. ## countability of languages

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.

(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.

p.s. ! means arrow to

4. (a) There is a one-to-one correspondence between the set of functions from S to $\mathbb{N}$ and the set of pairs of natural numbers $\mathbb{N}\times\mathbb{N}$. Now, it is a standard result that there is a one-to-one correspondence between $\mathbb{N}\times\mathbb{N}$ and $\mathbb{N}$: see Cantor pairing function, this proof, and this proof that the set of rational numbers is countable.