MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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$.

share|cite|improve this answer
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 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.