4
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
8
  • $\begingroup$ It is not injective. Are the sets I am talking about always $\Sigma_2^0$? $\endgroup$
    – Benjamin Steinberg
    Commented Feb 9, 2013 at 5:03
  • $\begingroup$ Don't you need $f$ to be infinite-to-one everywhere to get every $\Sigma^0_2$-set in this way? $\endgroup$
    – François G. Dorais
    Commented Feb 9, 2013 at 5:05
  • $\begingroup$ 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. $\endgroup$
    – Benjamin Steinberg
    Commented Feb 9, 2013 at 5:08
  • $\begingroup$ That is sets of primes $\endgroup$
    – Benjamin Steinberg
    Commented Feb 9, 2013 at 5:09
  • 1
    $\begingroup$ @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$. $\endgroup$
    – Noah Schweber
    Commented Feb 9, 2013 at 7:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .