Definition:Arithmetical Hierarchy

Definition

For every $i \in \N$, $\Sigma_i$ and $\Pi_i$ are sets of well-formed formulae in the language of arithmetic.

They are defined recursively as follows:

Let $\phi$ be logically equivalent to a well-formed formula in the language of arithmetic containing no quantifiers.

Then $\phi \in \Sigma_0$ and $\phi \in \Pi_0$

Let $\phi$ be logically equivalent to $Q_1 Q_2 \dotsm Q_k \psi$ where:

$\psi \in \Pi_n$
$Q_j$ is either $\exists x$ or $\forall x < y$, for some variable $x$ and term $y$

Then $\phi \in \Sigma_{n \mathop + 1}$.

Let $\phi$ be logically equivalent to $Q_1 Q_2 \dotsm Q_k \psi$ where:

$\psi \in \Sigma_n$
$Q_j$ is either $\forall x$ or $\exists x < y$, for some variable $x$ and term $y$

Then $\phi \in \Pi_{n \mathop + 1}$.