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

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

• How would the function be surjective? – Young Padawan Jul 20 '15 at 17:51
• Is it slightly clearer now? – Asaf Karagila Jul 20 '15 at 18:47

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.

• Is this true if K is equal to infinity?????? – sani Apr 3 '17 at 16:08

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

The function $f:\mathbb{N^K}\to \mathbb{N^K\times \{m \}}$ defined by $$f(a_1,a_2,\cdots, a_k)=(a_1,a_2,\cdots, a_k,m)$$ is clearly a bijection for fixed $m\in \mathbb{N}$ and we can write $\mathbb{N^{K+1}}$ as $$\mathbb{N^{K+1}}=\bigcup_{m=1}^{\infty}\{\mathbb{N^K\times \{m \}}\}$$ and this being a countable union of countable sets is countable.

• Is this true if K is equal to infinity?????? – sani Apr 3 '17 at 16:08
• @sani No. In fact, the set of sequences with entries $o$ or $1$ is not countable. – Arun Apr 10 '17 at 9:35