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?

  • $\begingroup$ 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... $\endgroup$ – 5xum Jan 7 '15 at 13:20
  • 1
    $\begingroup$ 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) $\endgroup$ – Andrew Phillip Jacobson Jan 7 '15 at 13:21
  • $\begingroup$ 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. $\endgroup$ – 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$?

  • $\begingroup$ 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 :( $\endgroup$ – 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?

  • $\begingroup$ 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. $\endgroup$ – Andrew Phillip Jacobson Jan 7 '15 at 13:32
  • $\begingroup$ 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. $\endgroup$ – desos Jan 7 '15 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.