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?
2
-
$\begingroup$ en.wikipedia.org/wiki/Kleene%27s_O $\endgroup$– KavehCommented Aug 9, 2016 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$– KavehCommented Aug 9, 2016 at 2:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
