Post's theorem · Computability Theory

The arithmetic hierarchy is defined by counting quantifiers; the iterated jumps $\emptyset, \emptyset', \emptyset'', \dots$ are defined by iterating the halting problem. Post’s theorem shows that the two are the same scale. Each existential quantifier in front of a $\Pi^0_n$ relation corresponds to one jump: the $\Sigma^0_{n+1}$ sets are the sets c.e. in $\emptyset^{(n)}$ , and the $\Delta^0_{n+1}$ sets are the sets computable in $\emptyset^{(n)}$ . As a consequence, $\emptyset^{(n)}$ is complete at level $\Sigma^0_n$ , and the hierarchy is strict.

2.1 One jump for one quantifier

The whole theorem rests on the following lemma, which converts an oracle for the jump into one more quantifier, and back.

Lemma 2.1.#

For every $Y \in \cs$ , a relation is $\Sigma^0_1(Y')$ if and only if it is $\Sigma^0_2(Y)$ .

Proof of Lemma 2.1.

( $\Leftarrow$ ) Let $A = \{ x : \exists y\ \forall z\ R(x, y, z) \}$ with $R$ $Y$ -computable. The relation $P(x, y) \iff \forall z\ R(x, y, z)$ is $\Pi^0_1(Y)$ , so its complement is $Y$ -c.e., and by Theorem 3.2 of “The Turing jump” there is a computable $f$ with $\neg P(x, y) \iff f(\langle x, y \rangle) \in Y'$ . Hence $P$ is $Y'$ -computable, and $A = \{ x : \exists y\ P(x, y) \}$ is $\Sigma^0_1(Y')$ .

( $\Rightarrow$ ) Let $A = W^{Y'}_e$ . By Proposition 1.5 of “Computation relative to an oracle”, $x \in A$ if and only if there are a string $\sigma$ and a stage $s$ with $\sigma \prec Y'$ and $\Phi^\sigma_e(x)[s]\converge$ . The relation $\Phi^\sigma_e(x)[s]\converge$ is computable. The relation $\sigma \prec Y'$ is

\forall k < |\sigma|\ \ \big( (\sigma(k) = 1 \wedge k \in Y') \vee (\sigma(k) = 0 \wedge k \notin Y') \big),

where $k \in Y'$ is $\Sigma^0_1(Y)$ and $k \notin Y'$ is $\Pi^0_1(Y)$ ; both are $\Sigma^0_2(Y)$ , so by Proposition 1.4 (relativized) the relation $\sigma \prec Y'$ is $\Sigma^0_2(Y)$ . Then $A$ is the projection of the intersection of a $\Sigma^0_2(Y)$ relation and a computable relation, hence $\Sigma^0_2(Y)$ .

The two directions use the jump in opposite ways. In ( $\Leftarrow$ ), one question to $Y'$ replaces a universal quantifier. In ( $\Rightarrow$ ), a computation with oracle $Y'$ is guessed as a finite string, and the correctness of the guess costs one more quantifier: positive answers of the oracle are $\Sigma^0_1(Y)$ facts, negative answers are $\Pi^0_1(Y)$ facts.

2.2 Post’s theorem

Theorem 2.2 (Post).#

For every $X \in \cs$ and $n \geq 0$ :

a relation is $\Sigma^0_{n+1}(X)$ if and only if it is $X^{(n)}$ -c.e.;
a set is $\Delta^0_{n+1}(X)$ if and only if it is computable in $X^{(n)}$ ;
for $n \geq 1$ , the set $X^{(n)}$ is $\Sigma^0_n(X)$ -complete, and in fact every $\Sigma^0_n(X)$ set is one-one reducible to it.

In particular, $\emptyset^{(n)}$ is $\Sigma^0_n$ -complete, the $\Sigma^0_{n+1}$ sets are the $\emptyset^{(n)}$ -c.e. sets, and the $\Delta^0_{n+1}$ sets are the sets computable in $\emptyset^{(n)}$ .

Proof of Theorem 2.2.

By induction on $n$ , simultaneously for all $X$ . For $n = 0$ , $X^{(0)} = X$ , and the $\Sigma^0_1(X)$ relations are the $X$ -c.e. relations. Suppose the statement holds for $n$ and all $X$ . A relation $A$ is $\Sigma^0_{n+2}(X)$ if and only if $A = \{ \vec x : \exists y\ P(\vec x, y) \}$ with $P$ a $\Pi^0_{n+1}(X)$ relation. The complement of $P$ is $\Sigma^0_{n+1}(X)$ , that is, $X^{(n)}$ -c.e. by the induction hypothesis, so $P$ ranges exactly over the $\Pi^0_1(X^{(n)})$ relations. Hence the $\Sigma^0_{n+2}(X)$ relations are the projections of $\Pi^0_1(X^{(n)})$ relations, that is, the $\Sigma^0_2(X^{(n)})$ relations. By Lemma 2.1 with $Y = X^{(n)}$ , these are the $\Sigma^0_1(X^{(n+1)})$ relations.
A set is $\Delta^0_{n+1}(X)$ if and only if it and its complement are $\Sigma^0_{n+1}(X)$ , that is, $X^{(n)}$ -c.e. by item 1, that is, computable in $X^{(n)}$ by Proposition 4.8 of “Computably enumerable sets” relativized.
$X^{(n)} = (X^{(n-1)})'$ is $X^{(n-1)}$ -c.e., hence $\Sigma^0_n(X)$ by item 1. Every $\Sigma^0_n(X)$ set is $X^{(n-1)}$ -c.e. by item 1, hence one-one reducible to $(X^{(n-1)})' = X^{(n)}$ by Theorem 3.2 of “The Turing jump”.

Corollary 2.3.#

For every $n \geq 1$ :

$\emptyset^{(n)}$ is $\Sigma^0_n$ and not $\Pi^0_n$ , and its complement is $\Pi^0_n$ and not $\Sigma^0_n$ ;
the set $\emptyset^{(n)} \oplus (\nat \setminus \emptyset^{(n)})$ is $\Delta^0_{n+1}$ , and neither $\Sigma^0_n$ nor $\Pi^0_n$ .

So all the inclusions $\Delta^0_n \subsetneq \Sigma^0_n, \Pi^0_n \subsetneq \Delta^0_{n+1}$ are strict.

Proof of Corollary 2.3.

$\emptyset^{(n)}$ is $\Sigma^0_n$ by the theorem. If it were $\Pi^0_n$ , it would be $\Delta^0_n$ , hence computable in $\emptyset^{(n-1)}$ by item 2, contradicting $\emptyset^{(n-1)} <_T \emptyset^{(n)}$ (Theorem 3.2 of “The Turing jump”). The statement on the complement follows by complementation.
The set $J = \emptyset^{(n)} \oplus (\nat \setminus \emptyset^{(n)})$ is computable in $\emptyset^{(n)}$ , hence $\Delta^0_{n+1}$ . If $J$ were $\Sigma^0_n$ , then $\nat \setminus \emptyset^{(n)} = \{ m : 2m + 1 \in J \}$ would be $\Sigma^0_n$ , by substitution, contradicting item 1. If $J$ were $\Pi^0_n$ , then $\emptyset^{(n)} = \{ m : 2m \in J \}$ would be $\Pi^0_n$ .

Corollary 2.4.#

A set is $\Delta^0_2$ if and only if it is computable in $\emptyset'$ , if and only if it is limit computable.
A set is arithmetic if and only if it is computable in $\emptyset^{(n)}$ for some $n$ .
For every $n \geq 1$ , the class of $\Delta^0_n$ sets is closed downward under Turing reducibility: if $A \leq_T B$ and $B$ is $\Delta^0_n$ , then $A$ is $\Delta^0_n$ . The classes $\Sigma^0_n$ and $\Pi^0_n$ are not.

Proof of Corollary 2.4.

Item 2 of the theorem for $n = 1$ , and Shoenfield’s limit lemma (Shoenfield's limit lemma).
A $\Sigma^0_n$ set is $\Delta^0_{n+1}$ , hence computable in $\emptyset^{(n)}$ ; conversely a set computable in $\emptyset^{(n)}$ is $\Delta^0_{n+1}$ .
$\Delta^0_n$ is the class of sets computable in $\emptyset^{(n-1)}$ , which is closed downward under $\leq_T$ . The set $\nat \setminus \emptyset^{(n)}$ is Turing equivalent to the $\Sigma^0_n$ set $\emptyset^{(n)}$ , but is not $\Sigma^0_n$ (Corollary 2.3); symmetrically, $\emptyset^{(n)}$ is Turing equivalent to the $\Pi^0_n$ set $\nat \setminus \emptyset^{(n)}$ , but is not $\Pi^0_n$ .

The name ” $\Delta^0_2$ approximation” used in the course on Turing degrees is thus justified: the sets with such approximations are exactly the $\Delta^0_2$ sets.

2.3 Exercises

Exercise 2.5 ★.

Show that the set $\{ e : \Phi^{\emptyset'}_e \text{ is total} \}$ is $\Pi^0_3$ .

Solution

It is $\{ e : \forall x\ \exists s\ \Phi^{\emptyset'}_e(x)[s]\converge \}$ , a $\Pi^0_2(\emptyset')$ set, since the relation $\Phi^{\emptyset'}_e(x)[s]\converge$ is $\emptyset'$ -computable. Its complement is $\Sigma^0_2(\emptyset')$ , that is, c.e. in $\emptyset'' = (\emptyset')'$ by Theorem 2.2 relativized to $\emptyset'$ , and hence $\Sigma^0_3$ by the theorem unrelativized. So the set is $\Pi^0_3$ .

Exercise 2.6 ★★.

Show that $X \leq_T Y$ if and only if $X' \leq_m Y'$ .

Solution

If $X \leq_T Y$ , then $X' \leq_1 Y'$ by Theorem 3.2 of “The Turing jump”. Conversely, let $h$ be a many-one reduction of $X'$ to $Y'$ . For $i \in \{0, 1\}$ , let $a_i$ be an index such that $W^Z_{a_i} = \{ n : Z(n) = i \}$ for every oracle $Z$ , and let $g_i$ be the computable function given by Theorem 3.2 of “The Turing jump”, with $Z(n) = i \iff g_i(n) \in Z'$ for every $Z$ . Then $X(n) = i \iff h(g_i(n)) \in Y'$ . The two sets $\{ n : h(g_0(n)) \in Y' \}$ and $\{ n : h(g_1(n)) \in Y' \}$ are $Y$ -c.e., and they are complementary, since they are $\{ n : X(n) = 0 \}$ and $\{ n : X(n) = 1 \}$ . Hence $X$ is $Y$ -computable.

Exercise 2.7 ★★.

Show that a set $A$ is $\Sigma^0_2$ if and only if $A = \{ x : \exists y\ \forall z \geq y\ \ g(x, z) = 1 \}$ for some total computable function $g : \nat^2 \to \{0, 1\}$ .

Solution

A set of this form is $\Sigma^0_2$ . Conversely, let $A = \{ x : \exists y\ \forall z\ R(x, y, z) \}$ with $R$ computable. Define $g(x, s) = 1$ if there is $y < s$ such that $R(x, y, z)$ holds for all $z < s$ , and in addition the least such $y$ is the same as at stage $s - 1$ ; and $g(x, s) = 0$ otherwise. If $x \in A$ , let $y_0$ be the least $y$ with $\forall z\ R(x, y, z)$ ; every $y < y_0$ eventually fails at some $z$ , so from some stage on the least candidate below $s$ is $y_0$ , and $g(x, s) = 1$ for all large $s$ . If $x \notin A$ , every $y$ eventually fails, and a $y$ that has failed is never a candidate again. So each $y$ is the least candidate at only finitely many stages, and for infinitely many $s$ either there is no candidate at stage $s$ or the least candidate differs from the one at stage $s - 1$ ; at these stages $g(x, s) = 0$ .

2.4 Notes and references

The theorem is due to Post, announced in 1948, and its proof is in Kleene’s Introduction to Metamathematics. Its modern formulation in terms of the jump follows Kleene and Post (1954). The characterization of $\Sigma^0_2$ sets in the last exercise is the starting point of the use of “infinitely often” and “cofinitely often” conditions in constructions below $\emptyset''$ .

E. L. Post, Degrees of recursive unsolvability (preliminary report), Bulletin of the American Mathematical Society 54 (1948), 641–642.
S. C. Kleene, Introduction to Metamathematics, North-Holland, 1952.
S. C. Kleene and E. L. Post, The upper semi-lattice of degrees of recursive unsolvability, Annals of Mathematics 59 (1954), 379–407.