I have a question about primitive recursive functions. Maybe it's trivial, if it is I will move it into math.stackexchange.


Is there a primitive recursive function $f$ which is a bijection of $N$ onto $N$ such that $f^{-1}$ is **not** primitive recursive ?



A question about primitive recursive functions
The answer is yes. First, let $g$ be a total computable function whose rate of growth is too fast for it to be primitive recursive, such as the diagonal Ackermann function. Now, define $f(k)=2n$, if $k$ is the number coding up (in some canonical way) the computation of $g(n)$. That is, $k$ should encode a list of the entire computation sequence for $g(n)$, including snapshots of the configuration of each stage of computation, what is on the tape, where the head is, the state and so on. Now, for numbers $k'$ that are not codes of computations, we let $f(k')$ be the smallest odd number not yet used. Thus, we have a bijection $f:\mathbb{N}\to\mathbb{N}$. 


Furthermore, $f$ is primitive recursive, because for a given $k$, we can bound the length of time it takes to compute $f(k)$---the algorithm need only unpack $k$ and verify whether it is a proper code or not, and then do some easy computations on the side. 


Meanwhile, the inverse function is not primitive recursive. The point here is that $k$ is far larger than $n$. We cannot get from $n$ or $2n$ to a code $k$ for the computation of $g(n)$, because we assumed that the growth rate of $g$ was too high for it to be primitive recursive. 


