13
$\begingroup$

The Posner-Robinson theorem states that, if $X$ is noncomputable, there is some $G$ such that $X\oplus G=G'$; that is, even though genuine jump inversion only works above $0'$, every (nontrivial) $X$ is "almost" the jump of something. There are a number of extensions and variations of the Posner-Robinson theorem; I'm interested in two, due to unpublished work of Hugh Woodin.

In multiple places - e.g. page 208 of "Proceedings of the 13th Asian Logic Conference" - we find the claim that Woodin proved the following higher-order analogues of the Posner-Robinson theorem:

  • If $X$ is not hyperarithmetic, then there is some $G$ such that $X\oplus G\equiv_T \mathcal{O}^G$.

  • (Assume $X^\#$ exists for every real $X$.) If $X$ is not constructible, then there is some $G$ such that $X\oplus G\equiv_T G^\#$.

My question is: are these proofs available anywhere?

$\endgroup$
1
  • $\begingroup$ Ted may have a proof for Turing degrees for the HYP version by Kumabe-Slaman forcing. $\endgroup$
    – 喻 良
    Oct 13, 2015 at 22:49

2 Answers 2

13
$\begingroup$

MR2449474 (2009j:03067) Woodin, W. Hugh. A tt version of the Posner-Robinson theorem. Computational prospects of infinity. Part II. Presented talks, 355–392, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., 15, World Sci. Publ., Hackensack, NJ, 2008.

The proof is nice, invoking both recursion-theoretic and set-theoretic tools. Hugh uses a Prikry-like forcing notion, and considers forcing over countable non-standard $\omega$-models of (a large fragment of) set theory.

(For other examples of forcing over non-standard models, see Projective prewellorderings vs projective wellfounded relations by X. Shi, or the last few chapters of the monograph Super-real fields by Hugh and Garth Dales.)

$\endgroup$
6
  • 2
    $\begingroup$ While extremely cool (+1), this doesn't seem to be what I was looking for, actually - Woodin there proves that the a tt-version of Posner-Robinson holds outside HYP: that is, he shows that for $X$ non-hyperarithmetic, there is some $Y$ such that $X+Y$ is $tt$-equivalent to $Y'$. He then extends this up the hierarchy, e.g. to the hyperjump, but again for $tt-$equivalence, and his hypothesis is stronger: e.g. Theorem 4.1 demands $X\not\in L_{\omega_1^*}$, where $\omega_1^*$ is the least admissible limit of admissibles. Also, the sharp is not treated in the paper. $\endgroup$ Oct 13, 2015 at 19:17
  • $\begingroup$ I believe he has at least a comment there about relativizing to other reducibilities or degree structures (such as the sharp). The same outline should provide these results. A point of the proof he chose to present was that tt-equivalence is more restrictive than Turing equivalence. $\endgroup$ Oct 13, 2015 at 19:25
  • $\begingroup$ But I'm specifically interested in the Turing equivalence situation, which is significantly different in that, for $tt$, the hypotheses on $X$ need to be strengthened - so e.g. the hyperjump version isn't a corolloary of Woodin's $tt$-Posner-Robinson for the hyperjump. (Also, I'd hope the Turing side is easier.) $\endgroup$ Oct 13, 2015 at 20:17
  • $\begingroup$ Yes, Noah, the argument is easier in that case. Take a look at the nice paper, you should be able to extract the variants you need. $\endgroup$ Oct 13, 2015 at 20:55
  • $\begingroup$ I'm going to hold off on accepting this answer for now, until I've had a chance to go through the paper and check that I can get the versions of the theorems I want. But - thank you very much, this is awesome! $\endgroup$ Oct 13, 2015 at 21:29
6
$\begingroup$

This result by Woodin is stated as "unpublished" in a paper published by his former Ph.D. student Xianghui Shi in July 2015, so that seems to be an authoritative source:

Axiom $I_0$ and higher degree theory
The Journal of Symbolic Logic 80, 970-1021 (2015).

$\endgroup$
2
  • $\begingroup$ (That 10 should be $I0$.) $\endgroup$ Oct 13, 2015 at 19:31
  • $\begingroup$ (I would think instead that Shi simply overlooked Hugh's 2008 paper. Shi himself points out through the paper that he simply argues about Zermelo's degrees to illustrate the idea of his results, and that they apply to general degree notions. It is the same situation.) $\endgroup$ Oct 13, 2015 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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