Timeline for Computable images of differences of r.e. sets
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 9, 2013 at 15:49 | vote | accept | Benjamin Steinberg | ||
| Feb 9, 2013 at 13:09 | comment | added | Benjamin Steinberg | @Francois, but I am allowing any computable image of a difference of re sets. | |
| Feb 9, 2013 at 8:00 | comment | added | Noah Schweber | (In the above, technically in defining $f(X)_s$ I need to restrict attention to $y<s$ as possible witnesses to keep the approximation effective, but that doesn't wind up affecting anything.) | |
| Feb 9, 2013 at 7:57 | comment | added | Noah Schweber | @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$. | |
| Feb 9, 2013 at 5:19 | comment | added | François G. Dorais | Benjamin, $\Sigma^0_2$-sets are the sets which are r.e. relative to the halting set, this is much larger than the differences of r.e. sets. | |
| Feb 9, 2013 at 5:09 | comment | added | Benjamin Steinberg | That is sets of primes | |
| Feb 9, 2013 at 5:08 | comment | added | Benjamin Steinberg | 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. | |
| Feb 9, 2013 at 5:05 | comment | added | François G. Dorais | Don't you need $f$ to be infinite-to-one everywhere to get every $\Sigma^0_2$-set in this way? | |
| Feb 9, 2013 at 5:03 | comment | added | Benjamin Steinberg | It is not injective. Are the sets I am talking about always $\Sigma_2^0$? | |
| Feb 9, 2013 at 4:58 | history | answered | Dan Turetsky | CC BY-SA 3.0 |