Eine Schichtung von Prädikaten und Formeln über den natürlichen Zahlen nach dem Muster und der Anzahl von Alternationen erstordentlicher Quantoren; Klassen Σ_n, Π_n und Δ_n klassifizieren Definierbarkeit und Entscheidbarkeit in der erstordentlichen Arithmetik.

Prinzip

Die Komplexität einer Formel nach dem führenden Quantor und der Anzahl der Existenz-/Allquantor-Wechsel messen; diese syntaktische Messung korreliert mit Berechenbarkeitseigenschaften und Reduzierbarkeiten zwischen Mengen natürlicher Zahlen.

Demonstration

Eine Formel der Form ∃x∀y R(x,y) (mit entscheidbarem R) gehört zu Σ_2; die Klasse Σ_1 entspricht existenziellen Formeln, deren Erweiterungen genau die rekursiv aufzählbaren Mengen sind, während Π_1 universelle (ko-rekursiv aufzählbare) Beschreibungen liefert.

Fehlanwendung

Die arithmetische Hierarchie als Maß praktischer Zeit- oder Speicherkomplexität zu behandeln oder ihre Σ/Π-Stufen mit nicht verwandten Komplexitätshierarchien über endlichen Strukturen zu verwechseln, führt zu Fehlinterpretationen dessen, was die Hierarchie erfasst.

Konsequenz

Richtige Anwendung liefert genaue Aussagen über Entscheidbarkeit, Vollständigkeit von Problemen für bestimmte Ebenen und über die Arten von Reduktionen oder Orakelzugriffen, die zur Entscheidung von Prädikaten erforderlich sind.

Umkehrung

Durch Umkehr des führenden Quantormusters wechselt man zwischen dualen Klassen (Σ_n ↔ Π_n); dabei tauschen sich existenzielle und universelle Komplexität und oft der Entscheidbarkeitscharakter (r.e. ↔ co-r.e.) aus.

Abgrenzung

Gilt für die erstordentliche Arithmetik über den natürlichen Zahlen und arithmetisch definierbare Formeln; schließt höherstufige Logiken, mengen-theoretische Hierarchien und Komplexitätsklassen, die durch Ressourcenbegrenzungen auf endlichen Strukturen definiert sind, aus.

Semantische Spannung

Spannung besteht gegenüber der analytischen Hierarchie und gegenüber Komplexitätshierarchien (z. B. polynomialer Hierarchie): Ähnliche Schichtungen unterscheiden sich in Domäne und den formalisierten Rechenressourcen.

Synthese

Die arithmetische Hierarchie ordnet arithmetische Definierbarkeit nach Quantorenalternanz, sodass die syntaktische Gestalt die Berechenbarkeit und Entscheidbarkeit vorhersagt und r.e., co-r.e. und darüber hinaus voneinander abgrenzt.