Title: Sets which do not have subsets of every higher degree
Abstract: Let A be a subset of ω, the set of natural numbers. The degree of A is its degree of recursive unsolvability. We say that A is rich if every degree above that of A is represented by a subset of A . We say that A is poor if no degree strictly above that of A is represented by a subset of A . The existence of infinite poor (and hence nonrich) sets was proved by Soare [9]. T heorem 1. Suppose that A is infinite and not rich. Then every hyperarith-metical subset H of ω is recursive in A . In the special case when H is arithmetical, Theorem 1 was proved by Jockusch [4] who employed a degree-theoretic analysis of Ramsey's theorem [3]. In our proof of Theorem 1 we employ a similar, degree-theoretic analysis of a certain generalization of Ramsey's theorem. The generalization of Ramsey's theorem is due to Nash-Williams [6]. If A ⊆ ω we write [ A ] ω for the set of all infinite subsets of A . If P ⊆ [ω] ω we let H(P) be the set of all infinite sets A such that either [ A ] ω ⊆ P = ∅. Nash-Williams' theorem is essentially the statement that if P ⊆ [ω] ω is clopen (in the usual, Baire topology on [ω] ω ) then H(P) is nonempty. Subsequent, further generalizations of Ramsey's theorem were proved by Galvin and Prikry [1], Silver [8], Mathias [5], and analyzed degree-theoretically by Solovay [10]; those results are not needed for this paper.
Publication Year: 1978
Publication Date: 1978-03-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 23
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot