Published online by Cambridge University Press: 12 March 2014
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).
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.