[proofplan] We prove the $\Sigma$-clause by induction on $n$, using the Turing jump as the uniform halting problem for computations relative to the previous jump. The forward direction rewrites a $\Sigma^0_{n+1}$ definition as an existential search whose matrix is decidable relative to $\varnothing^{(n)}$. The reverse direction codes an accepting oracle computation by a finite transcript and replaces each oracle answer by the arithmetical formula defining the oracle. The $\Pi$-clause follows by complementing, and the $\Delta$-clause follows from the fact that a set is decidable relative to an oracle exactly when both it and its complement are enumerable relative to that oracle. [/proofplan] [step:Fix the oracle-machine notation and the jump convention] Fix an effective enumeration $(\Phi_e^X)_{e \in \mathbb{N}}$ of partial functions computed by Turing machines with oracle $X \subset \mathbb{N}$. For an oracle $X \subset \mathbb{N}$, define the $X$-computably enumerable set enumerated by index $e$ by \begin{align*} W_e^X := \{x \in \mathbb{N} : \Phi_e^X(x) \downarrow\}. \end{align*} Define the Turing jump of $X$ by \begin{align*} X' := K^X := \{e \in \mathbb{N} : \Phi_e^X(e) \downarrow\}. \end{align*} Thus $\varnothing^{(0)} = \varnothing$ and $\varnothing^{(k+1)} = K^{\varnothing^{(k)}}$ for $k \geq 0$. We use the standard coding of finite sequences by natural numbers. A finite oracle computation transcript is a natural number coding the finite list of machine configurations, oracle queries, oracle answers, and transition steps occurring before halting. The predicate saying that a number codes a syntactically correct finite transcript for a fixed oracle machine, input, and prescribed oracle-answer pattern is primitive recursive. [/step] [step:Record the jump completeness principle used at each induction stage] [claim:Relative computably enumerable sets are decidable from the jump] Let $X \subset \mathbb{N}$ and let $B \subset \mathbb{N}$ be computably enumerable relative to $X$. Then $B \le_T X'$. [/claim] [proof] Since $B$ is computably enumerable relative to $X$, there exists an index $e \in \mathbb{N}$ such that \begin{align*} B = W_e^X. \end{align*} By the parameter theorem for oracle machines, there is a total computable function \begin{align*} s_e: \mathbb{N} &\to \mathbb{N} \end{align*} such that for every $x \in \mathbb{N}$, \begin{align*} \Phi_{s_e(x)}^X(s_e(x)) \downarrow \quad \iff \quad \Phi_e^X(x) \downarrow. \end{align*} Hence, for every $x \in \mathbb{N}$, \begin{align*} x \in B &\iff \Phi_e^X(x) \downarrow\\ &\iff \Phi_{s_e(x)}^X(s_e(x)) \downarrow\\ &\iff s_e(x) \in X'. \end{align*} The map $x \mapsto s_e(x)$ is computable, so an oracle for $X'$ decides membership in $B$ by computing $s_e(x)$ and querying whether $s_e(x) \in X'$. Therefore $B \le_T X'$. [/proof] [guided] We need one uniform fact about jumps: the jump $X'$ decides every set that can be enumerated using $X$ as an oracle. Let $B \subset \mathbb{N}$ be computably enumerable relative to $X$. By definition, there is an oracle machine index $e$ such that \begin{align*} B = W_e^X = \{x \in \mathbb{N} : \Phi_e^X(x) \downarrow\}. \end{align*} The jump $X'$ does not directly ask whether $\Phi_e^X(x)$ halts; it asks whether a machine halts on its own index. The parameter theorem converts the first question into the second. More precisely, there is a total computable map \begin{align*} s_e: \mathbb{N} &\to \mathbb{N} \end{align*} such that, for every $x \in \mathbb{N}$, \begin{align*} \Phi_{s_e(x)}^X(s_e(x)) \downarrow \quad \iff \quad \Phi_e^X(x) \downarrow. \end{align*} Thus the question "$x \in B$" is reduced to a single question about $X'$: \begin{align*} x \in B &\iff \Phi_e^X(x) \downarrow\\ &\iff \Phi_{s_e(x)}^X(s_e(x)) \downarrow\\ &\iff s_e(x) \in X'. \end{align*} Since $s_e$ is computable without any oracle, an oracle for $X'$ decides membership in $B$. This proves $B \le_T X'$. [/guided] [/step] [step:Prove the base case $n = 1$] A set $A \subset \mathbb{N}$ belongs to $\Sigma^0_1$ exactly when there is a decidable relation $R \subset \mathbb{N}^2$ such that, for every $x \in \mathbb{N}$, \begin{align*} x \in A \iff \exists y \in \mathbb{N}\, R(x,y). \end{align*} Given such an $R$, enumerate $A$ by searching all pairs $(x,y)$ and outputting $x$ when $R(x,y)$ holds. Conversely, if $A = W_e^\varnothing$, then there is a decidable computation predicate $T_e \subset \mathbb{N}^2$ such that \begin{align*} x \in A \iff \exists s \in \mathbb{N}\, T_e(x,s), \end{align*} where $T_e(x,s)$ means that the ordinary machine with index $e$ halts on input $x$ within $s$ steps. Hence $A \in \Sigma^0_1$ iff $A$ is computably enumerable relative to $\varnothing^{(0)} = \varnothing$. By definition, $A \in \Pi^0_1$ iff $\mathbb{N} \setminus A \in \Sigma^0_1$, so the $\Pi$-clause follows from the $\Sigma$-clause. Also $A \in \Delta^0_1$ iff both $A$ and $\mathbb{N} \setminus A$ are computably enumerable. Running the two enumerations in parallel decides membership in $A$, and every decidable set has decidable enumerations of itself and its complement. Therefore \begin{align*} A \in \Delta^0_1 \iff A \le_T \varnothing. \end{align*} [/step] [step:Show that every $\Sigma^0_{n+1}$ set is enumerable relative to $\varnothing^{(n)}$] Assume the $\Sigma$- and $\Pi$-clauses hold at level $n$, and let $A \subset \mathbb{N}$ satisfy $A \in \Sigma^0_{n+1}$. By the definition of the arithmetical hierarchy, there is a relation $B \subset \mathbb{N}^2$ with $B \in \Pi^0_n$ such that, for every $x \in \mathbb{N}$, \begin{align*} x \in A \iff \exists y \in \mathbb{N}\, (x,y) \in B. \end{align*} Because $B \in \Pi^0_n$, its complement $\mathbb{N}^2 \setminus B$ is $\Sigma^0_n$. Using a fixed computable pairing bijection between $\mathbb{N}^2$ and $\mathbb{N}$, the induction hypothesis gives that $\mathbb{N}^2 \setminus B$ is computably enumerable relative to $\varnothing^{(n-1)}$. By the jump completeness principle with $X = \varnothing^{(n-1)}$, the relation $\mathbb{N}^2 \setminus B$ is decidable relative to $\varnothing^{(n)}$. Therefore $B$ is also decidable relative to $\varnothing^{(n)}$. Now define an oracle enumeration procedure with oracle $\varnothing^{(n)}$: search through all pairs $(x,y) \in \mathbb{N}^2$, decide whether $(x,y) \in B$, and enumerate $x$ whenever the answer is yes. This enumerates exactly $A$, since $x$ is eventually output iff there exists $y$ with $(x,y) \in B$. Hence $A$ is computably enumerable relative to $\varnothing^{(n)}$. [/step] [step:Show that every set enumerable relative to $\varnothing^{(n)}$ is $\Sigma^0_{n+1}$] Assume the $\Sigma$- and $\Pi$-clauses hold at level $n$, and let $A \subset \mathbb{N}$ be computably enumerable relative to $\varnothing^{(n)}$. Choose an oracle machine index $e \in \mathbb{N}$ such that \begin{align*} A = W_e^{\varnothing^{(n)}}. \end{align*} For $x \in \mathbb{N}$, membership $x \in A$ holds iff there exists a finite accepting transcript $\tau \in \mathbb{N}$ for the computation of machine $e$ on input $x$ with oracle $\varnothing^{(n)}$. Let $Q_+(\tau) \subset \mathbb{N}$ denote the finite set of oracle queries recorded in $\tau$ with answer yes, and let $Q_-(\tau) \subset \mathbb{N}$ denote the finite set of oracle queries recorded in $\tau$ with answer no. There is a primitive recursive predicate $C_e(x,\tau)$ saying that $\tau$ is syntactically a halting transcript for machine $e$ on input $x$, apart from the truth of the listed oracle answers. Thus \begin{align*} x \in A \iff \exists \tau \in \mathbb{N}\, \left[ C_e(x,\tau) \wedge \bigwedge_{q \in Q_+(\tau)} q \in \varnothing^{(n)} \wedge \bigwedge_{q \in Q_-(\tau)} q \notin \varnothing^{(n)} \right]. \end{align*} Since $\varnothing^{(n)}$ is computably enumerable relative to $\varnothing^{(n-1)}$, the induction hypothesis gives $\varnothing^{(n)} \in \Sigma^0_n$. Hence $q \in \varnothing^{(n)}$ is expressible by a $\Sigma^0_n$ formula, while $q \notin \varnothing^{(n)}$ is expressible by a $\Pi^0_n$ formula. A finite Boolean combination of $\Sigma^0_n$ and $\Pi^0_n$ formulas is equivalent, after putting all bounded finite conjunctions into [prenex normal form](/theorems/4653), to a Boolean combination whose outer quantifier complexity is at most level $n+1$. Because the transcript variable $\tau$ is existentially quantified at the front, the whole formula is equivalent to a $\Sigma^0_{n+1}$ formula. Therefore $A \in \Sigma^0_{n+1}$. [guided] The key point is that an oracle computation uses only finitely many oracle answers before it halts. We turn those finitely many answers into arithmetical conditions. Since $A$ is computably enumerable relative to $\varnothing^{(n)}$, there is an oracle machine index $e$ such that \begin{align*} A = W_e^{\varnothing^{(n)}}. \end{align*} For a fixed input $x \in \mathbb{N}$, the statement $x \in A$ means that the machine with index $e$ eventually halts on input $x$ while consulting the oracle $\varnothing^{(n)}$. A halting computation is finite, so it can be coded by a natural number $\tau$. This code records the successive configurations of the machine, the oracle questions asked, and the yes/no answers used. Define $Q_+(\tau) \subset \mathbb{N}$ to be the finite set of numbers queried in $\tau$ and recorded with answer yes. Define $Q_-(\tau) \subset \mathbb{N}$ to be the finite set of numbers queried in $\tau$ and recorded with answer no. Define $C_e(x,\tau)$ to be the primitive recursive predicate saying that $\tau$ is a correctly formed accepting computation transcript for machine $e$ on input $x$, ignoring only whether the oracle answers written in the transcript are true. Then the transcript is a genuine accepting computation relative to $\varnothing^{(n)}$ exactly when all of its yes answers are true and all of its no answers are true. Thus \begin{align*} x \in A \iff \exists \tau \in \mathbb{N}\, \left[ C_e(x,\tau) \wedge \bigwedge_{q \in Q_+(\tau)} q \in \varnothing^{(n)} \wedge \bigwedge_{q \in Q_-(\tau)} q \notin \varnothing^{(n)} \right]. \end{align*} Now we translate the oracle conditions into arithmetical formulas. By definition, \begin{align*} \varnothing^{(n)} = (\varnothing^{(n-1)})' \end{align*} is computably enumerable relative to $\varnothing^{(n-1)}$. Applying the induction hypothesis at level $n$, this gives \begin{align*} \varnothing^{(n)} \in \Sigma^0_n. \end{align*} Therefore each positive oracle assertion $q \in \varnothing^{(n)}$ has a $\Sigma^0_n$ definition. Its negation $q \notin \varnothing^{(n)}$ has a $\Pi^0_n$ definition. Because the transcript contains only finitely many queries, we have only finitely many such $\Sigma^0_n$ and $\Pi^0_n$ conditions. Finite conjunctions can be placed into prenex normal form by grouping like quantifier blocks and adding dummy quantified variables where needed. The positive and negative oracle conditions therefore produce a formula of arithmetical complexity at most one level above $n$ once the existential transcript variable $\tau$ is placed at the front. The resulting formula has the form required for $\Sigma^0_{n+1}$. Hence $A \in \Sigma^0_{n+1}$. [/guided] [/step] [step:Derive the $\Pi$-clause by complement duality] For every $m \geq 1$ and every set $B \subset \mathbb{N}$, the arithmetical hierarchy is defined so that \begin{align*} B \in \Pi^0_m \iff \mathbb{N} \setminus B \in \Sigma^0_m. \end{align*} Applying the already proved $\Sigma$-clause at level $m = n$ to $\mathbb{N} \setminus A$ gives \begin{align*} A \in \Pi^0_n &\iff \mathbb{N} \setminus A \in \Sigma^0_n\\ &\iff \mathbb{N} \setminus A \text{ is computably enumerable relative to } \varnothing^{(n-1)}. \end{align*} This proves the $\Pi$-clause. [/step] [step:Derive the $\Delta$-clause from relative enumerability of a set and its complement] By definition, \begin{align*} A \in \Delta^0_n \iff A \in \Sigma^0_n \text{ and } A \in \Pi^0_n. \end{align*} Using the $\Sigma$- and $\Pi$-clauses already proved, this is equivalent to saying that both $A$ and $\mathbb{N} \setminus A$ are computably enumerable relative to $\varnothing^{(n-1)}$. If $A \le_T \varnothing^{(n-1)}$, then an oracle machine deciding $A$ relative to $\varnothing^{(n-1)}$ enumerates $A$ by outputting exactly those inputs on which it answers yes, and enumerates $\mathbb{N} \setminus A$ by outputting exactly those inputs on which it answers no. Thus both $A$ and its complement are computably enumerable relative to $\varnothing^{(n-1)}$. Conversely, suppose $A$ and $\mathbb{N} \setminus A$ are computably enumerable relative to $\varnothing^{(n-1)}$. To decide whether $x \in A$ using oracle $\varnothing^{(n-1)}$, run the two relative enumerations in dovetailing fashion until $x$ appears in one of them. Since exactly one of $A$ and $\mathbb{N} \setminus A$ contains $x$, one of the two searches halts and gives the correct answer. Hence $A \le_T \varnothing^{(n-1)}$. Therefore \begin{align*} A \in \Delta^0_n \iff A \le_T \varnothing^{(n-1)}. \end{align*} Combining this with the $\Sigma$- and $\Pi$-clauses proves Post's Theorem. [/step]