In der mathematischen Logik, der arithmetischen Hierarchie, arithmetischen Hierarchie oder Hierarchie von Kleene-Mostowski klassifiziert bestimmte Sätze, die auf der Kompliziertheit von Formeln gestützt sind, die sie definieren. Jeder Satz, der eine Klassifikation erhält, wird arithmetisch genannt.

Die arithmetische Hierarchie ist in der recursion Theorie, wirksamen beschreibenden Mengenlehre und der Studie von formellen Theorien wie Arithmetik von Peano wichtig.

Der Algorithmus von Tarski-Kuratowski stellt eine leichte Weise zur Verfügung, zu einem oberen die Klassifikationen binden zu lassen, die einer Formel und dem Satz zugeteilt sind, den er definiert.

Die hyperarithmetische Hierarchie und die analytische Hierarchie erweitern die arithmetische Hierarchie, um zusätzliche Formeln und Sätze zu klassifizieren.

Die arithmetische Hierarchie von Formeln

Die arithmetische Hierarchie teilt Klassifikationen den Formeln auf der Sprache der Arithmetik der ersten Ordnung zu. Die Klassifikationen werden angezeigt und für natürliche Zahlen n (einschließlich 0). Die griechischen Briefe hier sind lightface Symbole, der anzeigt, dass die Formeln aufgestellte Parameter nicht enthalten.

Wenn eine Formel zu einer Formel mit nur begrenztem quantifiers logisch gleichwertig ist, dann wird die Klassifikationen zugeteilt und.

Die Klassifikationen und werden induktiv für jede natürliche Zahl n das Verwenden der folgenden Regeln definiert:

• Wenn zu einer Formel der Form logisch gleichwertig ist, wo ist, dann die Klassifikation zugeteilt wird.

Wenn zu einer Formel der Form logisch gleichwertig ist, wo ist, dann die Klassifikation zugeteilt wird.

Außerdem ist eine Formel zu einer Formel gleichwertig, die mit einem existenziellen quantifiers beginnt und Zeiten zwischen der Reihe von existenziellem und universalem quantifiers abwechseln lässt; während eine Formel zu einer Formel gleichwertig ist, die mit einem universalen quantifiers und Stellvertretern ähnlich beginnt.

Weil jede Formel zu einer Formel in der prenex normalen Form gleichwertig ist, wird jede Formel ohne Satz quantifiers mindestens eine Klassifikation zugeteilt. Weil überflüssiger quantifiers zu jeder Formel hinzugefügt werden kann, einmal wird eine Formel die Klassifikation zugeteilt, oder es wird die Klassifikationen und für jede M größer zugeteilt als n. Die wichtigste einer Formel zugeteilte Klassifikation ist so diejenige mit kleinstem n, weil das genug ist, um alle anderen Klassifikationen zu bestimmen.

Die arithmetische Hierarchie von Sätzen von natürlichen Zahlen

Ein Satz X von natürlichen Zahlen wird durch die Formel &phi definiert; auf der Sprache der Arithmetik von Peano, wenn die Elemente X genau die Zahlen sind, die &phi befriedigen;. d. h. für alle natürlichen Zahlen n,

:

wo die Ziffer auf der Sprache der Arithmetik entsprechend ist. Ein Satz ist in der ersten Ordnungsarithmetik definierbar, wenn es durch eine Formel auf der Sprache der Arithmetik von Peano definiert wird.

Jeder Satz, sind X von natürlichen Zahlen, der in der ersten Ordnungsarithmetik definierbar ist, zugeteilte Klassifikationen der Form, und, wo eine natürliche Zahl wie folgt ist. Wenn X durch eine Formel dann X definierbar ist, wird die Klassifikation zugeteilt. Wenn X durch eine Formel dann X definierbar ist, wird die Klassifikation zugeteilt. Wenn X beide ist und dann die zusätzliche Klassifikation zugeteilt wird.

Bemerken Sie, dass es selten Sinn hat, von Formeln zu sprechen; der erste quantifier einer Formel ist entweder existenziell oder universal. So wird ein Satz durch eine Formel nicht definiert; eher gibt es beide und Formeln, die den Satz definieren.

Eine parallele Definition wird verwendet, um die arithmetische Hierarchie auf begrenzten Kartesianischen Mächten der natürlichen Zahlen zu definieren. Statt Formeln mit einer freier Variable werden Formeln mit k freien Zahl-Variablen verwendet, um die arithmetische Hierarchie auf Sätzen von K-Tupeln von natürlichen Zahlen zu definieren.

Relativierte arithmetische Hierarchien

Da wir definieren können, was es für einen Satz X bedeutet, hinsichtlich eines anderen Satzes Y rekursiv zu sein, indem es der Berechnung erlaubt wird, die X definiert, Y als ein Orakel zu befragen, können wir diesen Begriff zur ganzen arithmetischen Hierarchie erweitern und definieren, was es für X bedeutet, oder in Y, angezeigt beziehungsweise zu sein, und. Um so zu tun, befestigen Sie eine Reihe von ganzen Zahlen Y und fügen Sie ein Prädikat für die Mitgliedschaft in Y in die Sprache der Arithmetik von Peano hinzu. Wir sagen dann, dass X darin ist, wenn es durch eine Formel auf dieser ausgebreiteten Sprache definiert wird. Mit anderen Worten X ist, wenn es durch eine Formel definiert wird, die erlaubt ist, Fragen über die Mitgliedschaft in Y zu stellen. Wechselweise kann man die Sätze als jene Sätze ansehen, die gebaut werden können, mit Sätzen anfangend, die in Y rekursiv sind und wechselweise vorspringend, und sich das Nehmen der Ergänzungen von diesen zu n Zeiten niederlässt.

Lassen Sie zum Beispiel Y eine Reihe von ganzen Zahlen sein. Gelassen X, der Satz von durch ein Element von Y. Then X teilbaren Zahlen sein, wird durch die Formel definiert, so X ist darin (wirklich, ist es in ebenso, seitdem wir gebunden beide quantifiers durch n gekonnt haben).

Arithmetik reducibility und Grade

Arithmetischer reducibility ist ein Zwischenbegriff zwischen Turing reducibility und Hyperarithmetik reducibility.

Ein Satz ist (auch Arithmetik arithmetisch und arithmetisch definierbar), wenn es durch eine Formel auf der Sprache der Arithmetik von Peano definiert wird. Gleichwertig X ist arithmetisch, wenn X ist oder für eine ganze Zahl n. Ein Satz X ist in einem Satz Y, angezeigt arithmetisch, wenn X eine Formel auf der Sprache der Arithmetik von Peano definierbar ist, die durch ein Prädikat für die Mitgliedschaft in Y erweitert ist. Gleichwertig, X ist in Y arithmetisch, wenn X in oder für eine ganze Zahl n ist. Ein Synonym dafür ist: X ist auf Y arithmetisch reduzierbar.

Die Beziehung ist reflexiv und, und so die Beziehung transitiv, die durch die Regel definiert ist

:

ist eine Gleichwertigkeitsbeziehung. Die Gleichwertigkeitsklassen dieser Beziehung werden die arithmetischen Grade genannt; unter ihnen wird teilweise bestellt.

Die arithmetische Hierarchie von Teilmengen des Raums von Cantor und Baire

Der Kantor-Raum, angezeigt, ist der Satz aller unendlichen Folgen von 0s und 1s; der Raum von Baire, angezeigt oder, ist der Satz aller unendlichen Folgen von natürlichen Zahlen. Bemerken Sie, dass Elemente des Kantor-Raums mit Sätzen von ganzen Zahlen und Elementen des Raums von Baire mit Funktionen von ganzen Zahlen bis ganze Zahlen identifiziert werden können.

Der gewöhnliche axiomatization der Arithmetik der zweiten Ordnung verwendet eine Satz-basierte Sprache, auf der der Satz quantifiers als Quantitätsbestimmung über den Kantor-Raum natürlich angesehen werden kann. Eine Teilmenge des Kantor-Raums wird die Klassifikation zugeteilt, wenn es durch eine Formel definierbar ist. Der Satz wird die Klassifikation zugeteilt, wenn es durch eine Formel definierbar ist. Wenn der Satz beide ist und dann er die zusätzliche Klassifikation gegeben wird. Lassen Sie zum Beispiel, der Satz aller unendlichen binären Schnuren zu sein, die nicht der ganze 0 (oder gleichwertig der Satz aller nichtleeren Sätze von ganzen Zahlen) sind. Da wir sehen, dass das durch eine Formel definiert wird und folglich ein Satz ist.

Bemerken Sie dass, während beide die Elemente des Kantor-Raums (betrachtet als Sätze von ganzen Zahlen) und Teilmengen des Kantor-Raums in arithmetischen Hierarchien klassifiziert werden, aber das ist nicht dieselbe Hierarchie. Tatsächlich ist die Beziehung zwischen den zwei Hierarchien interessant und nichttrivial. Zum Beispiel sind die Elemente des Kantor-Raums nicht (im Allgemeinen) dasselbe als die Elemente des Kantor-Raums, so dass eine Teilmenge des Kantor-Raums ist. Jedoch verbinden viele interessante Ergebnisse die zwei Hierarchien.

