Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-17T00:42:20.812Z Has data issue: false hasContentIssue false

Π11 Sets,ω-Sets, and metacompleteness

Published online by Cambridge University Press:  12 March 2014

James C. Owings Jr.*
Affiliation:
University of Maryland

Extract

An ω-set is a subset of the recursive ordinals whosecomplement with respect to the recursive ordinals is unbounded and has ordertype ω. This concept has proved fruitful in the study of sets in relation to metarecursion theory. We provethat the metadegrees of the setscoincide with those of the meta-r.e. ω-sets. We then show that, given any set, ametacomplete set can befound which is weakly metarecursive in it. It then follows that weakrelative metarecursiveness is not a transitive relation on the sets,extending a result of G. Driscoll [2, Theorem 3.1]. Coincidentally, wediscuss the notions of total and complete regularity. Finally, we solvePost's problem for the transitive closure of weak relativemetarecursiveness. We recommend the reader look at pp. 324–328 of thefundamental article [6] of Kreisel and Sacks before proceeding. He will findthere a proof of the following very basic fact: a subset of the integers is iff it ismetarecursively enumerable (metafinite).

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1969

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