Timeline for How does the Constructibility Degree of a real compare with its Turing Degree?
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 24, 2010 at 23:28 | comment | added | Carl Mummert | 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. | |
| Oct 20, 2010 at 21:32 | answer | added | Stefan Geschke | timeline score: 4 | |
| Oct 20, 2010 at 21:11 | vote | accept | CommunityBot | ||
| Oct 20, 2010 at 20:52 | comment | added | user3462 | 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? | |
| Oct 20, 2010 at 20:05 | comment | added | Carl Mummert | 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$. | |
| Oct 20, 2010 at 19:24 | answer | added | Bjørn Kjos-Hanssen | timeline score: 5 | |
| Oct 20, 2010 at 19:22 | history | asked | user3462 | CC BY-SA 2.5 |