Arithmetische Hierarchie

Ein Beispiel dafür, wie die Ebenen der Hierarchie interagieren und wo einige grundlegende festgelegte Kategorien in ihr liegen.

Im Mathematische Logik, das arithmetische Hierarchie, Arithmetische Hierarchie oder Kleene - Mostowski Hierarchie (Nach Mathematikern Stephen Cole Kleene und Andrzej Mostowski) klassifiziert sicher Sets basierend auf Komplexität von Formeln, die sie definieren. Jeder Satz, der eine Klassifizierung erhält arithmetisch.

Die arithmetische Hierarchie ist wichtig in Rekursionstheorie, Effektive deskriptive Mengentheorieund das Studium formaler Theorien wie Peano -Arithmetik.

Das Tarski -Kuratowski -Algorithmus Bietet eine einfache Möglichkeit, eine Obergrenze für die Klassifikationen zu erhalten, die einer Formel zugeordnet sind, und das Set, das sie definiert.

Das Hyperarithmetische Hierarchie und die analytische Hierarchie Erweitern Sie die arithmetische Hierarchie, um zusätzliche Formeln und Sätze zu klassifizieren.

Die arithmetische Hierarchie der Formeln

Die arithmetische Hierarchie weist Klassifikationen zu den Formeln in der Sprache von Klassifizierung zu Arithmetik erster Ordnung. Die Klassifikationen werden bezeichnet ${\ displayStyle \ sigma _ {n}^{0}}$ und ${\ displaystyle \ pi _ {n}^{0}}$ für natürliche Zahlen n (einschließlich 0). Die griechischen Briefe hier sind Leichtface Symbole, die angeben, dass die Formeln keine festgelegten Parameter enthalten.

Wenn eine Formel ${\ displayStyle \ phi}$ ist dann logisch äquivalent zu einer Formel ohne Quantifizierer, dann ${\ displayStyle \ phi}$ wird die Klassifikationen zugewiesen ${\ displayStyle \ sigma _ {0}^{0}}$ und ${\ displaystyle \ pi _ {0}^{0}}$. Da jede Formel mit begrenzte Quantifizierer kann durch eine Formel ohne Quantifizierer ersetzt werden (zum Beispiel, zum Beispiel, ${\ displayStyle \ existiert x <2, \ phi (x)}$ ist äquivalent zu ${\ displayStyle \ phi (0) \ vee \ phi (1)}$), wir können auch zulassen ${\ displayStyle \ phi}$ Quantifizierer begrenzt haben.

Die Klassifizierungen ${\ displayStyle \ sigma _ {n}^{0}}$ und ${\ displaystyle \ pi _ {n}^{0}}$ werden für jede natürliche Zahl induktiv definiert n Verwenden der folgenden Regeln:

• Wenn ${\ displayStyle \ phi}$ ist logisch äquivalent zu einer Formel der Form ${\ displaystyle \ existiert m_ {1} \ existiert m_ {2} \ cdots \ existiert m_ {k} \ psi}$, wo ${\ displayStyle \ psi}$ ist ${\ displaystyle \ pi _ {n}^{0}}$, dann ${\ displayStyle \ phi}$ wird die Klassifizierung zugewiesen ${\ displayStyle \ sigma _ {n+1}^{0}}$.
• Wenn ${\ displayStyle \ phi}$ ist logisch äquivalent zu einer Formel der Form ${\ displaystyle \ forall m_ {1} \ forall m_ {2} \ cdots \ forall m_ {k} \ psi}$, wo ${\ displayStyle \ psi}$ ist ${\ displayStyle \ sigma _ {n}^{0}}$, dann ${\ displayStyle \ phi}$ wird die Klassifizierung zugewiesen ${\ displayStyle \ pi _ {n+1}^{0}}$.

A ${\ displayStyle \ sigma _ {n}^{0}}$ Die Formel entspricht einer Formel, die mit einigen beginnt existenzielle Quantifizierer und alterniert ${\ displayStyle n-1}$ Zeiten zwischen der Reihe existenzieller und Universelle Quantifizierer; während ein ${\ displaystyle \ pi _ {n}^{0}}$ Die Formel entspricht einer Formel, die mit einigen universellen Quantifizierern beginnt und analog wechselt.

