Extensions of the constructive ordinals

Publisher Website
Google Scholar
Abstract
Kleene [5] mentions two ways of extending the constructive ordinals. The first is by relativizing the setOof notations for the constructive ordinals, using fundamental sequences which are partial recursive inO. In this way we obtain the setOOwhich provides notations for the ordinals less than ω1O. Continuing the process, the sequenceO,OO,, … and the corresponding ordinalsare obtained. A second possibility is to define (constructive) higher number classes in which partial recursive functions are used at limit ordinals to provide an “accessibility” mapping from a previously defined number class. The relationship between the ordinals obtained by the two methods of extension has been an open problem. Methods developed in this article are used to show that the two ways of extending the constructive ordinals are equivalent, provided the sets of notations for the higher number classes satisfy certain natural conditions. Equivalence is obtained, not only with respect to ordinals, but also with respect to the forms of the sets of notations for the higher number classes. Specifically, the fundamental fact that the sets of notations for the constructive ordinals are complete Π11sets generalizes to suitably defined higher number classes. As an application we prove that the ordinals of the Addison and Kleene [1] constructive third number class are exactly the ordinals less than ω1Oand the setof notations for their third number class is recursively isomorphic toOO.

This publication has 9 references indexed in Scilit: