# Prove that $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$ is partial recursive

I'm stuck on this problem:

Given $f:\mathbb{N} \rightarrow \mathbb{N}$ a partial recursive function that is also injective and total. Prove that the function $f^{-1}:\mathbb{N} \rightarrow \mathbb{N}$ $$f^{-1} = \left\{\begin{array}{rcl} x & \mbox{if} & f(x) = y \\ \uparrow & \mbox{otherwise}\end{array}\right.$$ is partial recursive.

So to prove that a function is partial recursive I have to show that I can build it from basic recursive functions (successor, projection and constant) by applying composition, primitive recursion and then minimization.

I don't know what form $f$ has, but I think I can use it to construct $f^{-1}$. The only problem is that I don't know what to write...

• You're confusing partial recursive with primitive recursive. – Yuval Filmus Jul 28 '18 at 20:47

You can partially compute $f^{-1}(y)$ as follows:

for $x$ from $0$ to $\infty$:

if $f(x) = y$ then return $x$

If you don't like for loops, you can use the following implementation:

1. $x \gets 0$
2. if $f(x) = y$ then return $x$
3. $x \gets x + 1$
4. goto step 2
• Thank you, it makes a lot of sense but I'm really confused. I can see that what you wrote can be implemented by a Turing machine, but still by some definitions I know that: 1). The class $PR$ of partial recursive functions is the minimum set of $P$ primitive recursive functions closed by $\mu -operator$ 2) $\Phi:\mathbb{N} \rightarrow \mathbb{N}$ is partial recursive if and only if is computable by a Turing machine. What is the relationship between those two definitions? – tokenizer Jul 29 '18 at 9:18
• The two definitions are equivalent. – Yuval Filmus Jul 29 '18 at 10:31
• So I can build $f^{-1}$ using primitive recursive functions and applying the $\mu-operator$, right? – tokenizer Jul 29 '18 at 10:37
• All partially recursive functions have such a representation. – Yuval Filmus Jul 29 '18 at 10:42
• So is it right to express it like this: $f^{-1}(y,z)=\mu x<z (*(\bar{sg}(-(f(x),y)),*(\bar{sg}(-(y,f(x))), y)))$. Where $*$ is the primitive recursive function that computes the multiplication, $sg(x)$ returns the sign of $x$ (0 if $x \leq 0$ or 1 if $x > 1$), and $-$ is the function that computes the difference. – tokenizer Jul 29 '18 at 11:12