In the mathematical field of computability theory, a PA degree is a Turing degree that computes a complete extension of Peano arithmetic (Jockusch 1987).
These degrees are closely related to fixed-point-free (DNR) functions, and have been thoroughly investigated in recursion theory.
denotes the computable function with index (program) e in some standard numbering of computable functions, and
denotes the eth computable function using a set B of natural numbers as an oracle.
This relationship is denoted A ≤T B; the relation ≤T is a preorder.
A Turing degree is a collection of sets of natural numbers, such that any two sets in the collection are Turing equivalent.
A completion of Peano arithmetic is a set of formulas in the language of Peano arithmetic, such that the set is consistent in first-order logic and such that, for each formula, either that formula or its negation is included in the set.
Once a Gödel numbering of the formulas in the language of PA has been fixed, it is possible to identify completions of PA with sets of natural numbers, and thus to speak about the computability of these completions.
(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<ω.
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).
sets are complete (i.e. Turing equivalent to