How can I prove that the inverse function of a total recursive function is recursive?

607 Views Asked by At

The full question actually is :

If $A\subseteq \mathbb{N}$ and $f: \mathbb{N} \rightarrow \mathbb{N}$ is a function. Prove that if $f$ is a total recursive function and $A\subseteq \mathbb{N}$ recursive, then $f^{-1}(A)$ is recursive.

I guess that the part that $A\subseteq \mathbb{N}$ is recursive is helping us to understand that this statement is true. However, I do not know how to prove it.

Any help would be very much appreciated it.

1

There are 1 best solutions below

3
On BEST ANSWER

HINT: the question is not to show that the inverse function is recursive, but rather to show that the set $f^{-1}(A) = \{ n \in \mathbb{N}| f(n) \in A \}$ is recursive.

Now, given that $A$ is recursive, we know that its characteristic function $c_A$ is recursive, where $c_A(n)=1$ if $n \in A$ and $c_A(n)=0$ if $n \not \in A$

And since $f$ is recursive, the composition $c_A(f)$ is recursive as well, where we have $c_A(f(n))=1$ if $f(n) \in A$ and $c_A(f(n))=0$ if $f(n) \not \in A$. But that is exactly the characteristic function of $f^{-1}(A)$. Hence, the set $f^{-1}(A)$ is recursive.