Ordinal récursif

terme

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.

Articles connexes

modifier

Références

modifier