Weil jede Formel erster Ordnung eine hat Prenex normale FormJede Formel wird mindestens eine Klassifizierung zugewiesen. Da redundante Quantifizierer jeder Formel hinzugefügt werden können ${\ displayStyle \ sigma _ {n}^{0}}$ oder ${\ displaystyle \ pi _ {n}^{0}}$ Es wird die Klassifikationen zugewiesen ${\ displaystyle \ sigma _ {r}^{0}}$ und ${\ displaystyle \ pi _ {r}^{0}}$ für jeden r > n. Die einzige relevante Klassifizierung, die einer Formel zugeordnet ist n; Alle anderen Klassifizierungen können daraus bestimmt werden.

Die arithmetische Hierarchie von natürlichen Zahlen

Ein Satz X von natürlichen Zahlen wird durch Formel φ in der Sprache von definiert Peano -Arithmetik (Die Sprache erster Ordnung mit Symbolen "0" für Null, "s" für die Nachfolgefunktion, "+" für Addition, "×" für die Multiplikation und "=" für Gleichheit), wenn die Elemente von X sind genau die Zahlen, die φ erfüllen. Das ist für alle natürlichen Zahlen nAnwesend

$oder$

wo ${\ displayStyle {\ unterline {n}}}$ ist die Ziffer in der Sprache der Arithmetik, die entspricht ${\ displayStyle n}$. Ein Satz ist in Arithmetik erster Ordnung definierbar, wenn es durch eine Formel in der Sprache der Erdmantel-Arithmetik definiert wird.

Jedes Set X von natürlichen Zahlen, die in Arithmetik erster Ordnung definierbar sind, werden Klassifizierungen der Form zugewiesen ${\ displayStyle \ sigma _ {n}^{0}}$, ${\ displaystyle \ pi _ {n}^{0}}$, und ${\ displayStyle \ Delta _ {n}^{0}}$, wo ${\ displayStyle n}$ ist eine natürliche Zahl wie folgt. Wenn X ist definierbar durch a ${\ displayStyle \ sigma _ {n}^{0}}$ Formel dann X wird die Klassifizierung zugewiesen ${\ displayStyle \ sigma _ {n}^{0}}$. Wenn X ist definierbar durch a ${\ displaystyle \ pi _ {n}^{0}}$ Formel dann X wird die Klassifizierung zugewiesen ${\ displaystyle \ pi _ {n}^{0}}$. Wenn X ist beides ${\ displayStyle \ sigma _ {n}^{0}}$ und ${\ displaystyle \ pi _ {n}^{0}}$ dann ${\ displayStyle x}$ wird die zusätzliche Klassifizierung zugewiesen ${\ displayStyle \ Delta _ {n}^{0}}$.

Beachten Sie, dass es selten Sinn macht, davon zu sprechen ${\ displayStyle \ Delta _ {n}^{0}}$ Formeln; Der erste Quantifizierer einer Formel ist entweder existentiell oder universell. Also a ${\ displayStyle \ Delta _ {n}^{0}}$ Set wird nicht durch a definiert ${\ displayStyle \ Delta _ {n}^{0}}$ Formel; Vielmehr gibt es beide ${\ displayStyle \ sigma _ {n}^{0}}$ und ${\ displaystyle \ pi _ {n}^{0}}$ Formeln, die den Satz definieren. Zum Beispiel die Menge der ungeraden natürlichen Zahlen ${\ displayStyle n}$ ist definierbar durch beide ${\ displayStyle \ forall k (n \ neq 2 \ times k)}$ oder ${\ displayStyle \ existiert k (n = 2 \ Times k+1)}$.

Eine parallele Definition wird verwendet, um die arithmetische Hierarchie auf endlich zu definieren Kartesische Kräfte der natürlichen Zahlen. Anstelle von Formeln mit einer freien Variablen, Formeln mit k Freie Zahlenvariablen werden verwendet, um die arithmetische Hierarchie an Sätzen von zu definieren k-Tupel natürlicher Zahlen. Diese sind in der Tat mit der Verwendung von a zusammenhängen Paarungsfunktion.

Relativierte arithmetische Hierarchien

