[proofplan] We use the oracle-computability characterization of the arithmetical hierarchy: for each $n \geq 1$, $\Delta^0_n$ is the class of sets computable from $\varnothing^{(n-1)}$, $\Sigma^0_n$ is the class of sets computably enumerable relative to $\varnothing^{(n-1)}$, and $\Pi^0_n$ is the class of complements of such sets. The key separating set is the relativized halting set $K^{\varnothing^{(n-1)}}$, which is computably enumerable relative to $\varnothing^{(n-1)}$ but not computable from $\varnothing^{(n-1)}$ by a diagonal argument. This gives $\Delta^0_n \subsetneq \Sigma^0_n$; complementing gives $\Delta^0_n \subsetneq \Pi^0_n$; and the oracle jump decides relative c.e. and co-c.e. sets, giving the inclusions into $\Delta^0_{n+1}$. Finally, if $\Sigma^0_n=\Pi^0_n$, the separating halting set would be both c.e. and co-c.e. relative to $\varnothing^{(n-1)}$, hence computable relative to $\varnothing^{(n-1)}$, contradicting diagonalization. [/proofplan] [step:Fix the oracle level and recall the hierarchy characterization] Fix $n \in \mathbb{N}$, and define the oracle set \begin{align*} A := \varnothing^{(n-1)} \subseteq \mathbb{N}. \end{align*} We use the standard oracle characterization of the arithmetical hierarchy, namely [Post's Theorem](/theorems/5425) (citing a result not yet in the wiki: Post's Theorem): \begin{align*} \Delta^0_n &= \{B \subseteq \mathbb{N} : B \leq_T A\},\\ \Sigma^0_n &= \{B \subseteq \mathbb{N} : B \text{ is computably enumerable relative to } A\},\\ \Pi^0_n &= \{B \subseteq \mathbb{N} : \mathbb{N}\setminus B \text{ is computably enumerable relative to } A\}, \end{align*} and \begin{align*} \Delta^0_{n+1}=\{B \subseteq \mathbb{N}: B \leq_T A'\}, \end{align*} where $A'$ denotes the Turing jump of $A$. Since every $A$-computable set is $A$-computably enumerable by running its $A$-oracle decision procedure and enumerating exactly the accepted inputs, we have \begin{align*} \Delta^0_n \subseteq \Sigma^0_n. \end{align*} Since the complement of an $A$-computable set is also $A$-computable, every $A$-computable set is also co-c.e. relative to $A$, so \begin{align*} \Delta^0_n \subseteq \Pi^0_n. \end{align*} [guided] Fix $n \in \mathbb{N}$ and write \begin{align*} A := \varnothing^{(n-1)}. \end{align*} This notation isolates the only oracle used at level $n$. The standard bridge between quantifier definitions and oracle computation is Post's Theorem (citing a result not yet in the wiki: Post's Theorem). In the form needed here, it identifies \begin{align*} \Delta^0_n &= \{B \subseteq \mathbb{N} : B \leq_T A\},\\ \Sigma^0_n &= \{B \subseteq \mathbb{N} : B \text{ is computably enumerable relative to } A\},\\ \Pi^0_n &= \{B \subseteq \mathbb{N} : \mathbb{N}\setminus B \text{ is computably enumerable relative to } A\}, \end{align*} and \begin{align*} \Delta^0_{n+1}=\{B \subseteq \mathbb{N}: B \leq_T A'\}. \end{align*} Why do the basic inclusions $\Delta^0_n \subseteq \Sigma^0_n$ and $\Delta^0_n \subseteq \Pi^0_n$ follow immediately from this? If $B \in \Delta^0_n$, then $B$ has an $A$-oracle decision procedure. To enumerate $B$ relative to $A$, run that decision procedure on each input $k \in \mathbb{N}$ and print $k$ exactly when the procedure accepts. Thus $B$ is c.e. relative to $A$, so $B \in \Sigma^0_n$. Also, the complement $\mathbb{N}\setminus B$ is decidable by the same oracle decision procedure with the answer reversed, so $\mathbb{N}\setminus B$ is c.e. relative to $A$. Hence $B \in \Pi^0_n$. [/guided] [/step] [step:Separate $\Delta^0_n$ from $\Sigma^0_n$ using the relativized halting set] Define the relativized diagonal halting set \begin{align*} K^A := \{e \in \mathbb{N} : \Phi^A_e(e) \text{ halts}\}, \end{align*} where $(\Phi^A_e)_{e \in \mathbb{N}}$ is a fixed effective enumeration of all partial $A$-oracle computable functions $\mathbb{N} \rightharpoonup \mathbb{N}$. The set $K^A$ is computably enumerable relative to $A$: on input $e$, simulate the $A$-oracle computation $\Phi^A_e(e)$ and enumerate $e$ if the simulation halts. Therefore $K^A \in \Sigma^0_n$. We prove that $K^A \notin \Delta^0_n$. Suppose, toward a contradiction, that $K^A \leq_T A$. Then there is a total $A$-oracle computable function \begin{align*} D: \mathbb{N} \to \{0,1\} \end{align*} such that $D(e)=1$ exactly when $e \in K^A$. Define a partial $A$-oracle computable function \begin{align*} G: \mathbb{N} \rightharpoonup \mathbb{N} \end{align*} as follows: on input $x \in \mathbb{N}$, compute $D(x)$; if $D(x)=0$, halt and output $0$; if $D(x)=1$, run forever. Since $(\Phi^A_e)_{e \in \mathbb{N}}$ enumerates all partial $A$-oracle computable functions, choose $g \in \mathbb{N}$ such that \begin{align*} G = \Phi^A_g. \end{align*} Then \begin{align*} g \in K^A &\iff \Phi^A_g(g) \text{ halts} \\ &\iff G(g) \text{ halts} \\ &\iff D(g)=0 \\ &\iff g \notin K^A, \end{align*} a contradiction. Hence $K^A \notin \Delta^0_n$, and therefore \begin{align*} \Delta^0_n \subsetneq \Sigma^0_n. \end{align*} [/step] [step:Complement the separating set to separate $\Delta^0_n$ from $\Pi^0_n$] Define \begin{align*} C^A := \mathbb{N}\setminus K^A. \end{align*} Since $K^A$ is c.e. relative to $A$, its complement $C^A$ is co-c.e. relative to $A$, so \begin{align*} C^A \in \Pi^0_n. \end{align*} If $C^A \in \Delta^0_n$, then $C^A \leq_T A$, and therefore its complement $K^A$ would also be computable from $A$, contradicting the previous step. Thus $C^A \notin \Delta^0_n$, and hence \begin{align*} \Delta^0_n \subsetneq \Pi^0_n. \end{align*} [/step] [step:Use the next jump to place $\Sigma^0_n$ and $\Pi^0_n$ inside $\Delta^0_{n+1}$] Let $B \in \Sigma^0_n$. By the oracle characterization, $B$ is c.e. relative to $A$, so there is an index $e \in \mathbb{N}$ such that an $A$-oracle machine enumerates $B$. For each input $x \in \mathbb{N}$, membership $x \in B$ is equivalent to the assertion that the corresponding $A$-oracle enumeration computation eventually prints $x$. This is an $A$-oracle halting question, and hence is decidable by $A'$. Therefore $B \leq_T A'$, so $B \in \Delta^0_{n+1}$. Thus \begin{align*} \Sigma^0_n \subseteq \Delta^0_{n+1}. \end{align*} Let $B \in \Pi^0_n$. Then $\mathbb{N}\setminus B$ is c.e. relative to $A$, so by the preceding paragraph $\mathbb{N}\setminus B \leq_T A'$. Since $A'$ can decide the complement, it can decide $B$ by reversing the answer. Hence $B \leq_T A'$, and therefore \begin{align*} \Pi^0_n \subseteq \Delta^0_{n+1}. \end{align*} [/step] [step:Show the inclusions into $\Delta^0_{n+1}$ are proper] The set $K^A$ belongs to $\Sigma^0_n$, and therefore belongs to $\Delta^0_{n+1}$ by the previous step. Since $K^A \notin \Delta^0_n$, the inclusion \begin{align*} \Delta^0_n \subsetneq \Delta^0_{n+1} \end{align*} is proper. Because \begin{align*} \Pi^0_n \subseteq \Delta^0_{n+1}, \end{align*} it remains only to exhibit an element of $\Delta^0_{n+1}$ not in $\Pi^0_n$. The set $K^A$ itself does this. If $K^A \in \Pi^0_n$, then $\mathbb{N}\setminus K^A$ would be c.e. relative to $A$. Since $K^A$ is already c.e. relative to $A$, we could decide $K^A$ using $A$ by dovetailing the two relative enumerations: on input $x$, run the enumeration of $K^A$ and the enumeration of $\mathbb{N}\setminus K^A$ in parallel until one prints $x$; exactly one of the two enumerations must eventually print $x$. This would make $K^A$ computable from $A$, contradicting the diagonal argument. Therefore $K^A \notin \Pi^0_n$, and hence \begin{align*} \Pi^0_n \subsetneq \Delta^0_{n+1}. \end{align*} Similarly, $C^A=\mathbb{N}\setminus K^A$ belongs to $\Pi^0_n \subseteq \Delta^0_{n+1}$, but $C^A \notin \Sigma^0_n$. Indeed, if $C^A \in \Sigma^0_n$, then both $K^A$ and $C^A$ would be c.e. relative to $A$, and the same dovetailing argument would make $K^A$ computable from $A$, contradiction. Therefore \begin{align*} \Sigma^0_n \subsetneq \Delta^0_{n+1}. \end{align*} [guided] We already know $K^A \in \Sigma^0_n$ and $K^A \notin \Delta^0_n$. The previous step showed that every $\Sigma^0_n$ set is decidable from $A'$, so \begin{align*} K^A \in \Delta^0_{n+1}. \end{align*} Thus there is at least one set in $\Delta^0_{n+1}$ that is not in $\Delta^0_n$, namely $K^A$. Now we must prove the stronger strict inclusions \begin{align*} \Sigma^0_n \subsetneq \Delta^0_{n+1}, \qquad \Pi^0_n \subsetneq \Delta^0_{n+1}. \end{align*} For $\Pi^0_n$, the witness is again $K^A$. Suppose $K^A \in \Pi^0_n$. By definition of $\Pi^0_n$, the complement $\mathbb{N}\setminus K^A$ would be c.e. relative to $A$. But $K^A$ is also c.e. relative to $A$. Having both a relative enumeration of a set and a relative enumeration of its complement gives a relative decision procedure: on input $x$, run the two enumerations in parallel until one of them prints $x$. Since every natural number lies in exactly one of $K^A$ and $\mathbb{N}\setminus K^A$, one of the two searches terminates; if the first enumeration prints $x$, accept, and if the second prints $x$, reject. This makes $K^A$ computable from $A$, contradicting the diagonal argument. Hence $K^A \notin \Pi^0_n$, while $K^A \in \Delta^0_{n+1}$, so \begin{align*} \Pi^0_n \subsetneq \Delta^0_{n+1}. \end{align*} For $\Sigma^0_n$, use the complementary witness \begin{align*} C^A := \mathbb{N}\setminus K^A. \end{align*} Since $K^A$ is c.e. relative to $A$, the set $C^A$ is co-c.e. relative to $A$, so $C^A \in \Pi^0_n$. The inclusion already proved gives $C^A \in \Delta^0_{n+1}$. If $C^A$ were also in $\Sigma^0_n$, then both $C^A$ and its complement $K^A$ would be c.e. relative to $A$, and the same dovetailing procedure would decide $K^A$ from $A$. This again contradicts $K^A \notin \Delta^0_n$. Therefore $C^A \notin \Sigma^0_n$, and \begin{align*} \Sigma^0_n \subsetneq \Delta^0_{n+1}. \end{align*} [/guided] [/step] [step:Derive $\Sigma^0_n \neq \Pi^0_n$ from the same separating set] Since $K^A \in \Sigma^0_n$ and $K^A \notin \Pi^0_n$, the two classes cannot be equal: \begin{align*} \Sigma^0_n \neq \Pi^0_n. \end{align*} Combining the strict inclusions proved above gives, for the fixed $n$, \begin{align*} \Delta^0_n \subsetneq \Sigma^0_n \subsetneq \Delta^0_{n+1}, \qquad \Delta^0_n \subsetneq \Pi^0_n \subsetneq \Delta^0_{n+1}, \end{align*} and \begin{align*} \Sigma^0_n \neq \Pi^0_n. \end{align*} Because $n \in \mathbb{N}$ was arbitrary, the result holds for every finite level of the arithmetical hierarchy. [/step]