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 ?
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.
More concisely, it is not far from the truth to say that the purpose of (adding) the minimalisation operation for general recursion is to define inverse functions. That this is Difficult is put to practical use in many methods of encryption.
