Arithmetische Hierarchie

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

Klassifikation von Formeln[Bearbeiten]

Die arithmetische Hierarchie klassifiziert Formeln in der Sprache der Peano-Arithmetik in Klassen namens \Sigma^0_n, \Pi^0_n und \Delta^0_n 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^0_n liegt, dann liegt \varphi in \Sigma^0_{n+1}.
  • Wenn \varphi äquivalent zu einer Formel \forall x_1 \forall x_2\cdots \forall x_k  \psi ist, wobei \psi in \Sigma^0_n liegt, dann liegt \varphi in \Pi^0_{n+1}.
  • \Delta^0_n = \Sigma^0_n \cap \Pi^0_n (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^0_n-Formel steht zuerst ein Existenzquantor; bei einer \Pi^0_n-Formel ein Allquantor. Jede \Pi^0_n-Formel ist äquivalent zur Negation einer \Sigma^0_n-Formel.

Da zu jeder Formel redundante Quantoren, die keine vorkommende Variable binden, hinzugefügt werden können, liegen alle Formeln in \Sigma^0_n oder \Pi^0_n auch in \Sigma^0_m und \Pi^0_m 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[Bearbeiten]

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^0_n, \Pi^0_n, oder \Delta^0_n, 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[Bearbeiten]

Die entscheidbaren Mengen sind genau die \Delta^0_1-Mengen. Die rekursiv aufzählbaren Mengen entsprechen den \Sigma^0_1-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 ≥ 1:

Literatur[Bearbeiten]

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