A criterion for completeness of degrees of unsolvability

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⁽ⁿ⁾ there are an infinity of mutually incomparable degrees each incomparable with a′, …, a⁽ⁿ⁻¹⁾. 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.