Hostname: page-component-6898cfcb55-zsp5v Total loading time: 0 Render date: 2026-11-12T01:20:24.830Z 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 A ∈ P(ω), 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).

Information

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.)

Article purchase

Temporarily unavailable