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.

Improve this question
$\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$
    – Noah Schweber
    Commented 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
    Commented 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$
    – François G. Dorais
    Commented Feb 1, 2014 at 23:33

2 Answers 2

Reset to default
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.

Improve this answer
$\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
    Commented Feb 1, 2014 at 21:55
  • 1
    $\begingroup$ You're welcome, and yes -- that's what the paper shows $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented 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.

Improve this answer
$\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$
    – Noah Schweber
    Commented 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
    Commented Feb 1, 2014 at 21:05
  • $\begingroup$ (Oh, also: Hi Eric! :P) $\endgroup$
    – Noah Schweber
    Commented Feb 1, 2014 at 22:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .