Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-25T06:24:49.331Z Has data issue: false hasContentIssue false

Analytic inductive definitions

Published online by Cambridge University Press:  12 March 2014

Douglas Cenzer*
Affiliation:
University of Florida, Gainesville, Florida 32601

Extract

An operator Γ mapping P(ω) to itself is inductive if Γ(A) ⊇ A for all A. For such an inductive operator Γ we define {Γα : α ∈ ORD} by letting Γ = ⌀, Γα + 1 = Γ(Γα ) for all α, and Γβ = ⋃{Γα : α < β} for limit ordinals β. The closure ordinal ∣Γ∣ of Γ is the least ordinal α such that Γα+1 = Γα and the closure is Γ∣Γ∣.

Let be a class of operators over the natural numbers. The closure ordinal ∣∣ of is the supremum of {∣Γ∣: Γ is an inductive operator and }. The closure algebra generated by is {Aω: A is 1-1 reducible to for some inductive operator }. The inductive algebra generated by is {Γα : Γ is an inductive operator in and α < ∣Γ∣}.

For AP(ω), is the supremum of the ordinals of well-orderings recursive in A. For , let be the supremum of . For example, it is well known that ω() = ω(∆1 0 = ω 1, ω1 1) = ω 1 and ωn 1) = δn 1 for n > 1 (the latter by definition).

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1974

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Cenzer, D., Ordinal recursion and inductive definitions, Generalized recursion theory ( Oslo, 1972 ) (Fenstad, J. and Hinman, P., Editors), North-Holland, Amsterdam (to appear).Google Scholar
[2] Cenzer, D., The boundedness principle in ordinal recursion, Fundamenta Mathematicae (to appear).Google Scholar
[3] Kondo, M., Sur l'uniformization des complementaires analytiques et les ensembles projectifs de la seconde classe, Japanese Journal of Mathematics, vol. 15 (1938), pp. 197230.Google Scholar
[4] Putnam, H., On hierarchies and systems of notations, Proceedings of the American Mathematical Society, vol. 15 (1964), pp. 4450.Google Scholar
[5] Richter, W., Recursively Mahlo ordinals and inductive definitions, Logic Colloquium '69, North-Holland, Amsterdam, 1971, pp. 273288.CrossRefGoogle Scholar