Lexikon der Mathematik: arithmetische Hierarchie
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 ∈ ℕ0} in der arithmetischen Hierarchie liegt, bezeichnet man als arithmetisch repräsentierbar.Copyright Springer Verlag GmbH Deutschland 2017
Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.