PA degrees · Computability Theory

Some sets compute a member of every non-empty $\Pi^0_1$ class: they can solve, uniformly, every problem whose solutions form a $\Pi^0_1$ class. These sets are characterized by a simple diagonal property — they compute a $\{0, 1\}$ -valued function that differs from every computable function on the diagonal — and, historically, by their ability to compute a complete consistent extension of Peano arithmetic. Their degrees are the PA degrees. They are not necessarily complete, and not even necessarily above any given non-computable set: by the basis theorems, there are low PA degrees.

4.1 Definition and characterizations

Definition 4.1.#

A set $X$ is of PA degree, or PA, if $X$ computes a member of $\mathrm{DNC}_2$ , that is, a function $f : \nat \to \{0, 1\}$ with $f(e) \neq \Phi_e(e)$ for every $e$ such that $\Phi_e(e)\converge$ .

The class of PA sets is closed upward under Turing reducibility. The halting set is PA: the function $f(e) = 1$ if $\Phi_e(e)\converge = 0$ , and $f(e) = 0$ otherwise, is computable in $\emptyset'$ and belongs to $\mathrm{DNC}_2$ .

Theorem 4.2.#

For every set $X$ , the following are equivalent:

$X$ is PA;
for every pair of disjoint c.e. sets $A$ and $B$ , $X$ computes a set $C$ separating them: $A \subseteq C$ and $C \cap B = \emptyset$ ;
$X$ computes a member of every non-empty $\Pi^0_1$ class.

Proof of Theorem 4.2.

(1 ⇒ 2) Let $f \leq_T X$ be a member of $\mathrm{DNC}_2$ , and $A$ , $B$ disjoint c.e. sets. By the parameter form of SMN, there is a computable $q$ such that the program $q(n)$ , on any input, enumerates $A$ and $B$ , outputs $0$ if $n$ appears in $A$ , and $1$ if $n$ appears in $B$ ; it diverges if $n$ belongs to neither. So $\Phi_{q(n)}(q(n)) = 0$ if $n \in A$ , $= 1$ if $n \in B$ , and diverges otherwise. Let $C = \{ n : f(q(n)) = 1 \}$ , computable in $X$ . If $n \in A$ , then $f(q(n)) \neq 0$ , so $n \in C$ ; if $n \in B$ , then $f(q(n)) \neq 1$ , so $n \notin C$ .

(2 ⇒ 3) Let $\mathcal P = [T]$ be non-empty, with $T$ computable. For a string $\sigma$ , non-extendibility of $\sigma 0$ and of $\sigma 1$ are $\Sigma^0_1$ properties (Proposition 1.9); fix enumerations of them by stages. Let $A$ be the set of strings $\sigma$ such that the non-extendibility of $\sigma 0$ is confirmed at some stage $s$ and that of $\sigma 1$ is not confirmed at any stage $t < s$ , and $B$ the set of strings $\sigma$ such that the non-extendibility of $\sigma 1$ is confirmed at some stage $s$ and that of $\sigma 0$ is not confirmed at any stage $t \leq s$ . These sets are c.e. and disjoint, so $X$ computes a set $C$ separating them. Define $\sigma_0 = \varepsilon$ and $\sigma_{n+1} = \sigma_n 1$ if $\sigma_n \in C$ , $\sigma_{n+1} = \sigma_n 0$ otherwise. We show by induction that $\sigma_n$ is extendible. If $\sigma_n$ is extendible, at least one of its successors is. If both are, so is $\sigma_{n+1}$ . If only $\sigma_n 1$ is, then the non-extendibility of $\sigma_n 0$ is confirmed at some stage and that of $\sigma_n 1$ never, so $\sigma_n \in A \subseteq C$ and $\sigma_{n+1} = \sigma_n 1$ . If only $\sigma_n 0$ is, then $\sigma_n \in B$ , so $\sigma_n \notin C$ and $\sigma_{n+1} = \sigma_n 0$ . Hence the sequence $\bigcup_n \sigma_n$ , computable in $C$ and so in $X$ , is a member of $\mathcal P$ .

(3 ⇒ 1) $\mathrm{DNC}_2$ is a non-empty $\Pi^0_1$ class (Theorem 2.6).

