The Arithmetical Hierarchy and Post's Theorem

Addition and multiplication are primitive recursive: use $a+0=a$, $a+(m+1)=S(a+m)$, $a\cdot 0=0$, and $a\cdot (m+1)=a\cdot m+a$. Argument permutations are compositions with projections. Constants zero and one are initial functions or their compositions with successor. The function $\mathrm{sg}$ defined by $\mathrm{sg}(0)=0$, $\mathrm{sg}(m+1)=1$ is primitive recursive.

Let $r(\vec{x},u)$ be the $0$-$1$ characteristic function of $R$. Define $B(0,\vec{x})=0$, $B(m+1,\vec{x})=B(m,\vec{x})+r(\vec{x},m)$ and $C(0,\vec{x})=1$, $C(m+1,\vec{x})=C(m,\vec{x})r(\vec{x},m)$. These are primitive-recursion instances with parameters. Consequently $\mathrm{sg}(B(t(\vec{x}),\vec{x}))$ and $C(t(\vec{x}),\vec{x})$ are primitive recursive by composition.

The first expression is one exactly when at least one of the first $t(\vec{x})$ characteristic values is one; the second is one exactly when all are one. At bound zero their values are respectively zero and one. Thus they are the characteristic functions of the existential and universal relations asserted.

If $x\in A⟺\mathrm{\exists }sR(x,s)$ with $R$ primitive recursive, evaluate $R(x,s)$ for $s=0,1,\dots$ and accept on the first true value. Every primitive-recursive predicate is computable: its initial functions are computed directly and its finite composition and primitive-recursion derivation become composition and finite loops of machines, as in A partial function is partial recursive if and only if it is Turing computable. The search therefore recognizes exactly $A$.

Conversely, let $M$ recognize $A$. A recognizer may halt rejecting on negative inputs, so replace each rejecting halt of $M$ by a fixed loop, obtaining a machine $M^{\mathrm{\prime }}$ that halts exactly when $M$ accepts. Fix its code $e$. By Kleene's T-predicate and output function, $T(e,x,s)$ is a primitive-recursive predicate saying exactly that $s$ codes a complete halting history of $M^{\mathrm{\prime }}$ on $x$. Thus $x\in A⟺\mathrm{\exists }sT(e,x,s)$, a ${\mathrm{\Sigma }}_1^0$ definition.

If $A$ is ${\mathrm{\Delta }}_1^0$, both $A$ and its complement are ${\mathrm{\Sigma }}_1^0$ and hence recognizable. Dovetail their recognizers; exactly one accepts, yielding a decider for $A$.

If $A$ is decidable, both $A$ and its complement are recognizable, hence both are ${\mathrm{\Sigma }}_1^0$. Therefore $A\in {\mathrm{\Delta }}_1^0$.

Push negations through the displayed prefix. Each $\mathrm{\exists }$ changes to $\mathrm{\forall }$ and conversely; the negated primitive-recursive matrix is again primitive recursive.

Rename bound variables and merge equal-polarity blocks. Conjunction and disjunction distribute through adjacent like quantifiers, and shorter prefixes are padded by vacuous like-polarity quantifiers. Thus the leading polarity and at most $n$ alternations are retained.

The universal partial function $(e,x)\mapsto {\phi }_e(x)$ is partial computable. Its halting domain $K$ is computably enumerable, and hence is ${\mathrm{\Sigma }}_1^0$ by Sigma_1^0 sets are exactly the computably enumerable sets.

Write $x\in A⟺\mathrm{\exists }yR(x,y)$ with $R$ primitive recursive. There is a partial computable two-argument procedure which, on parameters $(x,z)$, searches for $y$ and halts exactly when $R(x,y)$; it ignores $z$. The hard-wiring function supplied by acceptability gives, uniformly and totally computably in $x$, an index $e_x$ for the corresponding one-argument procedure.

Therefore $x\in A$ exactly when ${\phi }_{e_x}(0)\downarrow$. After the fixed binary encodings from Completeness at an arithmetical level, the total computable map $x\mapsto ⟨e_x,0⟩$ reduces $A$ to $K$.

