Abstract: This paper investigates the problem of extending the recursion theoretic construction of a minimal degree to the Kripke [2]-Platek [5] recursion theory on the ordinals less than an admissible ordinal α , a theory derived from the Takeuti [11] notion of a recursive function on the ordinal numbers. As noted in Sacks [7] when one generalizes the recursion theoretic definition of relative recursiveness to α -recursion theory for α > ω the two usual definitions give rise to two different notions of reducibility. We will show that whenever α is either a countable admissible or a regular cardinal of the constructible universe there is a subset of α whose degree is minimal for both notions of reducibility. The result is an excellent example of a theorem of ordinary recursion theory obtainable via two different constructions, one of which generalizes, the other of which does not. The construction which cannot be lifted to α -recursion theory is that of Spector [10]. We sketch the reasons for this in §3.
Publication Year: 1973
Publication Date: 1973-03-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 6
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot