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 n th. 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.