Inverse of a recoursive function

Question

I'm defining a function f as the inverse of another recursive bijective function g. Can I assume f to be recursive based on the recursiveness of g? For contest I'm trying to solve a problem of my Mathematical Logic course. Thank you.

Answer 1

It depends how formal you want to be/need to be! Here's an intuitive proof ...

Suppose $g$ is recursive, and bijective on the natural numbers. Since it is bijective, for every $m$, $g(m)$ needs to be defined; and for every $n$ there is a unique $m$ such that $g(m) = n$. So $g$ is not only recursive but total.

Then it is easy to see that $g$'s inverse $f$ is effectively computable. Given input $n$, just start computing $g(0)$, $g(1)$, $g(2)$, ... until you get to some $g(m) = n$. This is an effective routine because each computation of $g(j)$ eventually terminates as $g$ is total recursive, and we know that we must get to $g(m) = n$. When we do, output the value $m$. And voila! -- a computation for $f(n) = m$, $g$'s inverse.

So by a labour-saving invocation of Church's Thesis, since it is computable, $f$ is recursive.