So wie wir definieren können, was es für einen Satz bedeutet X sein rekursiv relativ zu einem anderen Satz Y durch die Definition der Berechnung X konsultieren Y Als Orakel können wir diesen Begriff auf die gesamte arithmetische Hierarchie ausdehnen und definieren, wofür sie bedeutet X sein ${\ displayStyle \ sigma _ {n}^{0}}$, ${\ displayStyle \ Delta _ {n}^{0}}$ oder ${\ displaystyle \ pi _ {n}^{0}}$ in Ybezeichnet jeweils ${\ displaystyle \ sigma _ {n}^{0, y}}$ ${\ displayStyle \ Delta _ {n}^{0, y}}$ und ${\ displaystyle \ pi _ {n}^{0, y}}$. Beheben Sie dazu eine Reihe von Ganzzahlen Y und fügen Sie ein Prädikat für die Mitgliedschaft in hinzu Y zur Sprache der Erdmännchen -Arithmetik. Wir sagen das dann X ist in ${\ displaystyle \ sigma _ {n}^{0, y}}$ Wenn es durch a definiert ist ${\ displayStyle \ sigma _ {n}^{0}}$ Formel in dieser erweiterten Sprache. Mit anderen Worten, X ist ${\ displaystyle \ sigma _ {n}^{0, y}}$ Wenn es durch a definiert ist ${\ displayStyle \ sigma _ {n}^{0}}$ Formel erlaubt Fragen zur Mitgliedschaft in Y. Alternativ kann man die anzeigen ${\ displaystyle \ sigma _ {n}^{0, y}}$ Sets als Sets, die mit rekursiven Sätzen in erstellt werden können Y und abwechselnd nehmen Gewerkschaften und Schnittpunkte von diesen setzt sich auf n mal.

Zum Beispiel lassen Y eine Reihe von Ganzzahlen sein. Lassen X Sei der Satz von Zahlen, die durch ein Element von Y teilbar sind. Dann X wird durch die Formel definiert ${\ displayStyle \ phi (n) = \ existiert m \ existt t (y (m) \ land m \ mal t = n)}$ Also X ist in ${\ displayStyle \ sigma _ {1}^{0, y}}$ (Eigentlich ist es in ${\ displayStyle \ Delta _ {0}^{0, y}}$ auch da wir beide Quantifizierer mit n) gebunden konnten).

Arithmetische Reduzierbarkeit und Grad

Die arithmetische Reduzierbarkeit ist ein Zwischenbegriff zwischen Reduzierbarkeit und Hyperarithmus -Reduzierbarkeit.

Ein Satz ist arithmetisch (Auch Arithmetik und arithmetisch definierbar) Wenn es durch eine Formel in der Sprache der Erdbaumarithmetik definiert ist. Äquivalent X ist arithmetisch, wenn X ist ${\ displayStyle \ sigma _ {n}^{0}}$ oder ${\ displaystyle \ pi _ {n}^{0}}$ für eine ganze Ganzzahl n. Ein Satz X ist arithmetisch in ein Satz Y, bezeichnet ${\ displaystyle x \ leq _ {a} y}$, wenn X ist definierbar als eine Formel in der Sprache von Peano -Arithmetik Y. Äquivalent, X ist arithmetisch in Y wenn X ist in ${\ displaystyle \ sigma _ {n}^{0, y}}$ oder ${\ displaystyle \ pi _ {n}^{0, y}}$ für eine ganze Ganzzahl n. Ein Synonym für ${\ displaystyle x \ leq _ {a} y}$ ist: X ist arithmetisch reduzierbar zu Y.

Die Beziehung ${\ displaystyle x \ leq _ {a} y}$ ist reflexiv und transitiv und damit die Beziehung ${\ displayStyle \ äquiv _ {a}}$ definiert durch die Regel

$oder$

ist eine Äquivalenzbeziehung. Die Äquivalenzklassen dieser Beziehung werden als die bezeichnet Arithmetische Grade; Sie werden teilweise unter bestellt unter ${\ displayStyle \ leq _ {a}}$.

Die arithmetische Hierarchie der Untergruppen von Kantor- und Baire -Raum

Das Kantorraum, bezeichnet ${\ displayStyle 2^{\ Omega}}$, ist der Satz aller unendlichen Sequenzen von 0s und 1s; das Baire -Raum, bezeichnet ${\ displayStyle \ Omega ^{\ Omega}}$ oder ${\ displaystyle {\ mathcal {n}}}$ist der Satz aller unendlichen Sequenzen natürlicher Zahlen. Beachten Sie, dass Elemente des Kantorraums mit Zahlensätzen und Elementen des Baire -Raums mit Funktionen von Ganzzahlen bis hin zu Ganzzahlen identifiziert werden können.

