A criterion for completeness of degrees of unsolvability
- 1 June 1957
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 22 (2) , 159-160
- https://doi.org/10.2307/2964177
Abstract
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.Keywords
This publication has 3 references indexed in Scilit:
- TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)Proceedings of the National Academy of Sciences, 1957
- Arithmetical predicates and function quantifiersTransactions of the American Mathematical Society, 1955
- The Upper Semi-Lattice of Degrees of Recursive UnsolvabilityAnnals of Mathematics, 1954