Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Ordinal récursif
Résumé
En mathématiques, en particulier en calculabilité et en théorie des ensembles, un ordinal 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 .
Il est facile de vérifier que 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é . L'ordinal Church-Kleene est un ordinal limite. Un ordinal est calculable si et seulement s'il est plus petit que . 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, est dénombrable.
Les ordinaux calculables sont exactement les ordinaux qui ont une notation ordinale dans le O de Kleene.
Hiérarchie arithmétique
Grand ordinal dénombrable
Analyse ordinale
Notation ordinale
Hartley Rogers Jr. La théorie des fonctions récursives et la calculabilité effective, 1967. Réimprimé en 1987, MIT Press, (livre broché),
Gerald Sacks théorie de la récursivité supérieure . Perspectives en logique mathématique, Springer-Verlag, 1990.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.