Article contents
Π11 Sets, ω-Sets, and metacompleteness
Published online by Cambridge University Press: 12 March 2014
Extract
An ω-set is a subset of the recursive ordinals whose complement with respect to the recursive ordinals is unbounded and has order type ω. This concept has proved fruitful in the study of sets in relation to metarecursion theory. We prove that the metadegrees of the sets coincide with those of the meta-r.e. ω-sets. We then show that, given any set, a metacomplete set can be found which is weakly metarecursive in it. It then follows that weak relative metarecursiveness is not a transitive relation on the sets, extending a result of G. Driscoll [2, Theorem 3.1]. Coincidentally, we discuss the notions of total and complete regularity. Finally, we solve Post's problem for the transitive closure of weak relative metarecursiveness. We recommend the reader look at pp. 324–328 of the fundamental article [6] of Kreisel and Sacks before proceeding. He will find there a proof of the following very basic fact: a subset of the integers is iff it is metarecursively enumerable (metafinite).
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 1969
Footnotes
Most of the material in this paper is taken from the author's Ph.D. thesis (Cornell University, 1966), supervised by Gerald E. Sacks and supported by a N.S.F. Graduate Fellowship. The author is beholden to Sacks for developing and popularizing the beautiful intricacies of metarecursion theory. This work was also supported by NSF Contract GP 6897.
References
- 4
- Cited by