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

Prove that $\mathbb{N}^k$ is countable for every $k \in \mathbb{N}$.

Let $P(n)$ be the statement: “$\mathbb{N}^n$ is countable” $\forall n \in \mathbb{N}$.

Base Case: $\mathbb{N}^1 = \mathbb{N}$ is countable by definition, so $\checkmark$

Inductive Step: $\mathbb{N}^{k+1}$ $“=”$ $\mathbb{N}^k \times \mathbb{N}$

We know that $(A,B)$ countable $\implies$ $A \times B$ is countable. I am stuck on the part where I have to prove the rest, but I know that, for example, $(1,2,7) \in \mathbb{N}^3 \notin \mathbb{N}^2 \times \mathbb{N}$ but instead $((1,2),7) \in \mathbb{N}^2 \times \mathbb{N}$. So how would I go about proving the statement.

-
What have you tried? –  tomcuchta Dec 15 '11 at 3:34
-1: you asked this two months ago... –  t.b. Dec 15 '11 at 7:31
I don't think that this is a duplicate, I think that the question here is essentially about the induction step. It is a valid question which I got asked plenty of times by my own students when asked about it. –  Asaf Karagila Dec 15 '11 at 7:55
@tb OP obviously knows that product of two countable sets is countable -it's mentioned in his attempted proof. From the formulation of the questions it seems to me, that his problem is to see that $\mathbb N^k\times\mathbb N$ and $\mathbb N^{k+1}$ is the same thing (as far as the cardinality is concerned.) I agree that the OP might have explained more clearly what he is asking, but I do not think that it should be closed as a duplicate. –  Martin Sleziak Dec 15 '11 at 7:56
I am voting to reopen this question. –  Asaf Karagila Dec 15 '11 at 11:50

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

-

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.

-
If $\mathbb{N}$ includes $0$, as is usual in set theory, then your map $g$ is not injective, since you cannot tell if there are trailing $0$s on the sequence or not. You can fix this either by also encoding $k$ itself, or by adding $1$ to each exponent, or by including $p_{k+1}^1$ at the end as an end-marker or probably also in other ways. –  JDH Dec 15 '11 at 11:41
@JDH I personally don't include $0$ in $\mathbb{N}$, and I think it's fairly clear that adding in $0$ doesn't really change the cardinality, so that there is really no need to adjust. –  Alex Youcis Dec 16 '11 at 5:10

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.

-

Hint: For your inductive step, you have assumed there is a bijection between $\mathbb{N}^k$ and $\mathbb{N}$. You now want to prove that there is a bijection between $\mathbb{N}^{k+1}$ and $\mathbb{N}$. So if you use the bijection you have on the first $k$ components of $\mathbb{N}^{k+1}$ what do you have?

-