Proving $\mathbb{N}^k$ is countable

Solution 1:

When you want to prove something about cardinalities you actually say "I don't really care who is in the set, I just care about its size".

This means that you don't really care that $(1,2,3)\notin\mathbb N^2\times\mathbb N$, because once you proved that $\mathbb N^2\times\mathbb N$ is countable you have a natural bijection: $$\left(\left(x,y\right),z\right)\mapsto\left(x,y,z\right)$$ This function is clearly bijective, and while you cannot write "clearly" in a homework assignment - it is not hard to prove that for yourself as well. Every $(n+1)$-tuple is just an $n$-tuple with an additional element.

Alternatively, you can use the fact that $\mathbb N\times\mathbb N$ is countable as well and just "skip" the above part, by doing it implicitly as follows:

So now the induction step would be to take $f_n\colon\mathbb N^n\to\mathbb N$ which is a bijection, define $g\colon\mathbb N^{n+1}\to\mathbb N\times\mathbb N$ as follows:

$$g((a_1,\ldots,a_{n+1})) = (f_n(a_1,\ldots,a_n),a_{n+1})$$

This function is injective since two different tuples will either have a different coordinate $k\le n$ in which case the $f_n$ part would be different by injectivity of $f_n$; or different coordinate at the $n+1$ place, in which case the right coordinate of the image will be different.

It is also surjective due to a similar argument. And then $f_{n+1}$ is the composition of $g$ with a fixed bijection from $\mathbb N\times\mathbb N$ to $\mathbb N$.

Solution 2:

Hint:

It is enough to prove that $A \times B$ is countable whenever $A$ and $B$ are countable. To do this, write

$$ A = \{a_0,a_1,a_2, \dots\} $$ and $$ B = \{b_0,b_1,b_2,\dots\}. $$ To find a bijection, consider the map

$$\begin{align} 0 \mapsto (a_0,b_0) \\ 1 \mapsto (a_1,b_0) \\ 2 \mapsto (a_0,b_1) \\ 3 \mapsto (a_2,b_0) \\ 4 \mapsto (a_1,b_1) \\ 5 \mapsto (a_0,b_2) \\ 6 \mapsto (a_0,b_3) \\ 7 \mapsto (a_1,b_2) \\ \vdots \qquad\quad \end{align}$$ and show this map is a bijection. This map is "natural" in the sense that if you draw out the set of ordered pairs of nonnegative integers, this map follows a logical path. It is called the Cantor pairing function and it can be described visually.

Now to see that the previous statement is enough to prove what you want, use induction.

Solution 3:

Define $f:\mathbb{N}\to\mathbb{N}^k$ by just the inclusion into the first coordinate, this is clearly an injection. Define $g:\mathbb{N}^k\to\mathbb{N}:(a_1,\cdots,a_k)\mapsto p_1^{a_1}\cdots p_k^{a_k}$ where $p_i$ is the $i^{\text{th}}$ prime. This is an injection by the fundamental theorem of arithmetic. The rest follows by the Schroeder-Bernstein theorem.