Es gibt zwei Weisen, wie eine Teilmenge des Raums von Baire in der arithmetischen Hierarchie klassifiziert werden kann.

• Eine Teilmenge des Raums von Baire hat eine entsprechende Teilmenge des Kantor-Raums laut der Karte, die jede Funktion von zu bis die charakteristische Funktion seines Graphen nimmt. Eine Teilmenge des Raums von Baire wird die Klassifikation gegeben, oder wenn, und nur wenn die entsprechende Teilmenge des Kantor-Raums dieselbe Klassifikation hat.
• Eine gleichwertige Definition der analytischen Hierarchie auf dem Raum von Baire wird durch das Definieren der analytischen Hierarchie von Formeln mit einer funktionellen Version der Arithmetik der zweiten Ordnung gegeben; dann kann die analytische Hierarchie auf Teilmengen des Kantor-Raums von der Hierarchie auf dem Raum von Baire definiert werden. Diese abwechselnde Definition gibt genau dieselben Klassifikationen wie die erste Definition.

Eine parallele Definition wird verwendet, um die arithmetische Hierarchie auf begrenzten Kartesianischen Mächten des Raums von Baire oder Kantor-Raums mit Formeln mit mehreren freien Variablen zu definieren. Die arithmetische Hierarchie kann auf jedem wirksamen polnischen Raum definiert werden; die Definition ist für den Kantor-Raum und Raum von Baire besonders einfach, weil sie mit der Sprache der gewöhnlichen Arithmetik der zweiten Ordnung ausrüsten.

Bemerken Sie, dass wir auch die arithmetische Hierarchie von Teilmengen der Räume von Cantor und Baire hinsichtlich eines Satzes von ganzen Zahlen definieren können. Tatsächlich ist Fettschrift gerade die Vereinigung für alle Sätze von ganzen Zahlen Y. Bemerken Sie, dass die fette Hierarchie gerade die Standardhierarchie von Sätzen von Borel ist.

Erweiterungen und Schwankungen

Es ist möglich, die arithmetische Hierarchie von Formeln mit einer Sprache zu definieren, die mit einem Funktionssymbol für jede primitive rekursive Funktion erweitert ist. Diese Schwankung ändert ein bisschen die Klassifikation von einigen Sätzen.

Eine mehr semantische Schwankung der Hierarchie kann auf allen finitary Beziehungen auf den natürlichen Zahlen definiert werden; die folgende Definition wird verwendet. Jede berechenbare Beziehung wird definiert, um zu sein, und. Die Klassifikationen und werden induktiv mit den folgenden Regeln definiert.

• Wenn die Beziehung dann die Beziehung ist, wird definiert, um zu sein

Wenn die Beziehung dann die Beziehung ist, wird definiert, um zu sein

Diese Schwankung ändert ein bisschen die Klassifikation von einigen Sätzen. Es kann erweitert werden, um finitary Beziehungen auf den natürlichen Zahlen, dem Raum von Baire und dem Kantor-Raum zu bedecken.

Bedeutung der Notation

Die folgenden Bedeutungen können der Notation für die arithmetische Hierarchie auf Formeln beigefügt werden.

Die Subschrift in den Symbolen und zeigt die Zahl von Wechseln von Blöcken der universalen und existenziellen Zahl quantifiers an, die in einer Formel verwendet werden. Außerdem ist der äußerste Block in Formeln existenziell und in Formeln universal.

Der Exponent in den Symbolen, und zeigt den Typ der Gegenstände an, die messen werden. Gegenstände des Typs 0 sind natürliche Zahlen, und Gegenstände des Typs sind Funktionen, die den Satz von Gegenständen des Typs zu den natürlichen Zahlen kartografisch darstellen. Die Quantifizierung über höhere Typ-Gegenstände, wie Funktionen von natürlichen Zahlen bis natürliche Zahlen, wird durch einen Exponenten beschrieben, der größer ist als 0, als in der analytischen Hierarchie. Der Exponent 0 zeigt quantifiers über Zahlen an, der Exponent 1 würde Quantifizierung über Funktionen von Zahlen bis Zahlen anzeigen (Gegenstände des Typs 1), der Exponent 2 würde Quantifizierung über Funktionen entsprechen, die einen Gegenstand des Typs 1 nehmen und eine Zahl und so weiter zurückgeben.

