# Computable images of differences of r.e. sets

Suppose f is a computable function from a recursively enumerable set U to the natural numbers and that L,K are r.e. subsets of U. Is f(L-K) a difference of r.e. subsets? The motivation comes from

Primes occurring as orders of elements of a finitely presented group

A positive answer would mean that the theorem proposed in HW's nice answer is 100% correct. Otherwise the $\epsilon$-clarification in my answer is actually needed.

-

Is f injective? If so, yes. If not, no. In the second case, you could achieve any $\Sigma^0_2$ set.
It is not injective. Are the sets I am talking about always $\Sigma_2^0$? – Benjamin Steinberg Feb 9 '13 at 5:03
Don't you need $f$ to be infinite-to-one everywhere to get every $\Sigma^0_2$-set in this way? – François G. Dorais Feb 9 '13 at 5:05
@Francois: I think you're right. If we insist $f$ be finite-to-one, then it seems that $X\in\Delta^0_2\impliesf(X)\in\Delta^0_2$, by the limit lemma: let $X_s$ be the approximation to $X$ at stage $s$, and approximate $f(X)$ by saying that $n\in f(X)_s$ if there is at stage $s$ some $y$ which appears to be in $X$ such that $f(y)=n$. Then for each $n$ and each $y\in f^{-1}(n)$, cofinitely often we have $y\in X_s\iff y\in X$; since $f^{-1}(n)$ is finite, we then get that cofinitely often, $n\in f(X)_s\iff n\in f(X)$, so $f(X)$ is $\Delta^0_2$. – Noah Schweber Feb 9 '13 at 7:57