|
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 |
|||
|
|
|
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. |
|||||||||
|
