

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

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


