Countability of the set of functions $J_n\to \mathbb N$ 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?
 A: It's not the union, it's the Cartesian product.
A: 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)}$.
A: 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.
