It's not computable whether a number is a member of Kleene's ${\mathcal {O}}$. What is that set's Turing degree? I can almost see an argument that ${\mathcal {O}} \leq_T \emptyset^{(2)}$ but I can't see how to be sure that the set I'm thinking of is the smallest that meets the criteria. It also seems plausible that ${\mathcal {O}} =_T \emptyset^{(\omega_{CK})}$. Is this known?

  • $\begingroup$ en.wikipedia.org/wiki/Kleene%27s_O $\endgroup$ – Kaveh Aug 9 '16 at 2:18
  • $\begingroup$ $\mathcal{O}$ is $\Pi^1_1$-complete. Not sure what you mean by $\emptyset^{\omega_{CK}}$. To define jumps at limit ordinals you need fundamental sequences, you cannot just plug in an arbitrary ordinal there. See ch. 1 of vol. 2 of Classical Recursion Theory. $\endgroup$ – Kaveh Aug 9 '16 at 2:25

There is a talk given by Stephen Simpson, located here http://www.personal.psu.edu/t20/talks/pisa0104/talk.pdf, where he discusses the relative consistency strengths of various subsystems of second-order arithmetic $Z_2$. In particular, the theory $\Pi^1_1-CA_0$ denotes a subsystem of $Z_2$ whose set of true $\Pi^1_0$-consequences is of Turing degree $\emptyset^{(\omega^{CK}_{1})}$, which is the Turing degree corresponding to Kleene's $\mathcal O$. However, no proof is given, but I'm sure that one can be found in his bibliography for the talk (or perhaps even in his text on reverse mathematics http://www.personal.psu.edu/t20/sosoa/).

The relevant information in the PDF is on page 29.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.