Beispiele

• Die Sätze von Zahlen sind diejenigen, die durch eine Formel der Form definierbar sind, wo nur quantifiers begrenzt hat. Diese sind genau rekursiv enumerable Sätze.
• Der Satz von natürlichen Zahlen, die Indizes für Maschinen von Turing sind, die Gesamtfunktionen schätzen, ist. Intuitiv fällt ein Index in diesen Satz, wenn, und nur wenn für jeder "es einen solchen gibt, dass die Maschine von Turing mit dem Index auf dem Eingang nach Schritten hinkt". Ein ganzer Beweis würde zeigen, dass das Eigentum, das in Notierungen im vorherigen Satz gezeigt ist, auf der Sprache der Arithmetik von Peano durch eine Formel definierbar ist.
• Jede Teilmenge des Raums von Baire oder Kantor-Raums ist ein offener Satz in der üblichen Topologie auf dem Raum. Außerdem für jeden solchen Satz gibt es eine berechenbare Enumeration von Zahlen von Gödel von grundlegenden offenen Sätzen, deren Vereinigung der ursprüngliche Satz ist. Deshalb werden Sätze manchmal effektiv offen genannt. Ähnlich wird jeder Satz geschlossen, und die Sätze werden manchmal effektiv geschlossen genannt.
• Jede arithmetische Teilmenge des Kantor-Raums des Raums von Baire ist ein Satz von Borel. Die lightface Hierarchie von Borel erweitert die arithmetische Hierarchie, um zusätzliche Sätze von Borel einzuschließen. Zum Beispiel ist jede Teilmenge des Raums von Cantor oder Baire ein Satz (d. h. ein Satz, der der Kreuzung von zählbar vielen offenen Sätzen gleichkommt). Außerdem ist jeder dieser offenen Sätze, und die Liste von Zahlen von Gödel dieser offenen Sätze hat eine berechenbare Enumeration. Wenn eine Formel mit einer freien Satz-Variable X und freien Zahl-Variablen dann ist, ist der Satz die Kreuzung der Sätze der Form als n Reihen über den Satz von natürlichen Zahlen.

Eigenschaften

Die folgenden Eigenschaften halten für die arithmetische Hierarchie von Sätzen von natürlichen Zahlen und die arithmetische Hierarchie von Teilmengen des Raums von Cantor oder Baire.

• Die Sammlungen und werden unter begrenzten Vereinigungen und begrenzten Kreuzungen ihrer jeweiligen Elemente geschlossen.
• Ein Satz ist, wenn, und nur wenn seine Ergänzung ist. Ein Satz ist, wenn, und nur wenn der Satz beide ist und, in welchem Fall seine Ergänzung auch sein wird.
• Die Einschließungen und halten dafür.
• Die Einschließungen und halten für alle, und die Einschließung hält dafür. So bricht die Hierarchie nicht zusammen.

Beziehung zu Maschinen von Turing

Die Turing berechenbaren Sätze von natürlichen Zahlen sind genau die Sätze am Niveau der arithmetischen Hierarchie. Rekursiv enumerable Sätze sind genau die Sätze am Niveau.

Keine Orakel-Maschine ist dazu fähig, sein eigenes stockendes Problem zu beheben (eine Schwankung des Beweises von Turing gilt). Das stockende Problem für ein Orakel sitzt tatsächlich darin.

Der Lehrsatz des Postens stellt eine nahe Verbindung zwischen der arithmetischen Hierarchie von Sätzen von natürlichen Zahlen und den Graden von Turing her. Insbesondere es gründet die folgenden Tatsachen für den ganzen n  1:

• Der Satz (der n-te Sprung von Turing des leeren Satzes) ist vielein ganzer darin.
• Der Satz ist vielein ganzer darin.
• Der Satz ist Turing, der darin abgeschlossen ist.

Die polynomische Hierarchie ist eine "ausführbare quellenbegrenzte" Version der arithmetischen Hierarchie, in die polynomische Länge-Grenzen auf den beteiligten Zahlen gelegt werden (oder, gleichwertig werden polynomische Zeitgrenzen auf den Maschinen von Turing beteiligt gelegt). Es gibt eine feinere Klassifikation von einigen Sätzen von natürlichen Zahlen, die am Niveau der arithmetischen Hierarchie sind.

Siehe auch

• Logik von Interpretability
• Hierarchie (Mathematik)

...