# A question about primitive recursive functions

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 ?

-
Exercise 5.6 in this book claims that bijective primitive functions are a group, i.e. such a function $f$ exists: books.google.co.il/… –  Denis Apr 18 '13 at 13:39
DK, you mean to say that they are not a group. Frank, the inverse of Ackermann is primitive recursive, but this is not a bijection. But you can fix it up via the even/odd trick as in my argument and also as in DK's link (and those arguments are fundamentally similar). –  Joel David Hamkins Apr 18 '13 at 14:03

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.