most recent 30 from http://mathoverflow.net 2013-05-26T08:48:27Z http://mathoverflow.net/feeds/question/42923 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/42923/how-does-the-constructibility-degree-of-a-real-compare-with-its-turing-degree Tanmay Inamdar 2010-10-20T19:22:08Z 2010-10-20T21:32:02Z

<p>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.</p> <p>Thank you in advance.</p>

http://mathoverflow.net/questions/42923/how-does-the-constructibility-degree-of-a-real-compare-with-its-turing-degree/42924#42924 Bjørn Kjos-Hanssen 2010-10-20T19:24:16Z 2010-10-20T19:24:16Z

<p>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$.</p>

http://mathoverflow.net/questions/42923/how-does-the-constructibility-degree-of-a-real-compare-with-its-turing-degree/42949#42949 Stefan Geschke 2010-10-20T21:32:02Z 2010-10-20T21:32:02Z

<p>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.<br> This observation explains Carl Mummert's statement "in $L$ there are extremely large Turing degrees".</p>