Ordinal récursif

En mathématiques, en particulier en calculabilité et en théorie des ensembles, un ordinal $\alpha$ est dit calculable ou récursif s'il existe un bon ordre calculable d'un sous-ensemble calculable des nombres naturels ayant le type d'ordre $\alpha$.

Il est facile de vérifier que $\omega$ est calculable. On montre également que le successeur d'un ordinal calculable est calculable, et que l'ensemble de tous les ordinaux calculables est fermé vers le bas.

La borne supérieure de tous les ordinaux calculables est appelé l'ordinal de Church-Kleene, le premier ordinal non récursif, et noté $\omega _{1}^{CK}$. L'ordinal Church-Kleene est un ordinal limite. Un ordinal est calculable si et seulement s'il est plus petit que $\omega _{1}^{CK}$. Puisqu'il n'y a qu'un nombre dénombrable de relations calculables, il n'y a aussi qu'un nombre dénombrable d'ordinaux calculables. Ainsi, $\omega _{1}^{CK}$ est dénombrable.

Les ordinaux calculables sont exactement les ordinaux qui ont une notation ordinale dans le O de Kleene.

Articles connexes

• Hiérarchie arithmétique
• Grand ordinal dénombrable
• Analyse ordinale
• Notation ordinale

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Computable ordinal » (voir la liste des auteurs).

• Hartley Rogers Jr. La théorie des fonctions récursives et la calculabilité effective, 1967. Réimprimé en 1987, MIT Press, (ISBN 0-262-68052-1) (livre broché), (ISBN 0-07-053522-1)
• Gerald Sacks théorie de la récursivité supérieure . Perspectives en logique mathématique, Springer-Verlag, 1990. (ISBN 0-387-19305-7)