Die gewöhnliche Axiomatisierung von Arithmetik zweiter Ordnung Verwendet eine Set-basierte Sprache, in der die Set-Quantifizierer natürlich als Quantifizierung über den Kantorraum angesehen werden können. Eine Teilmenge des Kantorraums wird der Klassifizierung zugewiesen ${\ displayStyle \ sigma _ {n}^{0}}$ Wenn es durch a definierbar ist ${\ displayStyle \ sigma _ {n}^{0}}$ Formel. Dem Set wird die Klassifizierung zugewiesen ${\ displaystyle \ pi _ {n}^{0}}$ Wenn es durch a definierbar ist ${\ displaystyle \ pi _ {n}^{0}}$ Formel. Wenn das Set beides ist ${\ displayStyle \ sigma _ {n}^{0}}$ und ${\ displaystyle \ pi _ {n}^{0}}$ Dann erhält es die zusätzliche Klassifizierung ${\ displayStyle \ Delta _ {n}^{0}}$. Zum Beispiel lassen ${\ displayStyle o \ subset 2^{\ Omega}}$ Seien Sie der Satz aller unendlichen binären Zeichenfolgen, die nicht alle 0 sind (oder gleichzeitig der Satz aller nicht leeren Zahlenmengen). Wie ${\ displayStyle o = \ {x \ in 2^{\ Omega} | \ existiert n (x (n) = 1) \}}$ wir sehen das ${\ displayStyle o}$ wird durch a definiert ${\ displayStyle \ sigma _ {1}^{0}}$ Formel und daher ist a ${\ displayStyle \ sigma _ {1}^{0}}$ einstellen.

Beachten Sie, dass sowohl die Elemente des Kantorraums (als Sätze von Ganzzahlen) als auch Teilmengen des Kantorraums in arithmetischen Hierarchien klassifiziert werden, dies sind jedoch nicht die gleiche Hierarchie. Tatsächlich ist die Beziehung zwischen den beiden Hierarchien interessant und nicht trivial. Zum Beispiel die ${\ displaystyle \ pi _ {n}^{0}}$ Elemente des Kantorraums sind (im Allgemeinen) nicht gleich wie bei den Elementen ${\ displayStyle x}$ des Kantorraums so das ${\ displayStyle \ {x \}}$ ist ein ${\ displaystyle \ pi _ {n}^{0}}$ Teilmenge des Kantorraums. Viele interessante Ergebnisse beziehen jedoch die beiden Hierarchien.

Es gibt zwei Möglichkeiten, wie eine Untergruppe des Baire -Raums in der arithmetischen Hierarchie eingeteilt werden kann.

• Eine Teilmenge des Baire -Raums hat eine entsprechende Teilmenge des Kantorraums unter der Karte, die jede Funktion von ${\ displayStyle \ Omega}$ zu ${\ displayStyle \ Omega}$ zum charakteristische Funktion seiner Grafik. Eine Teilmenge des Baire -Raums wird in der Klassifizierung gegeben ${\ displayStyle \ sigma _ {n}^{1}}$, ${\ displaystyle \ pi _ {n}^{1}}$, oder ${\ displayStyle \ Delta _ {n}^{1}}$ Wenn und nur wenn die entsprechende Teilmenge des Kantorraums die gleiche Klassifizierung hat.
• Eine äquivalente Definition der analytischen Hierarchie im Baire-Raum wird durch Definieren der analytischen Hierarchie von Formeln unter Verwendung einer funktionellen Version der Arithmetik zweiter Ordnung angegeben. Dann kann die analytische Hierarchie auf Teilmengen des Kantorraums aus der Hierarchie auf dem Baire -Raum definiert werden. Diese alternative Definition liefert genau die gleichen Klassifikationen wie die erste Definition.

Eine parallele Definition wird verwendet, um die arithmetische Hierarchie auf endlichen kartesischen Kräften des Baire -Raums oder des Kantorraums unter Verwendung von Formeln mit mehreren freien Variablen zu definieren. Die arithmetische Hierarchie kann auf jedem definiert werden effektiver polnischer Raum; Die Definition ist besonders einfach für Cantor Space und Baire Space, da sie zur Sprache der gewöhnlichen Arithmetik zweiter Ordnung passen.

