Let $X$ be a finite set. Show that $\mathbb{N}^X$={$f : X → \mathbb{N}$} is countably infinite.

Question

My approach is to show that $\mathbb{N} → \mathbb{N}^X$ is a bijection, which is the definition of countably infinite. But I feel like I'm not getting anywhere along this path. Any help?

Answer 1

I assume that you want to prove there is a bijection between $\mathbb{N}$ and $\mathbb{N}^n$. We will prove it by induction to $n$. The way to prove the case $n=2$ is well-known: for example, we may consider the Cantor's pairing function: $$f(n,m) = (1+2+3+\cdots + (n+m)) + m.$$ Finding the bijection is easier if you know the Cantor-Bernstein-Schroeder theorem; for example, take $f(n,m) = 2^n3^m$ and $g(m) = (m,0)$ gives injection from one to another.

Now assume that we have a bijection $f_n: \mathbb{N}^n\to \mathbb{N}$ for $n\ge 2$. Then we can define $f_{n+1}:\mathbb{N}^{n+1}\to\mathbb{N}$ as $$f_{n+1}(a_1,\cdots,a_n,a_{n+1}) = f_2(f_n(a_1,\cdots,a_n),a_{n+1}).$$

You can check that $f{n+1}$ is really bijection. I will leave you checking details as your own.