Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-31T18:54:07.191Z Has data issue: false hasContentIssue false
  • English
  • Français

Degrees of classes of RE sets1

Published online by Cambridge University Press:  12 March 2014

J. R. Shoenfield
J. R. Shoenfield*
Affiliation:
Duke University, Durham North Carolina 27706
Get access Rights & Permissions [Opens in a new window]

Extract

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
Research Article
Information
The Journal of Symbolic Logic , Volume 41 , Issue 3 , September 1976 , pp. 695 - 696
Copyright
Copyright © Association for Symbolic Logic 1976

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.)

Footnotes

1

The author would like to thank Carl Jockusch and Tony Martin for comments on a preliminary version of this paper.

References

REFERENCES

[1] Dekker, J. C. E., A theorem on hypersimple sets, Proceedings of the American Mathematical Society, vol. 5 (1954), pp. 791–796.CrossRefGoogle Scholar
[2] Lachlan, A. H., Degrees of recursively enumerable sets which have no maximal supersets, this Journal, vol. 33 (1968), pp. 431–443.Google Scholar
[3] Martin, D. A., Classes of recursively enumerable sets and degrees of unsolvability, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 12 (1966), pp. 295–310.CrossRefGoogle Scholar
[4] Robinson, R. M., A dichotomy of the recursively enumerable sets, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 14 (1968), pp. 339–356.CrossRefGoogle Scholar