Beachten Sie, dass wir auch die arithmetische Hierarchie der Untergruppen der Kantor- und Baire -Räume im Vergleich zu einigen Zahlenfaden definieren können. In der Tat mutig ${\ displaystyle \ mathbf {\ sigma} _ {n}^{0}}$ ist nur die Vereinigung von ${\ displaystyle \ sigma _ {n}^{0, y}}$ Für alle Zahlengruppen Y. Beachten Sie, dass die kühne Face -Hierarchie nur die Standardhierarchie von ist Borel -Sets.

Erweiterungen und Variationen

Es ist möglich, die arithmetische Hierarchie von Formeln mit einer Sprache zu definieren, die für jeden mit einem Funktionsymbol erweitert wurde primitive rekursive Funktion. Diese Variation ändert die Klassifizierung von geringfügig von ${\ displaystyle \ sigma _ {0}^{0} = \ pi _ {0}^{0} = \ delta _ {0}^{0}}$, seit Verwendung primitiver rekursiv erfordert im Allgemeinen einen unbegrenzten existenziellen Quantifizierer und somit einige Sätze, die sich befinden ${\ displayStyle \ sigma _ {0}^{0}}$ durch diese Definition sind in ${\ displayStyle \ sigma _ {1}^{0}}$ nach der Definition am Anfang dieses Artikels. ${\ displayStyle \ sigma _ {1}^{0}}$ und so bleiben alle höheren Klassen in der Hierarchie unberührt.

Eine semantischere Variation der Hierarchie kann in allen fünzlichen Beziehungen zu den natürlichen Zahlen definiert werden. Die folgende Definition wird verwendet. Jede rechenbare Beziehung ist definiert zu sein ${\ displaystyle \ sigma _ {0}^{0} = \ pi _ {0}^{0} = \ delta _ {0}^{0}}$. Die Klassifizierungen ${\ displayStyle \ sigma _ {n}^{0}}$ und ${\ displaystyle \ pi _ {n}^{0}}$ werden induktiv mit den folgenden Regeln definiert.

• Wenn die Beziehung ${\ displayStyle r (n_ {1}, \ ldots, n_ {l}, m_ {1}, \ ldots, m_ {k}) \,}$ ist ${\ displayStyle \ sigma _ {n}^{0}}$ dann die Beziehung $oder 1}, \ ldots, m_ {k})}$ ist definiert, um zu sein ${\ displayStyle \ pi _ {n+1}^{0}}$
• Wenn die Beziehung ${\ displayStyle r (n_ {1}, \ ldots, n_ {l}, m_ {1}, \ ldots, m_ {k}) \,}$ ist ${\ displaystyle \ pi _ {n}^{0}}$ dann die Beziehung $oder 1}, \ ldots, m_ {k})}$ ist definiert, um zu sein ${\ displayStyle \ sigma _ {n+1}^{0}}$

Diese Variation ändert die Klassifizierung einiger Sätze geringfügig. Im Speziellen, ${\ displaystyle \ sigma _ {0}^{0} = \ pi _ {0}^{0} = \ delta _ {0}^{0}}$, als eine Klasse von Sätzen (definierbar durch die Beziehungen in der Klasse) ist identisch mit ${\ displayStyle \ Delta _ {1}^{0}}$ wie der letztere früher definiert war. Es kann erweitert werden, um die natürlichen Zahlen, den Baire -Raum und den Cantor -Raum zu decken.

Bedeutung der Notation

Die folgenden Bedeutungen können an die Notation für die arithmetische Hierarchie auf Formeln gebunden werden.

Das Index ${\ displayStyle n}$ in den Symbolen ${\ displayStyle \ sigma _ {n}^{0}}$ und ${\ displaystyle \ pi _ {n}^{0}}$ Zeigt die Anzahl der Wechsel von Blöcken von universellen und existenziellen Zahlenquantifizierern an, die in einer Formel verwendet werden. Darüber hinaus ist der äußerste Block existenziell in ${\ displayStyle \ sigma _ {n}^{0}}$ Formeln und universell in ${\ displaystyle \ pi _ {n}^{0}}$ Formeln.

