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

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?

• Can you post a little more about the question? If the question says you should deduce that the set of all functions from $\{0,1\}$ and $\mathbb N$ is countably finite, there is probably something thay you already proved before this... – 5xum Jan 7 '15 at 13:20
• Yeah sure I did mention that in the post! It asked me to show that NxN was countably infinite which I have done (or at least I think I have) – Andrew Phillip Jacobson Jan 7 '15 at 13:21
• I see. The way your question stands now, it could be understood that you did not yet prove that $\mathbb N\times\mathbb N$ is countably infinite, and that the problem you have will eventually lead to you proving that. – 5xum Jan 7 '15 at 13:23

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$?

• Well I see that every N can be assigned to either one or both of 0 or 1. e.g. (5)--->0 (6)----->0 (127)---->1 for example so we can lay it out like (0,5)(6,0)(127,1) and so on for every N but I still don't understand sorry :( – Andrew Phillip Jacobson Jan 7 '15 at 13:30

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?

• well I would simply need to show that the domain of g is N and I would be done considering I have already shown NxN is countably infinite. But I'm unsure how to go about this. – Andrew Phillip Jacobson Jan 7 '15 at 13:32
• You could construct an inverse function for $g$ to show that it's a bijection, or just explicitly prove that it's a injection and surjection: Let $a, b \in \mathcal{F}$. Now, if $a \neq b$, it means that there exists $n \in \{0,1\}$ s.t. $a(n) \neq b(n)$. This implies $g(a) \neq g(b)$. So $g$ is an injection. Now take $n = (n_1, n_2) \in \Bbb{N} \times \Bbb{N}$. Consider the function $f: \{0, 1\} \to \Bbb{N} \times \Bbb{N}$, $f(0) = n_1$, $f(1) = n_2$. Now $f \in \mathcal{F}$ and $g(f) = n$, so $g$ is a surjection. – desos Jan 7 '15 at 13:52