In:
Journal of Symbolic Logic, Cambridge University Press (CUP), Vol. 41, No. 3 ( 1976-09), p. 695-696
Abstract:
In [3], Martin computed the degrees of certain classes of RE sets. To state the results succinctly, some notation is useful. If A is a set (of natural numbers), dg ( A ) is the (Turing) degree of A . If A is a class of sets, dg ( A ) = { dg (A ) : A ∈ A ). Let M be the class of maximal sets, HHS the class of hyperhypersimple sets, and DS the class of dense simple sets. Martin showed that dg ( M ), dg ( HHS ), and dg ( DS ) are all equal to the set H of RE degrees a such that a ′ = 0″. Let M * be the class of coinfinite RE sets having no superset in M ; and define HHS * and DS * similarly. Martin showed that dg ( DS *) = H. In [2], Lachlan showed (among other things) that dg ( M *)⊆ K , where K is the set of RE degrees a such that a ″ 〉 0″. We will show that K ⊆ dg ( HHS *). Since maximal sets are hyperhypersimple, this gives dg ( M *) = dg ( HHS *) = K . These results suggest a problem. In each case in which dg(A) has been calculated, the set of nonzero degrees in dg(A) is either H or K or the empty set or the set of all nonzero RE degrees. Is this always the case for natural classes A ? Natural here might mean that A is invariant under all automorphisms of the lattice of RE sets; or that A is definable in the first-order theory of that lattice; or anything else which seems reasonable.
Type of Medium:
Online Resource
ISSN:
0022-4812
,
1943-5886
DOI:
10.1017/S0022481200051252
Language:
English
Publisher:
Cambridge University Press (CUP)
Publication Date:
1976
detail.hit.zdb_id:
2010607-5
SSG:
5,1
SSG:
17,1
Permalink