By [F3], ${\phi }_e(x)\downarrow$ is equivalent to $\mathrm{\exists }sT(e,x,s)$ with a primitive-recursive matrix. Thus $e\in \mathrm{T}\mathrm{O}\mathrm{T}$ is $\mathrm{\forall }x\mathrm{\exists }sT(e,x,s)$, a ${\mathrm{\Pi }}_2^0$ predicate.

By [F1], write $z\in A⟺\mathrm{\forall }x\mathrm{\exists }yR(z,x,y)$ with $R$ primitive recursive. Fix one program $P$ which, on coded inputs $(z,x)$, tests $R(z,x,0),R(z,x,1),\dots$ in order and halts with output $0$ at the first successful test. Each test terminates, so $P(z,x)$ halts exactly when $\mathrm{\exists }yR(z,x,y)$.

Let $e_P$ be a fixed index of $P$. The specialization map in [F4] gives a total computable $f(z)=s_1^1(e_P,z)$ whose program on input $x$ agrees with $P(z,x)$. Hence $f(z)\in \mathrm{T}\mathrm{O}\mathrm{T}$ exactly when $\mathrm{\forall }x\mathrm{\exists }yR(z,x,y)$, equivalently $z\in A$. Since $A$ was arbitrary, [F2] and step 1.1 prove ${\mathrm{\Pi }}_2^0$-completeness.

The run has finitely many steps, hence performs only finitely many query instructions. Let $F$ be the set of numbers queried in that run.

If $Y$ agrees with $X$ on $F$, induction over those finitely many transitions gives the same state, tapes, query answers, and next transition at every step. Thus the run halts with the same output.

For $n=0$, the first equivalence is the ${\mathrm{\Sigma }}_1^0$/c.e. theorem; deciding a set is equivalent to recognizing it and its complement.

Assume the characterizations at $n$. In a ${\mathrm{\Sigma }}_{n+2}^0$ presentation, the predicate following the first existential block is ${\mathrm{\Pi }}_{n+1}^0$. It is co-c.e. in $0^{(n)}$, and is therefore decidable by the halting oracle $0^{(n+1)}$; the first block is consequently a c.e. search in $0^{(n+1)}$. Conversely, record a halting $0^{(n+1)}$-oracle computation together with its finite query transcript. Replace each yes-query by its ${\mathrm{\Sigma }}_{n+1}^0$ halting witness and each no-query by the dual ${\mathrm{\Pi }}_{n+1}^0$ condition. Since the transcript is finite, its conditions merge with the outer existential witness into a ${\mathrm{\Sigma }}_{n+2}^0$ formula.

A $0^{(n)}$-decider recognizes both a set and its complement, and two relative recognizers can be dovetailed into a decider. Applying the first equivalence to both sides therefore gives the $\mathrm{\Delta }$ equivalence; negation gives the $\mathrm{\Pi }$ clause. This closes the induction.

Enumerate the $0^{(n)}$-c.e. sets as $(W_e^{0^{(n)}}{)}_e$ and set $D_n=\{e:e\mathrm{\notin }{W}_e^{0^{(n)}}\}$. If $D_n$ were itself $0^{(n)}$-c.e., say $D_n=W_d^{0^{(n)}}$, substituting $e=d$ gives $d\in D_n⟺d\mathrm{\notin }{D}_n$.

Hence $D_n$ is not $0^{(n)}$-c.e., while its complement is. Post's theorem identifies the complement as ${\mathrm{\Sigma }}_{n+1}^0$ and $D_n$ as ${\mathrm{\Pi }}_{n+1}^0$; exchanging them gives the claimed pair.

Padding a prefix by a vacuous final quantifier shows ${\mathrm{\Sigma }}_n^0\subseteq {\mathrm{\Sigma }}_{n+1}^0$ and similarly for $\mathrm{\Pi }$.

