Es el límite de una secuencia recursiva de recursivas ordinales en sí mismo un recursiva ordinal? Si es así, hay una buena prueba de ello?
Respuesta
¿Demasiados anuncios?
wtm
Puntos
140
Voy a elegir para responder a su respuesta a Andres por encima.
A raíz de lo que significan por una secuencia recursiva, vamos a $(\omega^{ck}_1,<)$ ser la cadena de dado recursiva ordinales $\alpha_i<\beta$, $i \in \mathbb N$ con $\beta$ un límite ordinal. Tendremos $\omega^{ck}_1$ ser el supremum de esta secuencia, donde $\omega^{ck}_1$ es el menos no recursivo, ordinal de la Iglesia de Kleene (CK). Si entiendo correctamente, tendremos $\alpha_1 < \alpha_2 < \dots < \alpha_k$ como estrictamente creciente computably enumerable de la secuencia con $\alpha+1 \neq \beta$ como se pide.
Ahora le damos un computable (recursivo) definición de sucesor ordinal límite y ordinal. 1) Definir el $|2^i|= \alpha+1$ sucesor ordinal, de tal manera que tendremos $\alpha <_e \alpha +1$ debido a la orden lineal y $i$ es el índice de una función parcial $\phi_e(i,n)=1$ si $\alpha <_e \alpha+1$ $0$ si de lo contrario. Puedo tomar como un hecho que el fin de la relación $<_e$ es computably enumerable, pero no computable (es decir, en el rango de una función recursiva parcial). También vale la pena mencionar que el $<_e$ está bien fundada, o no infinitamente descendente y, por tanto, la cadena de $(\omega^{ck}_1,<)$ tiene un mínimo elemento.
2) Para limitar, vamos a $|3 * 5^e| = lim_k|i_k| = \beta_e$ donde $e$ es el código numeral para un parcial de función recursiva $\psi_e$ la enumeración de cada una de las $\alpha_i <_e \beta^e$. Sin embargo, desde la $<_e$ es computably enumerable ($xRy$ en el rango de una función recursiva parcial para $R$ un buen orden) a través de la orden lineal, podemos utilizar la definición de la computables límite ordinal $\beta$ a demostrar que está acotada arriba por la Iglesia-Kleene ordinal, bien fundadas, como un límite para $\forall \alpha(\alpha < \beta)$, y por lo tanto en sí mismo un recursiva ordinal.
