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

share|cite|improve this question
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. – Noah Schweber Feb 1 '14 at 22:24
The domination principle is in fact the one I had in mind... but I didn't want to be overly restrictive. – Eric Astor Feb 1 '14 at 22:35
The domination principle was also studied by Frank Stefan and Zhang Jing -… - – François G. Dorais Feb 1 '14 at 23:33
up vote 6 down vote accepted

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.

share|cite|improve this answer
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''$"? – Eric Astor Feb 1 '14 at 21:55
You're welcome, and yes -- that's what the paper shows – Bjørn Kjos-Hanssen Feb 1 '14 at 22:01

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.

share|cite|improve this answer
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. – Noah Schweber Feb 1 '14 at 20:39
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. – Eric Astor Feb 1 '14 at 21:05
(Oh, also: Hi Eric! :P) – Noah Schweber Feb 1 '14 at 22:10

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.