Complejidad del conjunto de ordinales computables

Question

Según http://en.wikipedia.org/wiki/Analytical_hierarchy

El conjunto de todos los números naturales que son índices de ordinales computables es un $\Pi^1_1$ conjunto que no es $\Sigma^1_1$ .

Sin embargo, "el conjunto de todos los números naturales que son índices de ordinales computables" puede interpretarse como

• el conjunto de índices de relaciones binarias recursivas que ordenan bien algún subconjunto de números naturales;
• Kleene's $\cal O$ .

¿A qué interpretación se refiere el resultado anterior? Lo ideal es que las dos interpretaciones sean reducibles entre sí, y que el resultado se refiera a ambas, pero no me resulta evidente. Y también, ¿dónde puedo leer más sobre este resultado?

Gracias de antemano.

Answer 1

Dado que esta pregunta no ha obtenido ninguna respuesta de los expertos, voy a publicar aquí mis conclusiones (por si alguien se encuentra con la pregunta).

La referencia estándar del tema es el libro de Rogers "Theory of Recursive Functions and Effective Computability". Los ordinales recursivos se introducen en el capítulo 11 y la jerarquía analítica en el capítulo 16. Parece que los dos conjuntos mencionados en cuestión son efectivamente reducibles entre sí. Así que el resultado de la wikipedia se refiere efectivamente a ambos.

Answer 2

Véase el artículo de Wikipedia sobre Kleene's $\mathcal{O}$ :

De hecho, $\mathcal{O}$ es $\Pi^1_1$ -completa y cada $\Sigma^1_1$ subconjunto de $\mathcal{O}$ está efectivamente acotado en $\mathcal{O}$ (un resultado de Spector).

Creo que también funciona para otros bonito de los ordinales recursivos, pero no estoy seguro de que se mantenga para todas las indexaciones, por ejemplo, no está claro si esto se mantiene si la indexación no es universal (es decir, podemos traducir efectivamente las nociones de $\mathcal{O}$ a ella).