# Complexity of the set of computable ordinals

The set of all natural numbers which are indices of computable ordinals is a $\Pi^1_1$ set which is not $\Sigma^1_1$.

However, "the set of all natural number which are indices of computable ordinals" can be interpreted as

• the set of indices of recursive binary relations which well-order some subset of natural numbers;
• Kleene's $\cal O$.

To which interpretation the above result refers? Ideally the two interpretations are reducible to one another, and the result refers to both, but it's not obvious to me. And also, where can I read more about this result?

See the Wikipedia article for Kleene's $\mathcal{O}$:

In fact, $\mathcal{O}$ is $\Pi^1_1$-complete and every $\Sigma^1_1$ subset of $\mathcal{O}$ is effectively bounded in $\mathcal{O}$ (a result of Spector).

I think it also work for other nice indexing of recursive ordinals, but I am not sure it holds for all indexing, e.g. it is not clear if this holds if the indexing is not a universal one (i.e. we can effectively translate notions from $\mathcal{O}$ to it).

• Thanks for the answer. I've noticed it and probably should have mentioned in my answer. Rogers also proves $\Pi_1^1$ completeness of $\cal O$. So my question basically boils down to this: Can we effectively translate notions from $\cal O$ into a recursive relation that well-orders a subset of natural numbers with the corresponding order type. Although I couldn't find this stated in Rogers, proofs of Theorem XIX and Corollary XIX suggest that. – Levon Haykazyan Nov 2 '11 at 21:32
• @Levon Haykazyan: I believe the theorem you want is Theorem 4.4 in Chapter 1 of Sacks Higher Recursion Theory which is now freely available at projecteuclid.org/euclid.pl/1235422633 . It takes a little work to chase down the proof in that book, but at least the result is on page 18, so there is not too much work to reconstruct the entire proof. – Carl Mummert Nov 3 '11 at 0:33
• @CarlMummert: Thank you, that is indeed what I am looking form. – Levon Haykazyan Nov 4 '11 at 14:03

Since this question didn't get any answers from experts, I'll post here my findings (in case anybody will come across the question).

The standard reference to the subject is Rogers' book "Theory of Recursive Functions and Effective Computability". Recursive ordinals are introduced in Chapter 11 and Analytic Hierarchy in Chapter 16. It appears that both sets mentioned in question are indeed reducible to one another. So the result from wikipedia indeed refers to both.

• Rogers is fine, especially for the introductory stuff but IMO he tries to pack so much more advanced material in it gets confusing if you don't already know the material. On the other hand this might just be a side-effect of some of the notation in Rogers falling out of favor. In any case I second Carl's recommendation of Higher Recursion Theory. – Peter Gerdes Nov 21 '12 at 10:53