Prove the inverse of a 1-1 1-place partial recursive function is partial recursive.

135 Views Asked by At

I'm working through exercises in recursion theory and one such exercise is to prove the inverse of a 1-1 1-place partial recursive function $\psi$ is partial recursive, which was given with somewhat of a warning as to its difficulty. I've figured out if you can prove $dom(\psi)$ is recursive you can write $\psi^{-1}(x)=\mu z(z\in dom(\psi) \land \psi(z)=x)$ such that the predicate in the parenthesis is computable, so $\psi^{-1}$ is partial recursive. Though I have no idea even if $dom(\psi)$ is recursive much less how to prove it. Any ides?