A cohesive set which is not high

✍ Scribed by Carl Jockusch; Frank Stephan

• Publisher: John Wiley and Sons
• Year: 1993
• Tongue: English
• Weight: 1014 KB
• Volume: 39
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.19930390153

✦ Synopsis

Abstract

We study the degrees of unsolvability of sets which are cohesive (or have weaker recursion‐theoretic “smallness” properties). We answer a question raised by the first author in 1972 by showing that there is a cohesive set A whose degree a satisfies a' = 0″ and hence is not high. We characterize the jumps of the degrees of r‐cohesive sets, and we show that the degrees of r‐cohesive sets coincide with those of the cohesive sets. We obtain analogous results for strongly hyperimmune and strongly hyperhyperimmune sets in place of r‐cohesive and cohesive sets, respectively. We show that every strongly hyperimmune set whose degree contains either a Boolean combination of ∑2 sets or a 1‐generic set is of high degree. We also study primitive recursive analogues of these notions and in this case we characterize the corresponding degrees exactly. MSC: 03D30, 03D55.