# Degrees many-one below $0^\omega$

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$?

-
What do you mean by degrees of set? – abcdxyz Mar 30 '10 at 10:10
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}$. – Uri Andrews Mar 30 '10 at 10:38
By the way Uri, welcome to MO and thanks for asking this excellent question! – François G. Dorais Mar 30 '10 at 21:30
Thanks, Francois! – Uri Andrews Mar 30 '10 at 23:20
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? – Joel David Hamkins Mar 31 '10 at 1:21

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$.

-
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. – François G. Dorais Mar 30 '10 at 21:17
Thanks, Francois, I was wondering how to fix that. – Uri Andrews Mar 30 '10 at 23:21