Proof of Natural set to any power k, is countably infinite

Question

Show that $N^k = N × N × \cdots × N$ ($k$ factors) is countably infinite for every positive integer $k$.

where $N$ is the set of natural numbers.

I first approached this question by trying induction. $N\times N$ would be the base case. However, the problem arised when I tried to show $N \times N= N \times N \times N$.

Answer 1

Hint: $\Bbb{N} \times \Bbb{N} \times \Bbb{N} \cong (\Bbb{N} \times \Bbb{N}) \times \Bbb{N}$ or in other words, $(a,b,c) \cong ((a,b),c)$

Answer 2

You're right to try induction - if you can show $\mathbb{N}^2$ is countable, then $$\mathbb{N}^3=\mathbb{N}\times\mathbb{N}^2\cong\mathbb{N}\times\mathbb{N}=\mathbb{N}^2\cong\mathbb{N},$$ and so on for higher powers.

So how do you prove the base case - that is, $\mathbb{N}\cong\mathbb{N}^2$? HINT: Draw a picture of $\mathbb{N}^2$, and start labelling the elements 1, 2, 3, . . . Can you find a way to do this?

Answer 3

You can use this: Let $p_1,..,p_n$ be the first $n$ primes, and let $(a_1,a_2,..,a_n)$ be an $n$-ple in $\mathbb N^n$. Then map $$(a_1,a_2,...,a_n)\rightarrow p_1^{a_1}p_2^{a_2}....p_n^{a_n} $$

Which is an injection from $\mathbb N^n$ into $\mathbb N$ , since no two numbers have the same prime factorization and every number has a unique factorization. or $$(a_1,a_2,..,a_n) \rightarrow 0.a_!a_2...a_n 0000... $$ gives you an injection into the Rationals.

Then formally, you can then use Cantor-Schroeder-Bernstein to conclude $|\mathbb N^n|=|N|$

But notice that $|N^{|N|}| \neq |\mathbb N|$ , e.g., consider a decimal expansion $a.a_0a_1,...a_n... $

Answer 4

Let $A$ be an infinite countable set. There is a bijection $f$ between $A$ and $\mathbb{N}$. We can see $f(a)$ as the index of $a$. That means that $A$ can be written as $ A =\{a_1, a_2, a_3,\dots\}$, where $f(a_1) = 1$, $f(a_2)$ = 2 etc.

Let be $B$ be another infinite countable set, hence $B = \{b_1, b_2, b_3,\dots\}$.

Now, what is the bijection $F$ between $A\times B$ and $\mathbb{N}$? You have proven that there is a bijection $g:\mathbb{N}\times\mathbb{N}\to \mathbb{N}$. Again, we can see $g((n_1,n_2))$ as the index of the pair $(n_1, n_2)$. So we can define $F$ as $$F(a_n, b_m) = g(n,m)\text{.}$$

Now, choose $A = \mathbb{N}^{k - 1}$ and $B = \mathbb{N}$.