Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


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

Any ideas?

share|cite|improve this question
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$

share|cite|improve this answer
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.