Arithmetische Hierarchie

Die Arithmetische Hierarchie ist ein Konzept der mathematischen Logik. Sie klassifiziert Mengen von natürlichen Zahlen, die in der Sprache der Peano-Arithmetik definierbar sind, nach der Komplexität ihrer Definitionen. Die arithmetisch definierbaren Mengen werden auch als arithmetisch bezeichnet. Die arithmetische Hierarchie spielt eine wichtige Rolle in der Berechenbarkeitstheorie. Die hyperarithmetische Hierarchie und die analytische Hierarchie erweitern die arithmetische Hierarchie nach oben.

Definition

Klassifikation von Formeln

Die arithmetische Hierarchie klassifiziert Formeln in der Sprache der Peano-Arithmetik in Klassen namens $\Sigma _{n}^{0}$, $\Pi _{n}^{0}$ und $\Delta _{n}^{0}$ für natürliche Zahlen n.

Die niedrigste Stufe bilden Formeln, die eine entscheidbare Relation definieren. Diese bilden die Klasse $\Delta _{0}^{0}=\Pi _{0}^{0}=\Sigma _{0}^{0}$. Die weiteren Klassen werden für jede Zahl n induktiv wie folgt definiert:

• Wenn $\varphi$ äquivalent zu einer Formel $\exists x_{1}\exists x_{2}\cdots \exists x_{k}\psi$ ist, wobei $\psi$ in $\Pi _{n}^{0}$ liegt, dann liegt $\varphi$ in $\Sigma _{n+1}^{0}$.
• Wenn $\varphi$ äquivalent zu einer Formel $\forall x_{1}\forall x_{2}\cdots \forall x_{k}\psi$ ist, wobei $\psi$ in $\Sigma _{n}^{0}$ liegt, dann liegt $\varphi$ in $\Pi _{n+1}^{0}$.
• $\Delta _{n}^{0}=\Sigma _{n}^{0}\cap \Pi _{n}^{0}$ (für alle n)

Jede arithmetische Formel ist äquivalent zu einer Formel in Pränexnormalform, die abwechselnd einen All- und einen Existenzquantor hat. Bei einer $\Sigma _{n}^{0}$-Formel steht zuerst ein Existenzquantor; bei einer $\Pi _{n}^{0}$-Formel ein Allquantor. Jede $\Pi _{n}^{0}$-Formel ist äquivalent zur Negation einer $\Sigma _{n}^{0}$-Formel.

Da zu jeder Formel redundante Quantoren, die keine vorkommende Variable binden, hinzugefügt werden können, liegen alle Formeln in $\Sigma _{n}^{0}$ oder $\Pi _{n}^{0}$ auch in $\Sigma _{m}^{0}$ und $\Pi _{m}^{0}$ für alle m > n.

Alternativ kann die niedrigste Klasse $\Delta _{0}^{0}=\Pi _{0}^{0}=\Sigma _{0}^{0}$ so definiert werden, dass sie nur Formeln enthält, die zu einer Formel äquivalent sind, die nur beschränkte Quantoren hat. In diesem Fall enthält die niedrigste Klasse weniger Relationen; alle weiteren Klassen bleiben gleich.

Klassifikation von Mengen und Relationen

Eine Menge X von natürlichen Zahlen wird durch eine Formel $\varphi (x)$ in der Sprache der Peano-Arithmetik definiert, wenn X genau die Zahlen enthält, die $\varphi (x)$ erfüllen, d. h.:

$n\in X\Leftrightarrow \mathbb {N} \models \varphi ({\underline {n}}),$

wobei ${\underline {n}}$ der Term in der Sprache der Arithmetik ist, der die Zahl $n$ repräsentiert. Eine Menge heißt arithmetisch, wenn sie durch eine Formel der Peano-Arithmetik definiert wird. Eine Menge X von natürlichen Zahlen ist $\Sigma _{n}^{0}$, $\Pi _{n}^{0}$, oder $\Delta _{n}^{0}$, wenn sie durch eine Formel in der entsprechenden Klasse definiert wird. Ebenso lassen sich auch Relationen bzw. Mengen von k-Tupeln natürlicher Zahlen klassifizieren, wenn man Formeln mit k freien Variablen betrachtet.

Bezug zu Berechenbarkeit

Die entscheidbaren Mengen sind genau die $\Delta _{1}^{0}$-Mengen. Die rekursiv aufzählbaren Mengen sind die $\Sigma _{1}^{0}$-Mengen. Auch darüber hinaus gibt es eine enge Beziehung zwischen der arithmetischen Hierarchie und den Turinggraden. Nach dem Satz von Post gilt für alle $n\geq 1$:

• $\emptyset ^{(n)}$ (der $n$-te Turing-Jump der leeren Menge) ist many-one vollständig für $\Sigma _{n}^{0}$.
• Die Mengen in $\Sigma _{n+1}^{0}$ sind genau die Mengen, die rekursiv aufzählbar in $\emptyset ^{(n)}$ sind.
• $\emptyset ^{(n-1)}$ ist vollständig unter Turing-Reduktion für $\Delta _{n}^{0}$.

Literatur

• Hartley Rogers: Theory of recursive functions and effective computability. McGraw-Hill, 1967.