Hostname: page-component-745bb68f8f-d8cs5 Total loading time: 0 Render date: 2025-01-10T05:48:09.318Z Has data issue: false hasContentIssue false
  • English
  • Français

A note on degrees of subsets1

Published online by Cambridge University Press:  12 March 2014

Robert I. Soare
Robert I. Soare*
Affiliation:
University of Illinois at Chicago Circle
Get access Rights & Permissions [Opens in a new window]

Extract

In [2] we constructed an infinite set of natural numbers containing no subset of higher (Turing) degree. Since it is well known that there are nonrecursive sets (e.g. sets of minimal degree) containing no nonrecursive subset of lower degree, it is natural to suppose that these arguments may be combined, but this is false. We prove that every infinite set must contain a nonrecursive subset of either higher or lower degree.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 34 , Issue 2 , 25 July 1969 , pp. 256
Copyright
Copyright © Association for Symbolic Logic 1969

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

This work was supported by National Science Foundation Grant GP 8866.

References

[1] Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[2] Soare, R. I., Sets with no subset of higher degree, this Journal , vol. 34, (1969), pp. 53–56.Google Scholar