Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-22T20:32:45.405Z Has data issue: false hasContentIssue false
  • English
  • Français

A criterion for completeness of degrees of unsolvability

Published online by Cambridge University Press:  12 March 2014

Richard Friedberg
Richard Friedberg*
Affiliation:
Harvard University
Get access Rights & Permissions [Opens in a new window]

Extract

Kleene and Post [2] have shown that between each degree a and its completion a′ there are an infinity of mutually incomparable degrees of unsolvability, and that between a and its nth. completion a(n) there are an infinity of mutually incomparable degrees each incomparable with a′, …, a(n−1). They have left open the following questions: whether there exist complete degrees in similar profusion; whether indeed there exist incomparable complete degrees at all; and whether certain degrees, such as a(ω) ([2] p. 401), are complete. All these questions are answered affirmatively by the corollary of the present paper, which states that every degree greater than or equal to 0′ is complete. Since every complete degree is already known to be greater than or equal to 0′, it follows from the present paper that being greater than or equal to 0′ is both a necessary and a sufficient condition for completeness.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 22 , Issue 2 , June 1957 , pp. 159 - 160
Copyright
Copyright © Association for Symbolic Logic 1957

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

BIBLIOGRAPHY

[1]Friedberg, Richard, Two recursively enumerable sets of incomparable degrees of unsolvability, abstract in Bulletin of the American Mathematical Society, vol. 62(1956), p. 320.Google Scholar
[2]Kleene, S. C. and Post, E. L., The upper semi-lattice of degrees of recursive unsolvability, Annals of mathematics, vol. 59 (1954), pp. 379–407.CrossRefGoogle Scholar
[3]Kleene, S. C., Arithmetical predicates and function quantifiers, Transactions of the American Mathematical Society, vol. 79 (1955), pp. 312–340.CrossRefGoogle Scholar