The proof of (2 ⇒ 3) is uniform: from an index of $T$ , one computes the indices of $A$ and $B$ , and the member is obtained from the separating set by a fixed procedure. Combined with (1 ⇒ 2), it shows that a single member of $\mathrm{DNC}_2$ computes members of all non-empty $\Pi^0_1$ classes, uniformly in their indices. For this reason $\mathrm{DNC}_2$ is called a universal $\Pi^0_1$ class.

4.2 Consequences of the basis theorems

Corollary 4.3.#

There is a low PA set.
There is a computably dominated PA set.
For every non-computable set $C$ , there is a PA set that does not compute $C$ .

Proof of Corollary 4.3.

Apply Theorem 3.1, Theorem 3.5 and Theorem 3.7 to the non-empty $\Pi^0_1$ class $\mathrm{DNC}_2$ , all of whose members are PA.

So the ability to compute a member of every non-empty $\Pi^0_1$ class does not require much computational power in other respects: a low PA set has the same jump as a computable set, and it computes a solution to every problem with a $\Pi^0_1$ set of solutions. On the other hand, a PA set is never computable, since it computes a member of $\mathrm{DNC}_2$ .

4.3 Completions of Peano arithmetic

The name PA comes from logic. Fix a computable coding of the sentences of arithmetic by integers. A set $S$ of sentences is consistent if no contradiction is provable from it, and complete if for every sentence $\varphi$ , either $\varphi \in S$ or $\neg \varphi \in S$ . We use two facts from logic, which we admit.

Proofs are checkable. For a computable set of axioms, the relation ” $p$ codes a proof of $\varphi$ from the axioms” is computable, so the set of theorems is c.e.
Peano arithmetic proves true computations. If $\Phi_e(e)\converge = v$ , then Peano arithmetic $\mathrm{PA}$ proves the sentence $\theta_{e,v}$ expressing ” $\Phi_e(e)$ converges with value $v$ ”, and proves $\neg \theta_{e,w}$ for every $w \neq v$ . Here $\theta_{e,v}$ is the $\Sigma_1$ sentence obtained from Corollary 4.6 of “Arithmetic definability”, and the statement is the $\Sigma_1$ -completeness of $\mathrm{PA}$ , together with the uniqueness of the output, provable in $\mathrm{PA}$ .

We also use that $\mathrm{PA}$ is consistent, since its axioms are true in $\nat$ .

Theorem 4.4.#

A set $X$ is PA if and only if it computes a complete consistent set of sentences containing the axioms of $\mathrm{PA}$ .

Proof of Theorem 4.4.

( $\Rightarrow$ ) Identify a set of sentences with its characteristic function on codes, and let $\mathcal C$ be the class of sets $S$ such that: for every sentence $\varphi$ , exactly one of $\varphi$ and $\neg \varphi$ belongs to $S$ ; every axiom of $\mathrm{PA}$ belongs to $S$ ; and no proof of a contradiction uses only premises from $S$ . Its members are exactly the complete consistent sets of sentences containing $\mathrm{PA}$ . A set fails to belong to $\mathcal C$ if and only if one of the following finite witnesses exists: a sentence $\varphi$ with both or neither of $\varphi, \neg \varphi$ in $S$ ; an axiom of $\mathrm{PA}$ not in $S$ ; or a proof of a contradiction whose premises are in $S$ . Each witness involves finitely many bits of $S$ , and, by the first fact, can be recognized by an algorithm. So the complement of $\mathcal C$ is a $\Sigma^0_1$ class, and $\mathcal C$ is a $\Pi^0_1$ class. It is non-empty, since the set of sentences true in $\nat$ belongs to it. By Theorem 4.2, $X$ computes a member of $\mathcal C$ .

