Complexity of the set of computable ordinals

Question

According to http://en.wikipedia.org/wiki/Analytical_hierarchy

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?

Thank you in advance.

Answer 1

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).

Answer 2

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.