I Is the Inverse Image of a Computable Function Recursively Enumerable?

[Bedrich]

Hello, I am stuck on deciding if given sets are recursive or recursively enumerable and why. Those sets are:
set ƒ(A) = {y, ∃ x ∈ A ƒ(x) = y}
and the second is
set ƒ^-1(A) = {x, ƒ(x) ∈ A}
where A is a recursive set and ƒ : ℕ → ℕ is a computable function.

I am new to computability theory and any advice would be highly appreciated.

 

[andrewkirk]

They can both be recursively enumerable, for instance if $f^{-1}$ is a computable function (note that, strictly speaking, $f^{-1}$ is a function from N to the power set of N, ie the set of subsets of N). Examples are the functions that deliver result $\max(0,x-1), x+1, x$ and $0$.

But if $f^{-1}$ is not computable, the second set will not be RE. Do all functions from N to N have computable inverses?

 

[Bedrich]

They can both be recursively enumerable, for instance if $f^{-1}$ is a computable function (note that, strictly speaking, $f^{-1}$ is a function from N to the power set of N, ie the set of subsets of N). Examples are the functions that deliver result $\max(0,x-1), x+1, x$ and $0$.

But if $f^{-1}$ is not computable, the second set will not be RE. Do all functions from N to N have computable inverses?

Thank you for your answer. Can you please clarify the examples of functions. I can't really imagine how they could prove that ƒ^-1 is recursively enumerable. There is nothing said about that functions from ℕ → ℕ have computable inverses.

 

[andrewkirk]

Thank you for your answer. Can you please clarify the examples of functions. I can't really imagine how they could prove that ƒ^-1 is recursively enumerable. There is nothing said about that functions from ℕ → ℕ have computable inverses.

Having a computable inverse is the same as the image of the inverse being RE.

Consider the function $f:\mathbb N\to\mathbb N$ such that $f(x)=x+1$. The inverse function is $f^{-1}:\mathbb N\to 2^\mathbb N$ such that $f^{-1}(x)=\{x-1\}$ if $x>0$, and $f^{-1}(0)=\{0\}$.

The image of function $f^{-1}$ is $S=\{\{x\}\ :\ x\in \mathbb N\}$. This is recursively enumerable if there exists an algorithm that enumerates the members of $S$. Such an algorithm is:

x:=0;
while TRUE do
print(cat("{",x,"}"));
x := x+1;
end;​

where 'cat' is the string concatenation function.

Hence $S$ is RE.