Das Superscript ${\ displayStyle 0}$ in den Symbolen ${\ displayStyle \ sigma _ {n}^{0}}$, ${\ displaystyle \ pi _ {n}^{0}}$, und ${\ displayStyle \ Delta _ {n}^{0}}$ Gibt den Typ der Objekte an, die quantifiziert werden. Typ 0 -Objekte sind natürliche Zahlen und Typobjekte vom Typ 0 ${\ displayStyle i+1}$ sind Funktionen, die den Satz von Objekten vom Typ zuordnen ${\ displayStyle i}$ zu den natürlichen Zahlen. Die Quantifizierung über höhere Typobjekte wie Funktionen von natürlichen Zahlen zu natürlichen Zahlen wird durch ein Superscript größer als 0 beschrieben, wie in der analytische Hierarchie. Der Superscript 0 zeigt Quantifizierer über Zahlen an, das Superscript 1 würde die Quantifizierung über Funktionen von Zahlen zu Zahlen (Typ 1 -Objekte) angeben, das Superscript 2 würde der Quantifizierung über Funktionen entsprechen, die ein Objekt vom Typ 1 annehmen und eine Zahl zurückgeben, usw.

Beispiele

• Das ${\ displayStyle \ sigma _ {1}^{0}}$ Zahlensätze sind diejenigen, die durch eine Formel der Form definierbar sind $oder$ wo ${\ displayStyle \ psi}$ hat nur Quantifizierer begrenzt. Das sind genau das rekursiv aufzählbare Sätze.
• Die natürliche Anzahl natürlicher Zahlen, die Indizes für Turing -Maschinen sind, die Gesamtfunktionen berechnen ${\ displayStyle \ pi _ {2}^{0}}$. Intuitiv ein Index ${\ displayStyle e}$ fällt in diesen Satz, wenn und nur wenn für jeden ${\ displayStyle m}$ "Da ist ein ${\ displayStyle S}$ so dass die Turing -Maschine mit Index ${\ displayStyle e}$ Halt bei der Eingabe ${\ displayStyle m}$ nach ${\ displayStyle S}$ Schritte". Ein vollständiger Beweis würde zeigen, dass die Eigenschaft, die in Zitaten im vorherigen Satz angezeigt wird ${\ displayStyle \ sigma _ {1}^{0}}$ Formel.
• Jeder ${\ displayStyle \ sigma _ {1}^{0}}$ Die Teilmenge des Baire -Raums oder des Kantorraums ist ein offener Satz in der üblichen Topologie des Raums. Darüber hinaus gibt es für einen solchen Satz eine berechnungsbare Aufzählung der Gödel -Anzahl von offenen offenen Sätzen, deren Vereinigung der ursprüngliche Satz ist. Deshalb, ${\ displayStyle \ sigma _ {1}^{0}}$ Sets werden manchmal genannt effektiv offen. In ähnlicher Weise alle ${\ displayStyle \ pi _ {1}^{0}}$ Set ist geschlossen und die ${\ displayStyle \ pi _ {1}^{0}}$ Sets werden manchmal genannt effektiv geschlossen.
• Jede arithmetische Untergruppe von Kantorraum oder Baire -Raum ist a Borel -Set. Die Lightface -Borelhierarchie erweitert die arithmetische Hierarchie um zusätzliche Borel -Sets. Zum Beispiel jeder ${\ displayStyle \ pi _ {2}^{0}}$ Untergruppe von Kantor oder Baire -Raum ist a ${\ displayStyle g _ {\ delta}}$ SET (dh ein Satz, der der Schnittstelle zählbar viele offene Sätze entspricht). Darüber hinaus ist jedes dieser offenen Sets ${\ displayStyle \ sigma _ {1}^{0}}$ und die Liste der Gödel -Nummern dieser offenen Sets hat eine berechnete Aufzählung. Wenn ${\ displayStyle \ phi (x, n, m)}$ ist ein ${\ displayStyle \ sigma _ {0}^{0}}$ Formel mit einer kostenlosen Set -Variablen X und freie Zahlenvariablen ${\ displayStyle n, m}$ dann ist die ${\ displayStyle \ pi _ {2}^{0}}$ einstellen ${\ displaystyle \ {x \ mid \ forall n \ existiert m \ phi (x, n, m) \}}$ ist der Schnittpunkt der ${\ displayStyle \ sigma _ {1}^{0}}$ Sätze der Form ${\ displaystyle \ {x \ mid \ existiert m \ phi (x, n, m) \}}$ wie n Bereiche über die natürlichen Zahlen.
• Das ${\ displaystyle \ sigma _ {0}^{0} = \ pi _ {0}^{0} = \ delta _ {0}^{0}}$ Formeln können überprüft werden, indem alle Fälle einzeln durchgehen, was möglich ist, da alle ihre Quantifizierer begrenzt sind. Die Zeit dafür ist Polynom in ihren Argumenten (z. B. Polynom in n zum ${\ displayStyle \ varphi (n)}$); Somit sind ihre entsprechenden Entscheidungsprobleme in enthalten E (wie n ist exponentiell in seiner Anzahl von Bits). Dies gilt nicht mehr unter alternativen Definitionen von ${\ displaystyle \ sigma _ {0}^{0} = \ pi _ {0}^{0} = \ delta _ {0}^{0}}$, die die Verwendung primitiver rekursiver Funktionen ermöglichen, da die Quantifizierer jetzt durch jede primitive rekursive Funktion der Argumente gebunden sein können.
• Das ${\ displaystyle \ sigma _ {0}^{0} = \ pi _ {0}^{0} = \ delta _ {0}^{0}}$ Formeln unter einer alternativen Definition, die die Verwendung primitiver rekursiver Funktionen mit begrenzten Quantifizierern ermöglicht, entsprechen den Zahlen von Ganzzahlen der Form ${\ displayStyle \ {n: f (n) = 0 \}}$ für eine primitive rekursive Funktion f. Dies liegt daran f, ${\ displayStyle \ forall k <n: f (k) = 0}$ ist das gleiche wie ${\ displayStyle f (0)+f (1)+... f (n) = 0}$, und ${\ displayStyle \ existiert k <n: f (k) = 0}$ ist das gleiche wie ${\ displayStyle f (0)*f (1)*... f (n) = 0}$; mit Wertschöpfungsverlauf Rekursion Jedes von diesen kann durch eine einzelne primitive Rekursionsfunktion definiert werden.

