Ordinal computable

En matemáticas , específicamente en computabilidad y teoría de conjuntos , se dice que un ordinal es computable o recursivo si existe un buen ordenamiento computable de un subconjunto computable de los números naturales que tienen el tipo de orden . ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

Es fácil comprobar que es computable. El sucesor de un ordinal computable es computable y el conjunto de todos los ordinales computables es cerrado hacia abajo. ${\displaystyle \omega }$

El supremo de todos los ordinales computables se denomina ordinal de Church-Kleene , el primer ordinal no recursivo, y se denota por . El ordinal de Church-Kleene es un ordinal límite . Un ordinal es computable si y solo si es menor que . Dado que solo hay un número contable de relaciones computables, también hay un número contable de ordinales computables. Por lo tanto, es contable. ${\displaystyle \omega _{1}^{\mathsf {CK}}}$ ${\displaystyle \omega _{1}^{\mathsf {CK}}}$ ${\displaystyle \omega _{1}^{\mathsf {CK}}}$

Los ordinales computables son exactamente los ordinales que tienen una notación ordinal en Kleene ${\displaystyle {\mathcal {O}}}$ .

Véase también

• Jerarquía aritmética
• Ordinal contable grande
• Análisis ordinal
• Notación ordinal

Referencias

• Hartley Rogers Jr. La teoría de funciones recursivas y computabilidad efectiva , 1967. Reimpreso en 1987, MIT Press, ISBN  0-262-68052-1 (libro de bolsillo), ISBN 0-07-053522-1 
• Gerald Sacks , Teoría de la recursión superior . Perspectivas en lógica matemática, Springer-Verlag, 1990. ISBN 0-387-19305-7