Arithmetical hierarchy

Definition

Work in the first-order language of arithmetic with symbols $0$, $S$, $+$, $\cdot$ and $<$, interpreted in the standard model $\N$ of the natural numbers. A bounded quantifier has the form $\exists x < t$ or $\forall x < t$, where $t$ is a term not containing $x$. The classes of formulas $\Sigma_n$ and $\Pi_n$ are defined by induction on $n$.

1. $\Sigma_0 = \Pi_0$ is the class of formulas in which every quantifier is bounded.
2. A formula is $\Sigma_{n+1}$ if it has the form $\exists x_1 \cdots \exists x_k \, \psi$ with $\psi$ in $\Pi_n$.
3. A formula is $\Pi_{n+1}$ if it has the form $\forall x_1 \cdots \forall x_k \, \psi$ with $\psi$ in $\Sigma_n$.

A set $A \subseteq \N^m$ is $\Sigma^0_n$ if $A = \set{\bar a : \N \models \varphi(\bar a)}$ for some $\Sigma_n$ formula $\varphi$, and $\Pi^0_n$ if the same holds with a $\Pi_n$ formula. A set is $\Delta^0_n$ if it is both $\Sigma^0_n$ and $\Pi^0_n$. A set is arithmetical if it is $\Sigma^0_n$ for some $n$.