Eigenschaften

Die folgenden Eigenschaften gilt für die arithmetische Hierarchie der natürlichen Zahlen und die arithmetische Hierarchie von Untergruppen von Kantor- oder Baire -Raum.

• Die Sammlungen ${\ displaystyle \ pi _ {n}^{0}}$ und ${\ displayStyle \ sigma _ {n}^{0}}$ sind unter endlich geschlossen Gewerkschaften und endlich Schnittpunkte ihrer jeweiligen Elemente.
• Ein Satz ist ${\ displayStyle \ sigma _ {n}^{0}}$ Wenn und nur wenn seine Ergänzung ist ${\ displaystyle \ pi _ {n}^{0}}$. Ein Satz ist ${\ displayStyle \ Delta _ {n}^{0}}$ Wenn und nur wenn das Set beides ist ${\ displayStyle \ sigma _ {n}^{0}}$ und ${\ displaystyle \ pi _ {n}^{0}}$In diesem Fall wird auch das Komplement sein ${\ displayStyle \ Delta _ {n}^{0}}$.
• Die Einschlüsse ${\ displaystyle \ pi _ {n}^{0} \ subsetneq \ pi _ {n+1}^{0}}$ und ${\ displayStyle \ sigma _ {n}^{0} \ subsetneq \ sigma _ {n+1}^{0}}$ für alle halten ${\ displayStyle n}$. Somit kollabiert die Hierarchie nicht. Dies ist eine direkte Folge von Posts Theorem.
• Die Einschlüsse ${\ displaystyle \ delta _ {n}^{0} \ subsetneq \ pi _ {n}^{0}}$, ${\ displaystyle \ delta _ {n}^{0} \ subetneq \ sigma _ {n}^{0}}$ und $oder$ halten für ${\ displayStyle N \ Geq 1}$.

