Minimal upper bounds for ascending sequences of α-recursively enumerable degrees

E-ISSN： 1943-5886|41|1|250-260

ISSN： 0022-4812

Source： The Journal of Symbolic Logic, Vol.41, Iss.1, 1976-03, pp. : 250-260

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

Let a be an admissible ordinal and let ∧ ≤ α be a limit ordinal. A sequence of a-r.e. degrees is said to be ascending, simultaneous and of length ∧ if (i) there is an α-recursive function t: α × ∧ → α such that, for all ϒ < ∧, A _ϒ = {t(σ, ϒ)∣ σ < α} is of degree a _ϒ; (ii) if ϒ < ⊤ < ∧, then a _ϒ ≤_α a _τ and (iii) for all ϒ < ∧, there is a ⊤ > ϒ with a _ϒ, >_α a _ϒ. Lerman [4] showed that such an exists for every ∧ ≤ α. An upper bound a of is an α-r.e. degree in which every element of is α-recursive. a is minimal if there is no α-r.e. degree b <_α a which is also an upper bound of . Sacks [6] proved that every ascending sequence of simultaneously ω-r.e. degrees of length ω cannot have 0_ω′, the complete ω-r.e. degree, as a minimal upper bound. In contrast, Cooper [2] showed that there exists an ascending sequence of simultaneously ω-r.e. degrees of length to having a minimal upper bound which is an ω-r.e. degree. In this paper we investigate the behavior of ascending sequences of simultaneously α-r.e. degrees for admissible ordinals α > ω. Call α Σ_∞-admissibIe if it is Σ_n-nadmissible for all n. Let Φ(∧) say: No ascending sequence of simultaneously α-r.e. degrees of length ∧ can have 0_α′, the complete α-r.e. degree, as a minimal upper bound. Our main result in this paper is: