Existence of a injective and recursive(but not primitve recursive) fucntion that has a primitve recursive inverse.

Question

The Question is as follows:

For a one-to-one function f:N -> N, it's inverse is defined as:

$$ f^{-1}(n) = \begin{cases} m+1 & \text{if }f(m)=n \\ 0 & \text{if } \forall m\in\mathbb N: f(m)\ne n \end{cases}$$

Prove that there exists a injective and recursive Function F:N->N that is not primitve recursive but it's inverse Is.

I've tried to find the f funtion but $f^{-1}$ definition is really confusing to me and I can't come up with a function whose inverse is $f^{-1}$.

The fact that inverse function maps to m+1 is really strange as if $f(m)=n$ then $f^{-1}of(m)$=m+1 while it should technically be m.

How can find $f^{-1}$?

Answer 1

You're not supposed to "come up with a function whose inverse is $f^{-1}$". You should interpret the exercise as saying something like

For the purpose of this exercise, the word "inverse" and the notation $f^{-1}$ will have the following slightly unusual meaning: $$ f^{-1}(n) = \begin{cases} m+1 & \text{if }f(m)=n \\ 0 & \text{if } \forall m\in\mathbb N: f(m)\ne n \end{cases}$$ (bla bla bla)

It's not asking you to find a function whose ordinary inverse satisfies the equation; it's asking you to find an $f$ such the the modified inverse the exercise defines is primitive recursive, but $f$ is not itself primitive recursive.

If this is hard for you, just imagine that the problem uses a different word than "inverse" -- for example,

For a one-to-one function $f:\mathbb N \to \mathbb N$, its boojum is by definition the function

$$ f^{\rm B}(n) = \begin{cases} m+1 & \text{if }f(m)=n \\ 0 & \text{if } \forall m\in\mathbb N: f(m)\ne n \end{cases}$$

Prove that there exists a injective and recursive function $f:\mathbb N\to\mathbb N$ that is not primitve recursive but its boojum is.

Something like Ackermann's function should work as $f$; the challenge is then to show that $f^{\rm B}$ is primitive recursive.

You can make the proof easier to conduct by packing more information into the value of $f(n)$ -- for example, let $g$ be a fixed recursive-but-not-primitively-so function, and $T$ be a fixed turing machine that computes $g$, and then $$ f(n) = 2^n 3^{g(n)} 5^{(\text{number of steps $T$ executes on $n$})} $$