Wednesday, 30 June 2010

lo.logic - Degrees many-one below $0^omega$

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

No comments:

Post a Comment