5
$\begingroup$

Is there a standard principle in reverse math that is known to be equivalent (over $RCA_0$) to the existence of a set of high (Turing) degree? I'm interested in the general case, but would be happy to learn of such a principle for $\omega$-models.

I haven't been able to find much discussion on this topic... but then, I don't have much experience in reverse math yet. If the answer is obvious (say, $ACA_0$), please forgive me!

To clarify: the specific principle I'm interested in is the statement that "for all $X$, there exists some $Y\ge_T X$ with $Y'=X''$", appropriately rephrased to avoid the explicit use of the jump operator.

$\endgroup$
3
  • 1
    $\begingroup$ FWIW, one appropriate rephrasing is "for every set $X$, there is a function $f$ dominating all functions recursive in $X$." Another is the following. Fix $\Sigma^0_1$ and $\Sigma^0_2$ definitions $\varphi(Y, y)$ and $\psi(X, x)$ of the jump and double jump, respectively; then "High" should be the statement, "For every $A$ there is a $B\ge_T A$ and a computable function $h$ such that for all $e$, we have $\psi(A, e)\iff \varphi(B, h(e))$." (This is just saying that $A''$ is many-one reducible to $B'$.) I am not sure these two rephrasings are equivalent over $RCA_0$, but I suspect that they are. $\endgroup$ Feb 1, 2014 at 22:24
  • $\begingroup$ The domination principle is in fact the one I had in mind... but I didn't want to be overly restrictive. $\endgroup$
    – Eric Astor
    Feb 1, 2014 at 22:35
  • 1
    $\begingroup$ The domination principle was also studied by Frank Stefan and Zhang Jing - mathoverflow.net/questions/130832/… - comp.nus.edu.sg/~a0078129/FirstReport.pdf $\endgroup$ Feb 1, 2014 at 23:33

2 Answers 2

8
$\begingroup$

In the paper "On a conjecture of Dobrinen and Simpson regarding almost everywhere domination", Binns, Lerman, Solomon and I constructed $\omega$-models of this "high" principle which demonstrate it does not imply WKL, WWKL, or $G_\delta$-regularity.

$\endgroup$
2
  • 1
    $\begingroup$ That's immensely helpful. So the existence of a set of high degree does not imply even $WWKL_0$. A question: does this relativize in such a manner that the same holds true for the principle "for every $X$, there is a $Y\ge_T X$ with $Y'=X''$"? $\endgroup$
    – Eric Astor
    Feb 1, 2014 at 21:55
  • 1
    $\begingroup$ You're welcome, and yes -- that's what the paper shows $\endgroup$ Feb 1, 2014 at 22:01
3
$\begingroup$

I believe the answer is "no." Certainly $ACA_0$ is overkill; we can build an ascending sequence $H_0\le_T H_1\le_T . . .$ of sets such that $H_{n+1}'=H_n''$ (i.e., $H_{n+1}$ is high over $H_n$), but no $H_n$ computes $0'$. This is done by iterating a jump inversion theorem:

Suppose $X$, $Y$, and $Z$ are sets such that $X=Z'$ and $Z\not\ge_T Y$. Then there is a set $A$ with $A'=X$, $A\ge_T Z$, and $A\not\ge_T Y$.

(If I recall correctly, this is basically the Friedberg Completeness Criterion with extra bells and whistles, although there are several jump inversion theorems, so I might have the wrong name.) To get $H_{n+1}$ from $H_n$, just apply the theorem with $X=H_n'$, $Z=H_n$, and $Y=0'$.

On the other hand, such a principle might be useful in reverse math down the road, even if it hasn't shown up yet. A while ago, Damir Dzhafarov and I thought we'd found a use for the principle "for each set $X$, there is a $Y\ge_TX$ with $Y'=X''$" (rephrased appropriately, since of course jumps need not exist). Now if I recall correctly it wound up not being strong enough to help us, but I still think it's probably relevant for something.

$\endgroup$
3
  • $\begingroup$ It just occurred to me that by "high" you might mean "high and c.e." I'm pretty sure everything I wrote is still true, appropriately altered, but I'm not certain. $\endgroup$ Feb 1, 2014 at 20:39
  • $\begingroup$ I definitely didn't have c.e. in mind as a requirement. In fact, this question is motivated by finding a condition equivalent to having either high or DNC degree (i.e., failing to be weakly computably traceable). However, the c.e. case of this condition has been of significant interest to me so far... So yes, that's interesting, though not what I originally had in mind. $\endgroup$
    – Eric Astor
    Feb 1, 2014 at 21:05
  • $\begingroup$ (Oh, also: Hi Eric! :P) $\endgroup$ Feb 1, 2014 at 22:10

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.