Unter den Turing-Graden befinden sich Grade der Form , z. B. , , usw.
Ich werde dies der Vollständigkeit halber nur schnell beweisen. Hoffentlich hat niemand Bedenken mit diesem kurzen Beweis:
Lemma: Jeder zählbare Satz von Sätzen natürlicher Zahlen kann als ein einzelner Satz natürlicher Zahlen codiert werden, so dass jeder ursprüngliche Satz von einer Turing-Maschine decodiert werden kann.
Beweis: Sei unsere Menge von Mengen, so dass jedes eine Menge von natürlichen Zahlen ist. Definiere .
Somit ist . Es ist klar, dass es für jedes eine Turing-Maschine gibt, die mit einem Orakel für O berechnet .
Nebensatz: Jeder zählbare Satz von Turing-Graden hat eine Obergrenze.
Beweis: Sei unser zählbarer Gradsatz. Somit ist jedes eine zählbare Menge von Mengen natürlicher Zahlen. Sei eine Menge natürlicher Zahlen, die die Elemente von D_n codieren , und sei eine Menge natürlicher Zahlen, die alle E_n codieren .
Jede Menge in einem beliebigen Grad kann berechnet werden, indem zweimal hintereinander decodiert wird , so dass Turing-Grade . Daher ist eine obere Grenze von .
Sei die Obergrenze von wie oben beschrieben. Natürlich können wir den Turing-Sprung von , um den wir schreiben , und so weiter, um den zählbaren Satz von Turing-Graden . Nehmen wir die Obergrenze davon, so erhalten wir und natürlich auch die Obergrenze von Wir erhalten den Turing-Grad . Im Allgemeinen können wir für jede zählbare Ordnungszahl einen Grad .
Es ist bekannt, dass es für jeden Turing-Grad ungleich Null einen Turing-Grad mit dem er nicht zu vergleichen ist. Gibt es jedoch für jeden Turing-Abschluss (und ich bin besonders an interessiert ) einen Turing-Abschluss , der mit für alle zählbaren Ordnungszahlen ?
quelle
Antworten:
Die Antwort auf Ihre Frage ist klar : ES HÄNGT AB ! Dies führt uns zu einer Mengenlehre, die - obwohl interessant - für CS vielleicht etwas abseits liegt. Um dies zu beheben, habe ich den ersten Teil meiner Antwort ausschließlich auf die Berechenbarkeitstheorie bezogen und dann einen separaten Abschnitt auf der Seite der Mengenlehre hinzugefügt.
Bevor wir Ihre Frage überhaupt beantworten können, stellt sich heraus, dass es hier eine überraschende Subtilität gibt:
Dies wird bei mathoverflow und math.stackexchange unterschiedlich behandelt. Was ich unten geschrieben habe, sollte jedoch in sich geschlossen sein.
Das Problem sind Präsentationen (oder im Wesentlichen identische grundlegende Sequenzen ). Angenommen, ist eine Grenzwert-Ordnungszahl, wir haben für jedes definiert und wir möchten als die MengeDiese Menge ist jedoch keine Menge natürlicher Zahlen. Wenn wir eine Karte , können wir entlang auf natürliche Weise "interpretieren" :Hier ist das Problem: Wasλ 0( α ) α < λ 0( λ )
Abgesehen davon gibt es hier einen alternativen Ansatz, der auf den ersten Blick vielversprechend erscheint: Definieren Sie einfach für als Grenzwert für die kleinste Obergrenze von ! In Kombination mit der Klausel scheint dies eine rekursive Definition zu ergeben, die für alle zählbaren Ordnungszahlen funktioniert. Es stellt sich jedoch heraus, dass dieser gesamte Angriff auf einer falschen Annahme beruht: ist nicht die kleinste Obergrenze von im Turing Grad, und tatsächlich existieren nichttriviale kleinste Obergrenzen nie (dies ist der "exakte Paarsatz" von Spector). Wir müssen also unbedingt etwas arbeiten.0( λ ) λ {0(α):α<λ} 0(β+1)=(0(β))′ 0(ω) {0(n):n<ω}
An diesem Punkt ist es eine gute Idee, zurück zu gehen und zu versuchen, eine Theorie iterierter Sprünge "von Grund auf" zu entwickeln. Dies ist aufgrund von Kleene eine hyperarithmetische Theorie , die am Anfang von Sacks 'Buch ausführlich vorgestellt wird. Ich werde nur einen schnellen (und ahistorischen) Glanz geben.
Die oben definierten Mengen sind intuitiv das, was wir erhalten, wenn wir den Sprung nicht entlang einer bloßen Ordnungszahl, sondern entlang einer expliziten Ordnung einer Menge natürlicher Zahlen (dh einer Kopie der Ordnungszahl, die angemessen "beschriftet" ist, wiederholen ). Um dies genau zu machen, nehmen wir an, dass eine gute Ordnung einer Menge natürlicher Zahlen ist (beachten Sie, dass bestimmt ). Es ist leicht zu zeigen, dass es eine eindeutige Menge geordneter Paare natürlicher Zahlen mit den folgenden Eigenschaften gibt:Zfλ R D R D JR
Wenn der Nachfolger von , wird iff , wobei .u R v (u,y)∈JR ΦJR[v]y JR[v]={z:(v,z)∈JR}
Wenn ein Limit ist, dann istu R JR[u]={(v,y):v<Ru,y∈JR[v]}.
Dies erhalten Sie intuitiv, wenn Sie den Sprung entlang beginnend mit dem Emptyset wiederholen (die Tatsache, dass wir mit dem Emptyset begonnen haben, wurde heimlich bis zum letzten Aufzählungspunkt eingebaut, da , wenn das mindestens-Element ist muss leer sein; wir können relativieren, indem wir mit einer nicht leeren Spalte beginnen .R u R JR[u]
Wenn "nett" ist, ist das extrem brav:R
Die obigen Bedingungen sind stärker als nur zu verlangen, dass die Ordnungen berechenbar sind, aber tatsächlich ist jede berechenbare Ordnung (nicht berechenbar!) Ordnungsisomorph zu einer solchen "schönen" berechenbaren Ordnung. Auf dieser Grundlage ist es sinnvoll, für als "berechenbare Ordnungszahl" als den eindeutigen Turing-Grad einer "Sprungsequenz" entlang einer "schönen Darstellung" von . Allgemeiner ist es für jeden Turing-Grad sinnvoll, über den Grad für jede Ordnungszahl mit einer berechenbaren Darstellung zu sprechen.0(α) α α d d(α) α d
Die aus für einige berechenbare berechenbaren Mengen sind die hyperarithmetischen Mengen ; Hyperarithmetik hat eine Reihe von äquivalenten Charakterisierungen und ist einer der Grundbegriffe der modernen Berechenbarkeitstheorie und auch in der deskriptiven Mengenlehre von großer Bedeutung. Aber das bringt uns nur durch unzählige Ordnungszahlen; Die meisten zählbaren Ordnungszahlen haben keine berechenbaren Präsentationen! Das Supremum der berechenbaren Ordnungszahlen wird mit " " bezeichnet - es ist viel größer als andere populäre Ordnungszahlen wie , usw., aber immer noch zählbar und unter zählbaren Ordnungszahlen aus verschiedenen logischen Perspektiven immer noch recht klein0(α) α ωCK1 ϵ0 Γ0 . Und es ist nicht sehr schwer, zwei Turing-Grade zu kochen, von denen keiner im Vergleich zum anderen hyperarithmetisch ist, da wir nur "zählbar hoch" erreicht haben. Können wir es besser machen?
Um weiter zu gehen, müssen wir uns mit der Mengenlehre befassen, also werde ich hier eine horizontale Linie setzen:
Okay, lass uns über die Mengenlehre sprechen. Es stellt sich heraus , dass wir können den Sprung auf natürliche Weise Vergangenheit fortsetzen . Dies wird jedoch ziemlich schnell kompliziert. Die Idee stammt aus Godels konstruierbarem Universum . Die Idee ist, dass jeder zusätzliche Schritt in der Hierarchie so ist, als würde man viele Sprünge von dem machen, was man bisher hat (da man alles betrachtet, was in dem, was man hat, erster Ordnung definierbar ist bisher). Wenn wir das herausziehen, bekommen wir genau die Vorstellung von Mastercodes . Ich werde sie hier nicht genau definieren, aber Hodes hat ein ausgezeichnetes Papier zu diesem Thema .ωCK1 L ω
Nun, Mastercodes haben viele subtile und nervige Eigenschaften, aber sie lassen uns den Sprung vom bis zu , der ersten Ordnungszahl, die das konstruierbare Universum für unzählig hält, (ish) . (Im Allgemeinen können wir bei einem Grad Mastercodes bis zu "machen" , dem ersten Ordnungswert, den das kleinste innere Modell von ZFC, das für unzählig hält.)∗ ωL1 d ωL[d]1 d
Wenn das konstruierbare Universum alles ist, was es gibt - das heißt, wenn V = L -, dann sind wir pfirsichfarben:
Allgemeiner , "über Mastercodes erreichbar" gibt uns nur den Begriff der relativen Konstruierbarkeit : iff iff ist in jedem inneren Modell enthalten, das wenn aus einigen berechenbar ist. für .x≤Ly x∈L[y] x y x y(α) α<ωL[y]1
Es ist jedoch durchaus möglich - das heißt im Verhältnis zu ZFC konsistent -, dass sehr weit von . Zum Beispiel könnte zählbar sein, und tatsächlich könnte das "echte" aus der Sicht von ziemlich groß erscheinen ! In der Tat stellt sich heraus, dass starke satztheoretische Hypothesen uns daran hindern können, mit dieser Idee überhaupt sehr weit zu kommen:V L ωL1 ω1 L
Selbst unter der Annahme und etwas ausschließt (wie große Kardinäle) , die Konsistenz Stärke wird bump up, die -degrees noch ganz wild sein könnte, über zwingen . Insbesondere wenn gegenseitig Cohen-generisch (sagen wir) über , dann ist und ; Wir können Cohen-Generika erhalten, ohne zu ändern. In diesem Fall ist keines über zählbar viele Sprünge vom anderen aus erreichbar, vorausgesetzt, wir kaufen das "Mastercode-Bild" (und wenn nicht, müssen wir ein anderes Bild erstellen!). .ωL1=ω1 ≤L c0,c1 L c0∉L[c1] c1∉L[c0] ω1
quelle