Die arithmetische Hierarchie

Die arithmetische Hierarchie klassifiziert Mengen natürlicher Zahlen nach der Anzahl alternierender Quantoren, die zu ihrer Definition erforderlich sind, und verknüpft so die logische Komplexität mit dem Grad der Unberechenbarkeit.

Definition

Die arithmetische Hierarchie schichtet die in der Arithmetik erster Ordnung definierbaren Mengen, indem sie die Wechsel unbeschränkter Quantoren vor einer berechenbaren Matrix zählt, wobei Sigma-n-Mengen durch einen Block definiert werden, der mit einem Existenzquantor beginnt, und Pi-n-Mengen durch einen, der mit einem Allquantor beginnt.

Scope

Dieses Thema behandelt die Klassifizierung definierbarer Mengen in die Sigma-, Pi- und Delta-Ebenen durch Quantorenwechsel über berechenbaren Relationen, Posts Theorem, das die Hierarchie mit dem iterierten Halteproblem und Turing-Sprüngen in Beziehung setzt, die Strenge der Hierarchie und ihre Erweiterung zur analytischen Hierarchie.

Core questions

• Wie misst der Quantorenwechsel die Komplexität einer Menge?
• Wie verhalten sich die Sigma-, Pi- und Delta-Klassen auf jeder Ebene zueinander?
• Wie entspricht die Hierarchie der Iteration des Halteproblems?
• Warum ist die Hierarchie streng, wobei jede Ebene deutlich größer ist als die vorherige?

Key theories

Quantorenklassifikation

Eine Menge ist Sigma-n, wenn sie durch n alternierende Quantorenblöcke, die existentiell über einer berechenbaren Relation beginnen, definierbar ist, und Pi-n, wenn sie universell beginnen; die berechenbar aufzählbaren Mengen sind genau die Sigma-eins-Mengen.

Posts Theorem

Eine Menge ist genau dann Sigma-(n+1), wenn sie relativ zum n-ten Turing-Sprung berechenbar aufzählbar ist, wodurch die Ebenen der Hierarchie mit iterierten relativierten Halteproblemen verknüpft werden.

Strenge der Hierarchie

Jeder Turing-Sprung ist streng komplexer als der vorherige, sodass jede Ebene der arithmetischen Hierarchie die darunter liegenden Ebenen strikt enthält und die Hierarchie nicht kollabiert.

Clinical relevance

Die arithmetische Hierarchie ist der Standardmaßstab für die Komplexität definierbarer Probleme in Logik und Informatik: Sie ordnet Probleme wie Totalität, Endlichkeit und Kofinitheit berechenbarer Mengen präzisen Ebenen zu und umreißt die Grenze zwischen dem, was berechenbar aufzählbar ist, und dem, was stärkere nicht-berechenbare Ressourcen erfordert.

History

Kleene und Mostowski führten die arithmetische Hierarchie um 1943 unabhängig voneinander ein, indem sie Mengen nach der Quantorenkomplexität über berechenbaren Prädikaten klassifizierten. Posts Theorem verband die Hierarchie mit dem Turing-Sprung und vereinte die auf Definierbarkeit basierenden und die auf Berechenbarkeit basierenden Perspektiven, und der Rahmen wurde später nach oben in die analytische Hierarchie erweitert.

Key figures

• Stephen Cole Kleene
• Andrzej Mostowski
• Emil Post

Seminal works

• rogers1987
• soare1987
• cutland1980

Frequently asked questions

Was bedeutet eine höhere Ebene in der Hierarchie?

Mehr alternierende Quantoren bedeuten eine komplexere Definition und, nach Posts Theorem, ein Problem, das mehr Iterationen des Halteproblems zur Entscheidung erfordert. Mengen, die höher in der Hierarchie angesiedelt sind, sind für die Berechnung streng weniger zugänglich als die darunter liegenden.

Wo sind berechenbar aufzählbare Mengen angesiedelt?

Sie befinden sich auf der Sigma-eins-Ebene, definierbar durch einen einzelnen Existenzquantor über einer berechenbaren Relation. Ihre Komplemente befinden sich auf der Pi-eins-Ebene, und die Mengen, die beides sind, die Delta-eins-Mengen, sind genau die berechenbaren Mengen.