Is there any nice categorization of degrees of sets which are many-one reducible to $0^{\omega}$? ($0^{\omega}$ is the set whose nth column answers which $\Sigma_n$ statements are true in $(\mathbb{N},+,\cdot)$.) For instance, there are sets S which are turing above each $0^n$, and $S^{(2)}\equiv_T 0^{\omega}$. Can such a set be many-one reducible to $0^{\omega}$? If not, how about any set $S<_T 0^{\omega}$ above each $0^n$?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
2
|
||||||||||||||||
|
|
2
|
Sorry for answering my own question, but I'm still hoping for a characterization of some kind. A partial answer: Let $S$ be the result of a normal jump inversion forcing for $0^{\omega}$ with added requirements that the nth column is $0^n$ modulo a finite amount. This yields a degree many-one below $0^{\omega}$, even many-one above each $0^n$, whose jump is $0^{\omega}$. The reason S is many-one below $0^{\omega}$ is that we know that the algorithm gives uniformly an answer for the nth bit from $0^{n}$, since no higher requirements have been initialized by that point. So, running the turing algorithm from $0^{\omega}$ is the same as running the corresponding algorithm from $0^n$. The outcome is an arithmetical fact, so can be checked in one query of $0^{\omega}$. It appears that the many-one degrees below $0^{\omega}$ (many-one) above each $0^n$ is a rich enough structure, since it contains $[S,0^{\omega}]_m$. It seems possible that similarly intertwining requirements, we can get a set whose double-jump is $0^{\omega}$ above each $0^n$. |
||||||
|
