Inverse of a primitive recursive bijection

Question

Is it true or false that the inverse of a primitive recursive bijection $f: \mathbb{N} \to \mathbb{N}$ is also primitive recursive (pr)?

Answer 1

No this is not true!

Let's $A$ the Ackermann-Peter function (defined by $A(x)=A(x,x)$ with this definition). Note that $A$ is fast growing, recursive but not primitive recursive. But $A^{-1}$ defined by $A^{-1}(x)=1+\max\{y\;|\;A(y)\le x\}$ ($0$ if the set is empty) is recursive primitive (and very slow growing).

Now consider the sets $B=\{A(x) \;|\; x \in \mathbb N\}$ and $\overline{B}=\mathbb N\setminus B $ (both infinite).

And the sets $Odd=\{2x+1 \;|\; x \in \mathbb N\}$ and $\overline{Odd}=\mathbb N\setminus E $ (both infinite).

Then the bijection $\mathcal B$ that matchs the $k^{th}$ element of $B$ to the $k^{th}$ element of $Odd$ and the $k^{th}$ element of $\overline{B}$ to the $k^{th}$ element of $\overline{Odd}$ is recursive primitive (because given $x$, you need to compute $y=A^{-1}(x)$ and at the same time verify that $A(y-1)=x$ (both can be done with primitive functions). if $A(y-1)=x$ then $\mathcal B(x)=2y-1$ else $\mathcal B(x)=2*(x-y)$

But $\mathcal B^{-1}$ is not primitive recursive as $\mathcal B^{-1}(2x+1)=A(x)$

Answer 2

It might help to give not another answer alongside Xoff's, but to give some motivation for expecting the answer to your question to be 'False'.

Suppose $f\colon \mathbb{N} \to \mathbb{N}$ be bijective and primitive recursive. Then we know $f^{-1}\colon \mathbb{N} \to \mathbb{N}$ is defined. And we can show that it is computable. For here's the obvious method of computation (the one that convinces us that $f^{-1}$ is indeed computable). To calculate $f^{-1}(n)$, compute in turn $f(0), f(1), f(2), \ldots, f(k)$ until we hit $k$ such that $f(k) = n$, then put $f^{-1}(n) = k$. That's a computation, since each of $f(j)$ is finitely computable, and it terminates since $f$ is bijective on the numbers so eventually for some $k$, $f(k) = n$.

But note:

This computation [and obvious variants, e.g. by interweaving steps of the calculation of the various different $f(j)$] requires an open-ended do until loop, and primitive recursive functions can all be computed using only closed for $x = 1$ to $j$ loops.

That's not yet a proof. But it tells us why, morally, we can't expect $f^{-1}$ to be primitive recursive in general.