# A bijective mapping from $\mathbb N^k$ to $\mathbb N$?

Having $k$ numbers $N_i\in\mathbb{N}$, I'm looking for a bijective mapping

$f:\mathbb{N}\times\ldots\times\mathbb{N}\rightarrow\mathbb{N}$

So that $f^{-1}\left(N_0\right)=\left(N_1,\ldots,N_k\right)$.

Any ideas?

-
May I ask what additional structure should be preserved by isomorphism? –  Evgeny Jul 30 '13 at 7:57
and what does $N_0$ mean? and what is $(N_1,\cdots,N_k)$? –  Ittay Weiss Jul 30 '13 at 8:00
@IttayWeiss I suppose $(N_1, \ldots, N_k)$ is a $k$-tuple. –  dtldarek Jul 30 '13 at 8:06
Do you mean a bijective mapping? (that is, a one-to-one and onto mapping?) When we say "isomorphic mapping" we mean that in addition to bijective-ness, we need to preserve some structure such as $f(x+y)=f(x)+f(y)$ or perhaps $f(x^2)=f(x)^2$. –  Eric Stucky Jul 30 '13 at 8:07
@EricStucky you're right, I'm looking for a bijective mapping. There's no algebraic structure whatsoever. –  Artem Oboturov Jul 30 '13 at 8:10

There is a nice bijection that works like this (here for $k = 3$):

$$\color{red}{42},\color{blue}{2013},\color{green}{789}, \to \color{blue}{2}\, \color{red}{0}\, \color{green}{7}\, \color{blue}{0}\, \color{red}{0}\, \color{green}{8}\, \color{blue}{1}\, \color{red}{4}\, \color{green}{9}\, \color{blue}{3}\, \color{red}{2}\,,$$

this is an easy extension of this $\mathbb{N}^2 \to \mathbb{N}$ bijection.

Another approach is to use any $f: \mathbb{N}^2 \to \mathbb{N}$ bijection and compose it with itself, e.g.

$$f_k (a_1,a_2,\ldots,a_k) = f(a_1, f(a_2, \ldots f(a_{k-1},a_k)\ldots)).$$

I hope this helps $\ddot\smile$

-
This is a constructive solution which I could use in a computer program, as I intended to. –  Artem Oboturov Jul 30 '13 at 9:18

To give a bijection $A\leftrightarrow\Bbb N$ amounts to define a sequence $a_1,a_2,a_3,...$ which includes all elements of $A$.

When $A=\Bbb N^k$ a standard way to do this is to write $$\Bbb N^k=\bigcup_{r=0}^\infty A_r,\qquad A_r=\{(n_1,...,n_k)\in\Bbb N^k\,|\,\sum_{j=1}^kn_j=r\}$$ and since every $A_r$ is finite we can list all elements of $A_1$, followed by all elements of $A_2$, followed by all elements of $A_3$, and so on.

This certainly works although it may not be easy to say what is the $n$-th $k$-ple ofthe sequence excplicitly.

P.S.: the above is written under the conventional assumption that $0\in\Bbb N$. If, so to speak, $\Bbb N$ starts with 1 the above works in the same way with the observation that the first non-empty subset $A_r$ is $A_k$.

-