Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Specifically, is it the case that (for $a,b\in\omega^\omega$) $a$ $\leq_T$ $b$ implies $a$ $\leq_c$ $b$? I suspect it might be trivial, but not knowing much Recursion Theory, it's hard to see how it could.

Thank you in advance.

share|cite|improve this question
Being constructible from a real $b$ is a much more general notion than being computable from $b$. In particular, every real that is in $L$ is constructible (with no oracle) even though there are elements of $L$ of extremely large Turing degree. Also, the reals constructible from a real $b$ are closed under Turing jump and hyperjump. It's an almost trivial restatement of the definitions that given a real $b$, ZFC cannot prove there is any real that is not constructible from $b$. –  Carl Mummert Oct 20 '10 at 20:05
Yes, I would have expected the same. Intutively, I figured that the definable operations we use to construct $L$ should easily be enough to be able to come up with a Turing machine(in $L[b]$) with $b$ as an oracle. As an aside, how large is extremely large? –  tci Oct 20 '10 at 20:52
For example, the set $T$ of true formulas in the standard model of second order arithmetic is constructible, and must be of enormous Turing degree, because any set of natural numbers that is definable in second-order arithmetic is Turing reducible to $T$. There was a comment before (now deleted) that gave essentially the same example. –  Carl Mummert Oct 24 '10 at 23:28

2 Answers 2

up vote 4 down vote accepted

Yes, if $a\le_T b$ then $a$ is first-order definable from $b$; in particular $a\in L(b)$ so $a\le_c b$.

share|cite|improve this answer
In more detail: if $a\le_T b$ then $a=\Phi^b$ for some Turing functional $\Phi$. The set $\Phi^b$ is $\Sigma_1(b)$ definable (actually $\Delta_1(b)$ definable here since $\Phi^b$ is total). –  Bjørn Kjos-Hanssen Oct 20 '10 at 20:27
Hi, thanks for the answer. I unfortunately did not mention the more general question that I asked in the title, but thankfully Stefan and Andres answered that. Thanks once again. –  tci Oct 21 '10 at 19:15

As Bjorn pointed out, $a\leq_Tb$ implies $a\leq_cb$. But it should also be mentioned that constructible degrees are much coarser then Turing degrees: Suppose $\aleph_1^L$ is the real $\aleph_1$. Then every constructible degree (set of $\leq_c$-equivalent reals) is uncountable (take your real $a\in\omega^\omega$ and consider all coordinate wise sums of $a$ and a constructible real. These sums are all of the same constructible degree as $a$). Every Turing degree is countable since there are only countably many Turing machines.
This observation explains Carl Mummert's statement "in $L$ there are extremely large Turing degrees".

share|cite|improve this answer
Anyway, even if $\aleph_1^{L[a]}$ is countable for all $a$, constructibility degrees are much coarser than Turing degrees. Note $a$ is constructibly equivalent to its jump, its Hyperjump, and much more. Grozsek and her co-authors and students have looked at the relation between the order of constructible degrees and the Turing degrees (they are not equivalent structures). –  Andrés Caicedo Oct 20 '10 at 21:39
Hi Stefan, thanks for the answer. This answers the more general question which I unfortunately only mentioned in the title. Andres, if you know of any suitably low-level(in the sense of starting from a modest background/survey article) paper of theirs, could you please send me a link? –  tci Oct 21 '10 at 19:16
@Tanmay, keep in mind that most results in the constructibility side of this area require forcing. They may establish the corresponding result for Turing degrees, or there may be subtle differences, and in that case, the recursion theoretic counterpart tends to require a priority argument. In any case, there are some basic results that can be read without too much background. A good starting point is a survey by Richard Shore, "Degrees of constructibility", in Set theory of the continuum (Berkeley, CA, 1989), Math. Sci. Res. Inst. Publ., 26, Springer, New York, 1992, 123–135. –  Andrés Caicedo Oct 24 '10 at 16:38
@Tanmay, you may also want to contact directly Marcia Groszek or François Dorais for more up-to-date results, and perhaps links to surveys or introductory material. –  Andrés Caicedo Oct 24 '10 at 16:42

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.