( $\Leftarrow$ ) Let $S \leq_T X$ be a complete consistent set containing $\mathrm{PA}$ . Let $f(e) = 1$ if $\theta_{e,0} \in S$ , and $f(e) = 0$ otherwise; $f$ is computable in $X$ . If $\Phi_e(e)\converge = 0$ , then $\mathrm{PA} \vdash \theta_{e,0}$ ; since $S$ is complete, contains $\mathrm{PA}$ and is consistent, $\theta_{e,0} \in S$ (otherwise $\neg \theta_{e,0} \in S$ and $S$ would be inconsistent), so $f(e) = 1 \neq 0$ . If $\Phi_e(e)\converge = 1$ , then $\mathrm{PA} \vdash \neg \theta_{e,0}$ , so $\theta_{e,0} \notin S$ by consistency, and $f(e) = 0 \neq 1$ . If $\Phi_e(e)$ converges to another value or diverges, there is nothing to check. So $f \in \mathrm{DNC}_2$ .

The second direction contains Gödel’s first incompleteness theorem in Rosser’s form: a complete consistent extension of $\mathrm{PA}$ is not computable, since it would compute a member of $\mathrm{DNC}_2$ . The first direction shows that this is the only obstruction: any degree that computes a member of $\mathrm{DNC}_2$ computes a completion. Combined with Corollary 4.3, there are low completions of Peano arithmetic.

4.4 Exercises

Exercise 4.5 ★.

Show that $X$ is PA if and only if every partial computable function $\psi : \nat \rightharpoonup \{0, 1\}$ has a total $X$ -computable extension.

Solution

If $X$ is PA, let $A = \{ n : \psi(n)\converge = 0 \}$ and $B = \{ n : \psi(n)\converge = 1 \}$ , disjoint c.e. sets, and let $D \leq_T X$ separate $B$ from $A$ : $B \subseteq D$ and $D \cap A = \emptyset$ . The characteristic function of $D$ is a total $X$ -computable extension of $\psi$ .

Conversely, let $\psi(e) \simeq 1 - \Phi_e(e)$ when $\Phi_e(e)\converge \in \{0, 1\}$ , and $\psi(e)$ undefined otherwise; $\psi$ is partial computable with values in $\{0, 1\}$ . Let $g$ be a total $X$ -computable extension, and let $f(e) = g(e)$ if $g(e) \in \{0, 1\}$ and $f(e) = 0$ otherwise. If $\Phi_e(e)\converge \in \{0, 1\}$ , then $f(e) = g(e) = 1 - \Phi_e(e) \neq \Phi_e(e)$ . If $\Phi_e(e)\converge \geq 2$ , then $f(e) \in \{0, 1\}$ differs from it. So $f \in \mathrm{DNC}_2$ , and $X$ is PA.

Exercise 4.6 ★★.#

A set $Y$ is PA relative to $X$ if it computes a function $f : \nat \to \{0, 1\}$ with $f(e) \neq \Phi^X_e(e)$ whenever $\Phi^X_e(e)\converge$ . Show that if $Y$ is PA relative to $X$ , then $X \leq_T Y$ .

Solution

The proof of Theorem 4.2 relativizes: $Y$ computes a member of every non-empty $\Pi^0_1(X)$ class, that is, every class $[T]$ with $T$ an $X$ -computable tree. The singleton $\{ X \}$ is such a class, with tree $\{ X \uh n : n \in \nat \}$ . So $Y$ computes its only member, $X$ .

4.5 Notes and references

The degrees of completions of Peano arithmetic were studied by Scott (1962), who showed that they compute members of all non-empty $\Pi^0_1$ classes, and by Jockusch and Soare (1972), who proved the characterization by $\{0, 1\}$ -valued diagonally non-computable functions, also obtained by Solovay. Jockusch and Soare also proved the existence of low PA degrees. The incompleteness theorem in the form used here is due to Rosser (1936).

D. Scott, Algebras of sets binumerable in complete extensions of arithmetic, in Recursive Function Theory, Proceedings of Symposia in Pure Mathematics 5, American Mathematical Society, 1962, 117–121.
C. G. Jockusch and R. I. Soare, Degrees of members of Π⁰₁ classes, Pacific Journal of Mathematics 40 (1972), 605–616.
C. G. Jockusch and R. I. Soare, Π⁰₁ classes and degrees of theories, Transactions of the American Mathematical Society 173 (1972), 33–56.
J. B. Rosser, Extensions of some theorems of Gödel and Church, Journal of Symbolic Logic 1 (1936), 87–91.