Take the 2-minute tour ×
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.

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?

share|improve this question
3  
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
1  
@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
show 8 more comments

2 Answers 2

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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.