The Arithmetical Hierarchy and Post's Theorem

Let $r(\vec{x},u)$ be the $0$-$1$ characteristic function of $R$. The bounded sum $S(\vec{x})={\sum }_{u<t(\vec{x})}r(\vec{x},u)$ is primitive recursive by primitive recursion and composition.

The existential relation has characteristic test $S(\vec{x})>0$. Likewise $P(\vec{x})={\prod }_{u<t(\vec{x})}r(\vec{x},u)$ is primitive recursive and equals $1$ exactly for the universal relation, including the empty product case.

If $x\in A⟺\mathrm{\exists }sR(x,s)$ with $R$ primitive recursive, search $s=0,1,\dots$ and halt on the first true value. This recognizes exactly $A$.

Conversely, a recognizer has a finite halting computation exactly on its positive inputs. Its coded history gives an existential witness whose validity is primitive recursive, so $A$ has 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$.

The condition $e\in \mathrm{T}\mathrm{O}\mathrm{T}$ is $\mathrm{\forall }x\mathrm{\exists }sT(e,x,s)$, hence is ${\mathrm{\Pi }}_2^0$.

Write $z\in A⟺\mathrm{\forall }x\mathrm{\exists }yR(z,x,y)$ with $R$ primitive recursive. Uniformly produce a program which on input $x$ searches for such a $y$ and halts when one appears. By s-m-n its index is a total computable function of $z$, and that program is total exactly when $z\in A$.

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.

Assume a computable modulus is supplied for this approximation. Let $h(e,s)=1$ if program $e$ has halted by stage $s$, and $0$ otherwise. This is computable and converges pointwise to ${\chi }_{0^{\mathrm{\prime }}}$.

If a computable modulus $m(e)$ were available, simulate $e$ for $m(e)$ steps and return $h(e,m(e))$. This would decide $0^{\mathrm{\prime }}$, contradicting undecidability of the halting problem.