Utilizando el emparejamiento, reemplazo y la unión (para tomar límites) se pueden producir efectivamente algunos ordinales recursivos a partir de $\omega$ como $\omega+1$ , $\omega\cdot 2$ , $\omega^2$ , $\omega^\omega$ , $\varepsilon_0$ , $\varphi_{\gamma}(\beta)$ , $\Gamma_{\alpha}$ etc. Me pregunto hasta dónde podemos llegar de esta manera, es decir, construyendo sucesivamente ordinales a partir de los ya construidos aplicando el emparejamiento, la unión y la sustitución un número finito de veces. ¿Podemos agotar $\omega_1^{CK}$ ¿así? Si no, ¿existe una enumeración recursiva de $\omega_1^{CK}$ ?
Respuesta
¿Demasiados anuncios?
ManuelSchneid3r
Puntos
116
No existe una enumeración recursiva de $\omega_1^{CK}$ . De hecho, no hay hiperaritmética (o incluso $\Sigma^1_1$ ) manera de presentar $\omega_1^{CK}$ ¡! Esto fue demostrado por Spector .
Más generalmente, si un grado de Turing ${\bf a}$ calcula una copia de un ordinal $\alpha$ y ${\bf a}$ es hiperaritmético con respecto a ${\bf b}$ entonces ${\bf b}$ también calcula una copia de $\alpha$ . Esta propiedad general se denomina "hiperaritmética-es-recursiva", y resulta tener sorprendentes conexiones con la teoría de modelos (al menos, con su vertiente más teórica de conjuntos). Decimos que una clase de estructuras $\mathbb{K}$ satisface la hiperaritmética-es-recursiva si siempre que un grado de Turing ${\bf a}$ es hiperaritmético en ${\bf b}$ y calcula una copia de $\mathcal{A}$ entonces ${\bf b}$ también calcula una copia de $\mathcal{A}$ para todos $\mathcal{A}\in\mathbb{K}$ . Montalbán mostró que una teoría de primer orden $T$ es un contraejemplo de La conjetura de Vaught si y sólo si $T$ satisface "hyperarithmetic-is-recursive en un cono ," un ligero debilitamiento de "hiperaritmética-es-recursiva".
Sin embargo, con respecto a la primera parte de tu pregunta, no me queda del todo claro qué proceso tienes en mente; concretamente, cómo se permite utilizar la sustitución. En el sentido ingenuo, podemos llegar automáticamente a cualquier ordinal contable que tenga una copia (= ordenación de $\omega$ con el tipo de orden apropiado) definible en la teoría de conjuntos con una sola aplicación de sustitución. $\omega_1^{CK}$ y mucho más, entra en esta categoría. He aquí una ordenación explícita y definible de $\omega$ con el tipo de pedido $\omega_1^{CK}$ :
-
Definimos Conjunto de Kleene $\mathcal{O}$ de las notaciones ordinales como siempre.
-
Ahora definimos una relación $\triangleleft$ en $\mathcal{O}$ de la siguiente manera: $m\triangleleft n$ si $m$ es un índice para un ordinal que es menor que el ordinal $n$ es un índice para.
-
Por último, dejamos que $$M=\{m\in\mathcal{O}: \forall n\in\mathcal{O}(n<m\implies (m\triangleleft n\vee n\triangleleft m))\}$$ sea el conjunto de mínimo índices para los ordinales. Entonces $M$ ordenado por $\triangleleft$ tiene el tipo de orden $\omega_1^{CK}$ .
-
Ahora bien, como $M$ no consiste en realidad en todos los números naturales, no hemos terminado técnicamente, pero esto se arregla fácilmente: dejemos que $M=\{m_0<m_1<m_2< ...\}$ y que $\triangleleft'$ se define por $x\triangleleft'y\iff m_x\triangleleft m_y$ . Entonces $\triangleleft'$ es una buena ordenación de $\omega$ con el tipo de pedido $\omega_1^{CK}$ . Y esto ni siquiera araña la superficie de los ordinales que podemos construir.
Así que en el proceso que describes, probablemente quieras limitar la atención de alguna manera a las aplicaciones "efectivas" de la sustitución, y no me queda del todo claro qué significa esto.
Dicho esto, puede que le interese tangencialmente este documento de Arai en el que calcula esencialmente un límite para el $L$ -de reales (equivalentemente, conjuntos hereditariamente contables) cuya existencia se puede "demostrar" en ZFC+V=L en un sentido preciso. Creo que esto se sobrepasa lo que quieres por un gran margen, tanto porque se permite el juego de poderes como porque no hay una imagen de "construcción finita" (por lo que puedo decir), pero aún así podrías encontrarlo limpio.
