Timeline for Undecidability [sic] in set theory [per se]
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 15, 2011 at 12:41 | comment | added | Carl Mummert | Kleene's $\mathcal{O}$ is of the same Turing degree as the set of ''e'' such that $\phi_e$ is a computable well-ordering of $\omega$. In the latter case there is not the same explicit coding. However, in the example from my first paragraph there is essentially no coding at all, it is literally the set of graphs of well-orderings of $\omega$. | |
| Dec 15, 2011 at 6:52 | comment | added | David Feldman | Now that I've gotten up to speed a little concerning Kleene's {\em O}, I guess I don't agree yet that "being well ordered is a purely set-theoretic problem." (On the other hand, being well-orderable, yes.) Your example seems to belong directly to the theory of computation, as distinct from set theory. Whatever the importance of Kleene's {\em O} to mathematicians (proof theorists, right?), the question whether some specific $n$ belongs to Kleene's {\em O} doesn't strike me as "natural," if for no other reason, because of dependence on the particular coding. | |
| Dec 15, 2011 at 1:26 | history | answered | Carl Mummert | CC BY-SA 3.0 |