En matemáticas , específicamente computabilidad y teoría de conjuntos , un ordinal se dice que es computable o recursivo si hay un buen ordenamiento computable de un subconjunto de los números naturales que tienen el tipo de orden .
Es fácil comprobar que es computable. El sucesor de un ordinal computable es computable y el conjunto de todos los ordinales computables se cierra hacia abajo.
El supremo de todos los ordinales computables se llama ordinal de Church-Kleene y se denota por. El ordinal Church-Kleene es un ordinal límite . Un ordinal es computable si y solo si es menor que. Dado que solo hay muchas relaciones computables numerables, también hay solo muchos ordinales computables numerables . Por lo tanto, es contable.
Los ordinales computables son exactamente los ordinales que tienen una notación ordinal en Kleene.
Ver también
Referencias
- Hartley Rogers Jr. The Theory of Recursive Functions and Effective Computability , 1967. Reimpreso en 1987, MIT Press, ISBN 0-262-68052-1 (rústica), ISBN 0-07-053522-1
- Teoría de la recursividad superior de Gerald Sacks . Perspectivas en lógica matemática, Springer-Verlag, 1990. ISBN 0-387-19305-7