The level-$n$ diagonal construction supplies a ${\mathrm{\Sigma }}_{n+1}^0$ set outside ${\mathrm{\Pi }}_{n+1}^0$. If it lay in ${\mathrm{\Sigma }}_n^0$, then it would also lie in ${\mathrm{\Pi }}_{n+1}^0$ by padding and complement normalization, a contradiction; the complementary witness gives the $\mathrm{\Pi }$ separation.

Use the halting-set meaning of $0^{\mathrm{\prime }}$ fixed in Post's theorem. A query code $e$ specifies an ordinary computation whose halting is in question. Put $0_s^{\mathrm{\prime }}=\{e\le s:\text{the computation coded by }e\text{ halts within }s\text{ steps}\}$. Bounded simulation makes membership in $0_s^{\mathrm{\prime }}$ uniformly decidable in $(e,s)$. These sets are finite and increasing, and their union is $0^{\mathrm{\prime }}$: a genuinely halting computation enters once $s$ exceeds both its code and its halting time; a nonhalting computation never enters.

If $A{\le }_T{0}^{\mathrm{\prime }}$, fix $M^{0^{\mathrm{\prime }}}$ computing ${\chi }_A$. Define $g(x,s)$ by simulating at most $s$ oracle-machine transitions of $M(x)$, answering each query by the decidable set $0_s^{\mathrm{\prime }}$. Return the output if it halts with output in $\{0,1\}$ within the cutoff, and return $0$ otherwise. Each stage halts, so $g$ is total computable and bit-valued even when an incorrect oracle sends $M$ into a loop or an unintended output. No time-efficiency bound on this finite simulation is asserted.

For fixed $x$, the true run has a finite transition length $r$ and a finite query set $F$ by L1. All negative answers on $F$ are correct at every stage. Each positive answer becomes permanently correct by step 1.1; take $s_0\ge r$ beyond the finitely many corresponding entry stages. For every $s\ge s_0$, L1 gives exactly the true run with oracle $0_s^{\mathrm{\prime }}$, and the cutoff does not interrupt it. Thus $g(x,s)={\chi }_A(x)$ eventually. An empty $F$ requires only the time cutoff, and $s_0$ is an existence bound, not a claimed computable modulus.

Conversely, let total computable $h(x,s)$ converge eventually to ${\chi }_A(x)$. For each $(x,s)$, effectively form the ordinary program that computes $h(x,s)$, searches $t=s+1,s+2,\dots$, and halts upon finding $h(x,t)\mathrm{\ne }h(x,s)$. Its halting is a $0^{\mathrm{\prime }}$ question. Ask these questions for $s=0,1,\dots$ until receiving a negative answer. Eventual constancy ensures termination; a negative answer means that all later values equal the current value, which must therefore be ${\chi }_A(x)$. Output it. This computes $A$ in $0^{\mathrm{\prime }}$ and proves the reverse implication.

The decidable set $E=\{2k:k\in \mathbb{N}\}$ is ${\mathrm{\Delta }}_1^0$, hence is both ${\mathrm{\Sigma }}_1^0$ and ${\mathrm{\Pi }}_1^0$.

Prefix padding puts both descriptions of $E$ at every positive level $n$. Thus $E\in {\mathrm{\Sigma }}_n^0\cap {\mathrm{\Pi }}_n^0$, refuting disjointness.

Let $h(e,s)=1$ if program $e$ has halted by stage $s$, and $0$ otherwise. Bounded simulation makes $h$ total computable, and it converges pointwise to the characteristic function ${\chi }_{0^{\mathrm{\prime }}}$ of the halting set. Thus ${\chi }_{0^{\mathrm{\prime }}}$ is limit computable.

Suppose ${\chi }_{0^{\mathrm{\prime }}}$ had a total computable approximation $g(e,s)$ with a computable stabilization modulus $m(e)$. Computing $g(e,m(e))$ would then decide $0^{\mathrm{\prime }}$, contradicting undecidability of the halting problem. This argument covers every possible approximation, including $h$ from step 1.1, so no such modulus exists.