auch Kleene-Hierarchie genannt, eine echte Hierarchie

\begin{eqnarray}{{\rm{\Sigma }}}_{0}^{0}\subset {{\rm{\Sigma }}}_{1}^{0}\subset {{\rm{\Sigma }}}_{2}^{0}\subset \cdots \end{eqnarray}

von Mengen, bestehend aus Teilmengen von \({{{\rm{{\mathbb{N}}}}}_{0}}^{k}\). Hierbei sind \({{\rm{\Sigma }}}_{0}^{0}\) die entscheidbaren Mengen (Entscheidbarkeit) und \({{\rm{\Sigma }}}_{1}^{0}\) die rekursiv aufzählbaren Mengen.

Allgemein liegt eine Menge \(A\subseteq {{\rm{{\mathbb{N}}}}}_{0}{}^{k}\) in \({{\rm{\Sigma }}}_{k}^{0}\) wenn sie sich wie folgt charakterisieren läßt:

\begin{eqnarray}x\in A\iff \exists {y}_{1}\forall {y}_{2}\ldots Q{y}_{k}P(x,{y}_{1},{y}_{2},\ldots, {y}_{k}).\end{eqnarray}

Hierbei ist Q = ∃, falls k ungerade, sonst Q = ∀, und P ist ein entscheidbares Prädikat.

Mit

\begin{eqnarray}{\Pi }_{k}^{0}=\{A|\bar{A}\in {{\rm{\Sigma }}}_{k}^{0}\}\end{eqnarray}

bezeichnet man die Menge der Komplementmengen der Mengen in \({{\rm{\Sigma }}}_{k}^{0}\). Diese lassen sich analog charakterisieren, mit dem Unterschied, daß die alternierende Quantorenfolge mit ∀ beginnen muß. Es gilt:

\begin{eqnarray}{{\rm{\Sigma }}}_{k}^{0}\cup {\Pi }_{k}^{0}\subset {{\rm{\Sigma }}}_{k+1}^{0}\cap {\Pi }_{k+1}^{0}.\end{eqnarray}

Eine Funktion, deren Graph {(n, f(n)) | n ∈ ℕ₀} in der arithmetischen Hierarchie liegt, bezeichnet man als arithmetisch repräsentierbar.