is defined to be a PA degree if there is a set of natural numbers in the degree that computes a completion of Peano Arithmetic. (This is equivalent to the proposition that every set in the degree computes a completion of PA.) Because there are no computable completions of PA, the degree 0 consisting of the computable sets of natural numbers is not a PA degree. Because PA is an effective first-order theory, the completions of PA can be characterized as the infinite paths through a particular computable subtree of 2<ω. Thus the PA degrees are exactly the degrees that compute an infinite path through this tree. Properties The PA degrees are upward closed in the Turing degrees: if a is a PA degree and a ≤T b then b is a PA degree. The Turing degree 0‘, which is the degree of the halting problem, is a PA degree. There are also PA degrees that are not above 0‘. For example, the low basis theorem implies that there is a low PA degree. On the other hand, Antonín Kučera has proved that there is a degree less than 0‘ that computes a DNR function but is not a PA degree (Jockusch 1989:197). Carl Jockusch and Robert Soare (1972) proved that the PA degrees are exactly the degrees of DNR2 functions. By definition, a degree is PA if and only if it computes a path through the tree of completions of Peano arithmetic. A stronger property holds: a degree a is a PA degree if and only if a computes a path through every infinite computable subtree of 2<ω (Simpson 1977). Arslanov's completeness criterion M. M. Arslanov gave a characterisation of which c.e. sets are complete (i.e. Turing equivalent to ). For a c.e. set , if and only if computes a DNR function. In particular, every PA degree is DNR2 and hence DNR, so is the only c.e. PA degree. See also Basis theorem (computability) Kőnig's lemma References Carl Jockusch (1987), "Degrees of functions with no fixed points", Logic Colloquium '87, Fenstad, Frolov, and Hilpinen, eds., North-Holland, Carl Jockusch and Robert Soare (1972), "Π01 classes and degrees of theories", Transactions of the American Mathematical Society, v. 173, pp. 33–56. Stephen G. Simpson (1977), "Degrees of unsolvability: a survey of results", Handbook of Mathematical Logic, Barwise (ed.), North-Holland, pp. 631–652. Computability theory