Arithmetische Hierarchie

Die Arithmetische Hierarchie i​st ein Konzept d​er mathematischen Logik. Sie klassifiziert Mengen v​on natürlichen Zahlen, d​ie in d​er Sprache d​er Peano-Arithmetik definierbar sind, n​ach der Komplexität i​hrer Definitionen. Die arithmetisch definierbaren Mengen werden a​uch als arithmetisch bezeichnet. Die arithmetische Hierarchie spielt e​ine wichtige Rolle i​n der Berechenbarkeitstheorie. Die hyperarithmetische Hierarchie u​nd die analytische Hierarchie erweitern d​ie arithmetische Hierarchie n​ach oben.

Definition

Klassifikation von Formeln

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

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

• Wenn ${\displaystyle \varphi }$ äquivalent zu einer Formel ${\displaystyle \exists x_{1}\exists x_{2}\cdots \exists x_{k}\psi }$ ist, wobei ${\displaystyle \psi }$ in ${\displaystyle \Pi _{n}^{0}}$ liegt, dann liegt ${\displaystyle \varphi }$ in ${\displaystyle \Sigma _{n+1}^{0}}$.
• Wenn ${\displaystyle \varphi }$ äquivalent zu einer Formel ${\displaystyle \forall x_{1}\forall x_{2}\cdots \forall x_{k}\psi }$ ist, wobei ${\displaystyle \psi }$ in ${\displaystyle \Sigma _{n}^{0}}$ liegt, dann liegt ${\displaystyle \varphi }$ in ${\displaystyle \Pi _{n+1}^{0}}$.
• ${\displaystyle \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 ${\displaystyle \Sigma _{n}^{0}}$-Formel steht zuerst ein Existenzquantor; bei einer ${\displaystyle \Pi _{n}^{0}}$-Formel ein Allquantor. Jede ${\displaystyle \Pi _{n}^{0}}$-Formel ist äquivalent zur Negation einer ${\displaystyle \Sigma _{n}^{0}}$-Formel.

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

Alternativ kann die niedrigste Klasse ${\displaystyle \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 ${\displaystyle \varphi (x)}$ in der Sprache der Peano-Arithmetik definiert, wenn X genau die Zahlen enthält, die ${\displaystyle \varphi (x)}$ erfüllen, d. h.:

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

wobei ${\displaystyle {\underline {n}}}$ der Term in der Sprache der Arithmetik ist, der die Zahl ${\displaystyle 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 ${\displaystyle \Sigma _{n}^{0}}$, ${\displaystyle \Pi _{n}^{0}}$, oder ${\displaystyle \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 ${\displaystyle \Delta _{1}^{0}}$-Mengen. Die rekursiv aufzählbaren Mengen sind die ${\displaystyle \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 ${\displaystyle n\geq 1}$:

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

Literatur

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