Is there a way to give an injective function from the set of all finite natural sequences to $\mathbb{N}$, without relying on prime numbers? I'm trying to prove that $|\bigcup_{k\in\mathbb{N}}\mathbb{N}^k|=|\mathbb{N}|$. I have an idea, but in order for it to work, I must define, rather conviniently, a function $$G\colon\bigcup_{k\in\mathbb{N}}\mathbb{N}^k\to\mathbb{N}$$
that, according to what I have found is needed, must be injective among (probably) other things. The problem here is that for as long as I've been trying, nothing comes to my mind as to how to do it without relying on prime numbers.
That said, I'd like to know if it is even possible to define an injective (let alone all the other properties that I surely need) function without the use of prime numbers. 
Please note that I'm not looking for a full answer, maybe just a hint if it is actually the case.
Thanks in advance.
 A: Contrary to my usual practice, I’ll interpret $\Bbb N$ as $\Bbb Z^+$, the set of positive integers, rather than as the set of non-negative integers, since it makes things just a little easier. Just for fun, here’s an actual bijection from $\bigcup_{k\ge 1}\Bbb N^k$ to $\Bbb N$ that uses only an elementary combinatorial result.
It’s a standard fact and easy to show that there are exactly $\binom{n-1}{k-1}$ ordered $k$-tuples of positive integers whose sum is $n$. It follows that there are $\sum_{k=1}^n\binom{n-1}{k-1}=\sum_{k=0}^{n-1}\binom{n-1}k=2^{n-1}$ finite sequences of positive integers that sum to $n$, since any such sequence is a $k$-tuple for some $k\le n$. For $n\in\Bbb N$ let $S_n$ be the set of finite sequences of positive integers whose sum is $n$; then $\left|\bigcup_{k=1}^{n-1}S_k\right|=\sum_{k=0}^{n-2}2^k=2^{n-1}-1$, so let’s try to define a bijection between $S_n$ and $[2^{n-1},2^n-1]$. (All intervals are taken in $\Bbb Z$.)
A natural possibility is to order $S_n$ lexicographically and let $\varphi_n:S_n\to[2^{n-1},2^n-1]$ be the unique order-isomorphism; $\varphi=\bigcup_{n\in\Bbb Z^+}\varphi_n$ is then a bijection from $\bigcup_{k\ge 1}\Bbb N^k$ to $\Bbb N$. This is clearly well-defined, but it takes a bit of work actually to exhibit the functions $\varphi_n$. Rather than simply presenting the result and then justifying it, I think that it will be clearer if I approach it more nearly the way I did in thinking about the problem.
In $S_n$ there are $2^{n-2}$ sequences that begin with $1$, $2^{n-3}$ that begin with $2$, and so on up to $2^0$ that begin with $n-1$, and then there is the $1$-term sequence $\langle n\rangle$. This is because when the first term of a sequence in $S_n$ is $d$, either $d=n$ and there are no more terms, or the remainder of the sequence is any of the $2^{n-d-1}$ members of $S_{n-d}$. A sequence in $S_n$ that begins with $d>1$ therefore has at least $\sum_{k=1}^{d-1}2^{n-1-k}=\sum_{k=n-d}^{n-2}2^k=2^{n-1}-2^{n-d}$ predecessors in $S_n$, and the final expression is evidently also valid for $d=1$.
The same reasoning shows that a sequence in $S_n$ that begins $\langle d_1,d_2\rangle$ has at least
$$(2^{n-1}-2^{n-d_1})+(2^{n-d_1-1}-2^{n-d_1-d_2})=2^{n-1}-2^{n-d_1-1}-2^{n-d_1-d_2}$$
predecessors in $S_n$. One that begins $\langle d_1,d_2,d_3\rangle$ has at least
$$\begin{align*}
&\;\;\;\;\;2^{n-1}-2^{n-d_1-1}-2^{n-d_1-d_2}+2^{n-d_1-d_2-1}-2^{n-d_1-d_2-d_3}\\
&=2^{n-1}-2^{n-d_1-1}-2^{n-d_1-d_2-1}-2^{n-d_1-d_2-d_3}
\end{align*}$$
predecessors in $S_n$. And in general $\langle d_1,d_2,\ldots,d_k\rangle\in S_n$ has exactly
$$\begin{align*}
&\;\;\;\;\;2^{n-1}-2^{n-1-d_1}-2^{n-d_1-d_2-1}-\ldots-2^{n-d_1-d_2-\ldots-d_{k-1}-1}-2^{n-d_1-d_2-\ldots-d_k}\\
&=2^{n-1}-2^{n-1-d_1}-2^{n-d_1-d_2-1}-\ldots-2^{n-d_1-d_2-\ldots-d_{k-1}-1}-1\\
&=2^{n-1}-1-\frac12\sum_{i=1}^{k-1}2^{n-\sum_{j=1}^id_j}\\
&=2^{n-1}-1-\frac12\sum_{i=2}^k2^{\sum_{j=i}^kd_j}\tag{1}
\end{align*}$$
predecessors in $S_n$. As a quick and dirty check, $(1)$ says that the sequence $\langle n\rangle$ should have $2^{n-1}-1$ predecessors in $S_n$, while the sequence of $n$ ones should have none, as is indeed the case.
We can now write down $\varphi$: if $\sigma=\langle d_1,d_2,\ldots,d_k\rangle$ is a finite sequence of positive integers whose sum is $n$, then
$$\begin{align*}
\varphi(\sigma)&=2^{n-1}-1-\frac12\sum_{i=2}^k2^{\sum_{j=i}^kd_j}\\
&=2^{n-1}-1-\frac12\sum_{i=2}^k2^{\sum_{j=i}^kd_j}\;.
\end{align*}$$
The final summation is of course understood to be $0$ when $k=1$.
A: I like
$$(n_1,\ldots,n_k)\mapsto 2^{n_1}+2^{n_1+n_2}+\cdots+2^{n_1+n_2+\cdots+n_k}.$$
But this does use the prime number $2$.
