Alternative Finestructural and Computational Approaches to Constructibility

Abstract

We consider attempts to simplify finestructural arguments concerning inner models of ZFC, in particular L; in addition, we exhibit different aspects of the computational strength of Infinite Time Register Machines.

Die Arbeit befasst sich mit alternativen Methoden zur Analyse von Gödels konstruktiblem Universum <em>L</em>, dem ⊆-minimalen klassenmächtigen Modell von ZFC und anderer konstruktibler Strukturen.<br /> Im ersten Teil werden <em>F</em>-Strukturen eingeführt, ein Ansatz von Koepke zur Vereinfachung der Feinstrukturtheorie von Kernmodellen. Wir gewinnen einige Vorteile für die weitere Entwicklung aus der Einführung einer Namensfunktion <em>N</em> unter die Basisfunktionen und kleinerer Modifikationen des Hüllenoperators. Es wird demonstriert, dass die <em>F</em>-Hierarchie ein geeignetes Instrument zum Beweis wichtiger Eigenschaften von <em>L</em> ist, wie etwa der Hausdorffschen verallgemeinerten Kontinuumshypothese GCH oder des kombinatorische Prinzips ◊. Dann wird eine Methode zur Erweiterung strukturerhaltender Funktionen, sogenannter feiner Abbildungen, angegeben, Koepkes vereinfachter Beweis des Überdeckungssatzes für <em>L</em> erläutert und ein Approximationssatz für <em>L</em> gezeigt: Unter ¬0^# ist jedes <em>X</em> ⊂ <em>On</em> von überabzählbarer Konfinalität, das unter den Basisfunktionen der <em>F</em>-Hierarchie abgeschlossen ist, Vereinigung von abzählbar vielen Elementen von <em>L</em>.<br /> Gegenüber dem Beweis des Approximationssatzes von Magidor, der die Abgeschlossenheit unter primitiv-rekursiven Mengenfunktionen voraussetzt, gewinnen wir deutlich an Kürze und Einfachheit.<br /> Weiter ergänzen wir die Basisfunktionen der <em>F</em>-Hierarchie durch Ansätze aus der Hyperfeinstrukturtheorie von Friedman und Koepke. Im Kontext der <em>F</em>-Hierarchie ergibt sich daraus das allgemeinere Konzept des Hyperings, das wir ausführen und benutzen, um die hyperfeinstrukturellen Beweise des Quadrat- und Morastprinzips in die <em>F</em>-Hierarchie zu übertragen. Das hierbei vornehmlich benutzte horizontale Hypering H₂ sorgt dabei für eine Unabhängigkeit der konstruierten Objekte von der gewählten Aufzählung der Formeln. <br /> Anschließend betrachten wir Infinite Time Register Machines (<em>ITRMs</em>) sowohl als Anwendung von wie auch als weiteren Zugang zu konstruktiblen Methoden. <em>ITRMs</em> sind Registermaschinen, deren Laufzeiten beliebige Ordinalzahlen sein können. Wir beweisen das Lost-Melody-Theorem für <em>ITRMs</em>, d.h. die Existenz einer reellen Zahl, die durch eine <em>ITRM</em> als Orakelzahl erkannt, aber nicht berechnet werden kann. Wir führen getypte Maschinen ein, die Register mit verschiedenem Limesverhalten parallel verwenden und klassifizieren die Maschinentypen hinsichtlich ihrer Berechnungsstärke. Insbesondere zeigen wir, dass <em>ITRMs</em> mit n+1 überlaufenden Registern und einigen schwächeren Hilfsregistern den n-ten Hypersprung berechnen und das Halteproblem für <em>ITRMs</em> mit n überlaufenden Registern lösen können. Wir beweisen, dass die Menge der <em>ITRM</em>-erkennbaren reellen Zahlen in der Ordnung von <em>L</em> Lücken aufweist, und zwar mindestens von der Größe sup{<em>ω_i^CK|i ∈ ω</em>}, wobei <em>ω_i^CK</em> die <em>i</em>-te zulässige Ordinalzahl bezeichnet. Außerdem zeigen wir, dass die beweistheoretischen Analysen von Welch bezüglich der Existenz der Haltezahlen für verschiedene Maschinen im Kontext der getypten Maschinen zu präziseren Schranken führen.<br /> Im letzten Teil skizzieren wir Ansätze zu einer Übertragung alternativer Feinstrukturen auf allgemeinere konstruktible Strukturen, sogenannte Kernmodelle. Wir übertragen zentrale Konzepte, zeigen einige Erhaltungseigenschaften für die Ultrapotenzkonstruktion und ein Dodd-Jensen-Lemma für das entsprechende Iterationskonzept. Die Bewahrung der feinstrukturellen Information in Iterationen hingegen scheitert. Daran anschließend erläutern wir kurz die Gründe dieser Schwierigkeiten und diskutieren mögliche Auswege.