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.

DefinitionBearbeiten

Klassifikation von FormelnBearbeiten

Die arithmetische Hierarchie klassifiziert Formeln in der Sprache der Peano-Arithmetik in Klassen namens  ,   und   für natürliche Zahlen n.

Die niedrigste Stufe bilden Formeln, die eine entscheidbare Relation definieren. Diese bilden die Klasse  . Die weiteren Klassen werden für jede Zahl n induktiv wie folgt definiert:

  • Wenn   äquivalent zu einer Formel   ist, wobei   in   liegt, dann liegt   in  .
  • Wenn   äquivalent zu einer Formel   ist, wobei   in   liegt, dann liegt   in  .
  •   (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  -Formel steht zuerst ein Existenzquantor; bei einer  -Formel ein Allquantor. Jede  -Formel ist äquivalent zur Negation einer  -Formel.

Da zu jeder Formel redundante Quantoren, die keine vorkommende Variable binden, hinzugefügt werden können, liegen alle Formeln in   oder   auch in   und   für alle m > n.

Alternativ kann die niedrigste Klasse   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 RelationenBearbeiten

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

 

wobei   der Term in der Sprache der Arithmetik ist, der die Zahl   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  ,  , oder  , 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 BerechenbarkeitBearbeiten

Die entscheidbaren Mengen sind genau die  -Mengen. Die rekursiv aufzählbaren Mengen sind die  -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  :

  •   (der  -te Turing-Jump der leeren Menge) ist many-one vollständig für  .
  • Die Mengen in   sind genau die Mengen, die rekursiv aufzählbar in   sind.
  •   ist vollständig unter Turing-Reduktion für  .

LiteraturBearbeiten

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