# Countability of the set of functions $J_n\to \mathbb N$ [duplicate]

Let $J_n=\{1,\dots,n\}$. How do I show that the set of all functions $J_n\to \mathbb N$ is countable? Any function is given by specifying the images of $1,\dots,n$. There are $|\mathbb N|$ options for the image of each $i=1, \dots, n$. So intuitively, the set of such functions is the union of $n$ copies of $\mathbb N$, hence countable. But how to formalize it?

• It might help to consider a simple case first: what if $n=2$? Do you see a way to "code" a (ordered) pair of natural numbers as a single natural number? – Noah Schweber Aug 26 '18 at 19:06

It's not the union, it's the Cartesian product.

• How can one see this? I only can see that a particular function is (by definition) a subset of $J_n\times\mathbb N$. – user531587 Aug 26 '18 at 19:10
• @user531587 Yes, and that's a Cartesian product (really, you should think of it as $\mathbb{N}\times...\times\mathbb{N}$ ($n$ times)). – Noah Schweber Aug 26 '18 at 19:13
• @NoahSchweber But the Cartesian product $J_n\times \mathbb N$ is just the definition of a single function. I need to account for all functions somehow, but I don't know how to do that. (And I'm not sure where did you get $\mathbb N^n$ from.) – user531587 Aug 26 '18 at 19:17
• @user531587 Each function $f:J_n\to \mathbb N$ assigns to element of $\{1,\ldots,n\}$ a natural number. So such a function could be given by $f(1)=42,$ $f(2)=120, \ldots, f(n) = 99,$ or something like this. We can correspond this to the ordered pair $(42,120,\ldots,99) \in \mathbb N^n,$ the $n$-fold cartesian product of $\mathbb N.$ – spaceisdarkgreen Aug 26 '18 at 19:19
• @spaceisdarkgreen Oh, I see, so there is a bijection between the set of functions I described and the set $\mathbb N^n$. And since finite Cartesian products of countable sets are countable, the result follows. – user531587 Aug 26 '18 at 19:21

Let $\mathcal{J_k} = \{f : J_k \to \mathbb{N} \}$ be the set of functions from $J_k$ to $\mathbb{N}$. Now, the mapping

\begin{align} & \mathcal{J_k} \ \longrightarrow \ \mathbb{N}^k \\ & \quad f \mapsto (f(1), \dots, f(k) ) \end{align}

is bijective, so it suffices to show that $\mathbb{N}^k$ is countable. Take distinct primes $p_1, \dots, p_k$ and consider the function

$$\Gamma: \mathbb{N^k} \to \mathbb{N} \\ (n_1, \dots, n_k) \mapsto p_1^{n_1}\cdots p_k^{n_k}$$

By the fundamental theorem of arithmetic, $\Gamma$ is injective, and so $|\mathbb{N}^k| \leq |\mathbb{N}| = \aleph_0$ as desired.

If you want to have an explicit injection, you can compose both mappings, i.e. you can take the function $f \mapsto p_1^{f(1)}\cdots p_k^{f(k)}$.

Each function is given by a $n$-tuple $(f_1, \dotsc, f_n) \in \mathbb{N}^n$ of natural numbers, where $f_i = f(i)$.

You can use the Cantor pairing function, $$\pi(x, y) := y + \sum_{i=0}^{x+y} i = y+\frac{1}{2} (x + y) (x + y + 1)$$ which is a bijection between $\mathbb{N}$ and $\mathbb{N}^2$, iteratively to encode an $n$-tuple to a natural number.

E.g.

• $\langle f_1, f_2 \rangle = \pi(f_1, f_2)$
• $\langle f_1, f_2, f_3 \rangle = \langle f_1, \langle f_2, f_3 \rangle \rangle$
• $\langle f_1, f_2, f_3, f_4 \rangle = \langle f_1, \langle f_2, f_3, f_4 \rangle \rangle = \langle f_1, \langle f_2, \langle f_3, f_4 \rangle \rangle\rangle$

and so on. This is called a Cantor tuple function.