Showing the set of functions $\{0, 1\} \to \mathbb{N}$ is countably infinite.

Question

I'm doing a question it asked me to show that $\mathbb{N} \times \mathbb{N}$ was countably infinite but I am stuck on the following part of the question:

deduce that the set of all functions $f : \{0, 1\} \to \mathbb{N}$ is countably infinite.

I don't really get what this question is asking at all.

Any help?

Answer 1

A function $f:\{0,1\}\to\Bbb N$ can be understood as an assignment. You assign a natural number to $0$ and another natural number (not necessarily different) to $1$.

Now, you have to show that the set of all such assignments is countably infinite, just like $\Bbb N\times\Bbb N$.

Can you identify each assignment to a different element of $\Bbb N\times \Bbb N$?

Answer 2

Define $$ \mathcal{F} = \{f \mid f \text{ is a function } \{0,1\} \to \Bbb{N} \}. $$ Now let $f \in \mathcal{F}$. Now we have $f(0) = n_0 \in \Bbb{N}$ and $f(1) = n_1 \in \Bbb{N}$. Consider the function $$ g: \mathcal{F} \to \Bbb{N} \times \Bbb{N}, \quad g(f) = (f(0), f(1)) $$

Now, can you show that $g$ is a bijection?