Hostname: page-component-77c89778f8-sh8wx Total loading time: 0 Render date: 2024-07-17T04:36:47.303Z Has data issue: false hasContentIssue false
  • English
  • Français

A theorem on minimal degrees

Published online by Cambridge University Press:  12 March 2014

J. R. Shoenfield
J. R. Shoenfield*
Affiliation:
Stanford University
Get access Rights & Permissions [Opens in a new window]

Extract

In their original paper on degrees [3], Kleene and Post showed that there is a degree between 0 and 0′. Later, Friedberg [1] and Muchnik [4] showed that there is a recursively enumerable degree between 0 and 0′. Since then, this phenomenon has been repeated several times: a result has been proved for degrees, and then, after considerable additional effort, it has been proved for recursively enumerable degrees.

There are some obvious respects in which that set of all degrees differs from the set of recursively enumerable degrees; e.g., the former is uncountable and has no largest member.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 31 , Issue 4 , December 1966 , pp. 539 - 544
Copyright
Copyright © Association for Symbolic Logic 1997

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

References

[1]Friedberg, Richard M., Two recursively enumerable sets of incomparable degrees of unsolvability, Proceedings of the National Academy of Science, Vol. 43 (1957), pp. 236–238.CrossRefGoogle ScholarPubMed
[2]Friedberg, Richard M., The fine structure of degrees of unsolvability of recursively enumerable sets, Summaries of Cornell University Summer Institute for Symbolic Logic (1957), pp. 404–406.Google Scholar
[3]Kleene, S. C. and Post, Emil L., The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics, vol. 59 (1954), pp. 379–407.CrossRefGoogle Scholar
[4]Muchnik, A. A., Negative answer to the problem of reducibility of the theory of algorithms (in Russian), Doklady Akad. Nauk SSSR, vol. 108 (1956), pp. 194–197.Google Scholar
[5]Muchnik, A. A., Solution of Post's reduction problem and of certain problems in the theory of algorithms (in Russian), Trudy Moskow Mat. Obsc., vol. 7 (1958), pp. 391–405.Google Scholar
[6]Sacks, Gerald E., Degrees of Unsolvability, Princeton University Press, 1963.Google Scholar
[7]Yates, C. E. M., A minimal pair of recursively enumerable sets, to appear.Google Scholar