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.

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?

Thanks

share|improve this question

1 Answer 1

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|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.) –  Arthur Fischer 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. –  Arthur Fischer Jan 29 '13 at 10:31

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.