Premium
A cohesive set which is not high
Author(s) -
Jockusch Carl,
Stephan Frank
Publication year - 1993
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19930390153
Subject(s) - mathematics , set (abstract data type) , computer science , programming language
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.