Take the 2-minute tour ×

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.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Is f injective? If so, yes. If not, no. In the second case, you could achieve any $\Sigma^0_2$ set.

share|improve this answer
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
I am thinking of f,U,L,K as things I can vary and I would like to know the full range of primes that can be picked up. –  Benjamin Steinberg Feb 9 '13 at 5:08
That is sets of primes –  Benjamin Steinberg Feb 9 '13 at 5:09
@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

Your Answer


