## [Arithmetische Hierarchie](/de/node/60138) Definition 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 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 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 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 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 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 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 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 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.