Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

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

Is there an example of a bijective map pi: N^2 --> N (where N = natural #'s) which is primitive recursive?

I'm thinking along the lines of projection function but can't quite spell it. Are there some examples?

And how is it bijective as opposed to injective or sujective?


share|cite|improve this question
up vote 4 down vote accepted

Consider the map $$f \colon \mathbb N^2 \to \mathbb N$$ defined as $f(n,m)=2^n(2m +1) - 1$ this is primitive recursive and it's also bijective. Bijectivity follows directly by the unique factorization's theorem: indeed for every natural number $x \in \mathbb N$ we have that $x+1 > 0$ can be uniquely factor as the product of finite sequence power of primes $x=2^{n}p_1^{n_1}\dots p_k^{n_k}$ where the $p_i$ are odd primes, the product $p_1^{n_1}\dots p_k^{n_k}$ is odd so it can be expressed as $2m + 1$ for a unique $m \in \mathbb N$. So $x+1 = 2^n(2m+1)$ for a unique pair $(n,m) \in \mathbb N^2$ and so $x= 2^n(2m + 1) - 1$.

For the primitive recursion part, we have that the functions $$g \colon \mathbb N \to \mathbb N$$ $$n \mapsto 2^n$$ $$h \colon \mathbb N \to \mathbb N$$ $$m \mapsto 2m + 1$$ the multiplication $$ \cdot \colon \mathbb N^2 \to \mathbb N$$ and the predecessor $$p \colon \mathbb N\setminus \{0\} \to\mathbb N$$ $$p(n) = n-1 $$ are primitive recursive, so the function $f=p \circ (\cdot)\circ (g,h)$ which is obtained by composition by these function is primitive recursive too.

share|cite|improve this answer
@ArthurFischer thanks for pointing out, I'll edit, thanks. :) – Giorgio Mossa Jan 29 '13 at 10:00
Details, details, details.. ;-) (Looks good now, BTW.) – arjafi Jan 29 '13 at 10:07
@ArthurFischer enough details? – Giorgio Mossa Jan 29 '13 at 10:29
You misunderstood, I think. Your previous version was fine. By "Details, details, details.. ;-)" I was referring to the small error regarding the bijectivity of your original function $f$. I apologise if this was not clear. – arjafi Jan 29 '13 at 10:31

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.