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$?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ What do you mean by degrees of set? $\endgroup$– abcdxyzCommented Mar 30, 2010 at 10:10
-
$\begingroup$ I mean the Turing degree of the set. This is meant to ask about the interplay between a set being turing above each $0^n$ vs. it being many-one below $0^{\omega}$. The constructions that I've seen of sets turing strictly below $0^{\omega}$ but above each $0^n$ are far from producing many-one reductions from $0^{\omega}$. $\endgroup$– Uri AndrewsCommented Mar 30, 2010 at 10:38
-
$\begingroup$ By the way Uri, welcome to MO and thanks for asking this excellent question! $\endgroup$– François G. DoraisCommented Mar 30, 2010 at 21:30
-
$\begingroup$ Yes Uri, welcome to MO! I'm not sure what kind of characterization you're looking for, since being many-one reducible to 0^omega seems already like a good characterization, when one is used to thinking about Turing degrees. Do you know already how the m-1 degree of 0^omega interacts with the T-degree of 0^omega? $\endgroup$– Joel David HamkinsCommented Mar 31, 2010 at 1:21
-
$\begingroup$ Thanks, Joel. I don't really know much about the many-1 degrees within the Turing degree of $0^{\omega}$, which is definitely interesting in it's own right. To be honest, I don't personally know much about the analogous question for any Turing degree above $0$. The intended question was about Turing degrees which contain a set which is many-one reducible to $0^{\omega}$, mostly because I was afraid to broach the issue of the many-one refinement of a single turing degree or to leave the comfort of the Turing degrees entirely. $\endgroup$– Uri AndrewsCommented Mar 31, 2010 at 9:01
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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$.
-
$\begingroup$ Uri, you seem to have a double identity! Try using the same ID all the time. If your double earns some points, contact administrators or drop a message on tea.mathoverflow.net so they can merge your twin with your regular self. $\endgroup$ Commented Mar 30, 2010 at 21:17