# 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