• Zum Beispiel für eine universelle Maschine t ist der Satz von Paaren (n, m) so, dass t auf n, aber nicht auf m, in m ist in ${\ displayStyle \ Delta _ {2}^{0}}$ (berechnet mit einem Orakel für das Stoppproblem), aber nicht in ${\ displaystyle \ sigma _ {1}^{0} \ cup \ pi _ {1}^{0}}$.
• ${\ displaystyle \ sigma _ {0}^{0} = \ pi _ {0}^{0} = \ delta _ {0}^{0} = \ sigma _ {0} _ {0}^{0} \ subset \ delta _ {1}^{0}}$. Die Aufnahme ist streng durch die in diesem Artikel angegebene Definition, aber eine Identität mit ${\ displayStyle \ Delta _ {1}^{0}}$ hält unter einer der Variationen der Definition oben gegeben.

Beziehung zu Turing -Maschinen

Berechnungsbare Sätze

Wenn s a Turing Computable Setdann beide s und seine ergänzen sind rekursiv aufgezählt (wenn t eine Turing -Maschine ist, die 1 für Eingänge in S und 0 enthält, können wir eine Turing -Maschine bauen, die nur auf der ersteren stimmt, und ein weiteres nur auf letzterem).

Durch Posts Theoremsowohl s als auch seine Ergänzung sind in ${\ displayStyle \ sigma _ {1}^{0}}$. Dies bedeutet, dass S beides in ist ${\ displayStyle \ sigma _ {1}^{0}}$ und in ${\ displayStyle \ pi _ {1}^{0}}$und daher ist es in ${\ displayStyle \ Delta _ {1}^{0}}$.

Ebenso für jeden Satz s in ${\ displayStyle \ Delta _ {1}^{0}}$sowohl s als auch seine Ergänzung sind in ${\ displayStyle \ sigma _ {1}^{0}}$ und sind deshalb (von Posts Theorem) rekursiv aufzählbar durch einige Turing -Maschinen t₁ und T₂, beziehungsweise. Für jede Zahl n genau eines dieser Halten. Wir können daher eine Turing -Maschine t konstruieren, die sich zwischen t weilt₁ und T₂, stalten und zurückkehren 1, wenn der erstere anhält oder anhält und wieder zurückkommt, wenn der letztere anhält. Somit hält T bei jedem N an und kehrt zurück, ob es in S ist, so dass s berechnet werden kann.

Zusammenfassung der Hauptergebnisse

Die rechenbaren Turing -Sätze natürlicher Zahlen sind genau die Sätze auf Ebene ${\ displayStyle \ Delta _ {1}^{0}}$ der arithmetischen Hierarchie. Die rekursiv aufzählbaren Sets sind genau die Sätze auf dem Niveau ${\ displayStyle \ sigma _ {1}^{0}}$.

Nein Oracle Machine ist in der Lage, sich selbst zu lösen Problem stoppen (Eine Variation des Beweises von Turing gilt). Das Stillstörungsproblem für a ${\ displayStyle \ Delta _ {n}^{0, y}}$ Oracle sitzt tatsächlich in ${\ displayStyle \ sigma _ {n+1}^{0, y}}$.

Posts Theorem stellt eine enge Verbindung zwischen der arithmetischen Hierarchie der Sätze natürlicher Zahlen und der her Turing -Grad. Insbesondere legt es die folgenden Fakten für alle fest n ≥ 1:

• Der Satz ${\ displayStyle \ leereSet ^{(n)}}$ (das nth Turing Sprung des leeren Satzes) ist Viele komplett in ${\ displayStyle \ sigma _ {n}^{0}}$.
• Der Satz ${\ displayStyle \ mathbb {n} \ setminus \ leereSet ^{(n)}}$ ist viele eins vollständig in ${\ displaystyle \ pi _ {n}^{0}}$.
• Der Satz ${\ displayStyle \ leereSet ^{(n-1)}}$ ist Turing vollständig in ${\ displayStyle \ Delta _ {n}^{0}}$.

Das Polynomhierarchie ist eine "praktikable, ressourcengebundene" Version der arithmetischen Hierarchie, in der Polynomlängengrenzen auf die beteiligten Zahlen platziert werden (oder gleichzeitig polynomiale Zeitgrenzen auf die beteiligten Turing-Maschinen platziert werden). Es gibt eine feinere Klassifizierung einiger Sätze natürlicher Zahlen, die auf Ebene sind ${\ displayStyle \ Delta _ {1}^{0}}$ der arithmetischen Hierarchie.

Beziehung zu anderen Hierarchien

Siehe auch

• Lévy hierarchy
• Hierarchie (Mathematik)
• Interpretierungslogik
• Polynomhierarchie

Verweise