Prove that the cardinality of $\mathbb{N}^{\mathbb{N}_2}$ countable.

Question

Since $\mathbb{N}_2 = \{1,2\}$ and the cardinality of $\{1,2\}$ is $2$. I assume you can re-express this as $|\mathbb{N}|^{2}$. The part where I'm stuck on is understanding what $|\mathbb{N}|^{2}$ actually means.

Answer 1

$\mathbb N^{\mathbb N_2}$ is the set of all functions $\mathbb N_2\to \mathbb N,$ so you want to find a bijection between that set and the natural numbers. One very important thing to observe is that, for any sets $A$ and $B,$ $|A^B|$ only depends on the cardinality of $A$ and $B,$ not on anything else about those two sets, so we can view exponentiation as an operation on cardinalities, defined like $|A|^{|B|} =|A^B|.$

So in this sense, all you are doing is rewriting: $|\mathbb N^{\mathbb N_2}|=|\mathbb N|^{|\mathbb N_2|}=|\mathbb N|^2.$ Computing the right-hand-side just means computing the left-hand side, so there's no progress and the task is still just to find a bijection between $\mathbb N^{\mathbb N_2}$ and $\mathbb N.$

But on the other hand, the notation suggests another interpretation in which $|\mathbb N|^2$ means the same thing as $|\mathbb N|\cdot |\mathbb N|.$ The definition of this is that $|\mathbb N|\cdot |\mathbb N| = |\mathbb N\times \mathbb N|$ where $\mathbb N\times \mathbb N$ is the set of ordered pairs of natural numbers. This alternative interpretation is completely justified, since there is a very simple and natural bijection between $\mathbb N^{\mathbb N_2}$ and $\mathbb N\times \mathbb N$ (a function $f:\mathbb N_2\to \mathbb N$ corresponds to the ordered pair $(f(1), f(2))$). Thus, if you can find a bijection between $\mathbb N\times \mathbb N$ and $\mathbb N,$ then this gives a bijection $\mathbb N^{\mathbb N_2}$ to $\mathbb N.$