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.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ 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$. $\endgroup$– Carl MummertCommented Oct 20, 2010 at 20:05
-
$\begingroup$ 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? $\endgroup$– user3462Commented Oct 20, 2010 at 20:52
-
$\begingroup$ 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. $\endgroup$– Carl MummertCommented Oct 24, 2010 at 23:28
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
2
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$.
answered Oct 20, 2010 at 19:24
-
1$\begingroup$ 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). $\endgroup$ Commented Oct 20, 2010 at 20:27
-
$\begingroup$ 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. $\endgroup$– user3462Commented Oct 21, 2010 at 19:15
$\begingroup$
$\endgroup$
4
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".
answered Oct 20, 2010 at 21:32
-
3$\begingroup$ 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). $\endgroup$ Commented Oct 20, 2010 at 21:39
-
$\begingroup$ 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? $\endgroup$– user3462Commented Oct 21, 2010 at 19:16
-
$\begingroup$ @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. $\endgroup$ Commented Oct 24, 2010 at 16:38
-
$\begingroup$ @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. $\endgroup$ Commented Oct 24, 2010 at 16:42