The computable models of uncountably categorical theoriesan inquiry in recursive model theory
Alexander Linsbichler · 2011
Die Arbeit stellt eine detaillierte Einfuhrung in die Rekursive Modelltheorie fur Leser mit mathematischer und mengentheoretischer Grundausbildung dar, hinfuhrend auf die Behandlung der rekursiv darstellbaren Modelle von $\aleph_{1}$-kategorischen Theorien. Auch Hinweise auf die historische Entwicklung und wissenschaftstheoretische Bedeutung verwendeter Konzepte werden angedeutet. Es wird durchwegs versucht, dem Leser durch umfangreiche Literaturhinweise eine Vertiefung in einzelne weiterfuhrende Aspekte zu erleichtern. Kapitel 1 beinhaltet eine Einfuhrung in die klasssische Modelltheorie mit Schwerpunkt auf die im weiteren Verlauf der Arbeit benotigten Definitionen und Resultate. Das Spektrum einer Theorie T wird definiert als die Funtion $\kappa\mapsto{I(T,\kappa)}$, wobei $\kappa$ eine beliebige Kardinalzahl ist und $I(T,\kappa)$ die Anzahl von Isomorphietypen von Modellen von T mit Kardinalitat $\kappa$. Das sogenannte Spektrenproblem, die Frage nach den moglichen Spektren vollstandiger Theorien, wird prasentiert und behandelt. Den Abschluss von Kapitel 1 bilden ein Abschnitt uber $\aleph_{1}$-kategorische Theorien, also Theorien T mit $I(T,\kappa)=1$ fur alle $\kappa>\aleph_{0}$, und damit verbunden eine Einfuhrung in die geometrische Stabilitatstheorie. Vollstandige, $\aleph_{1}$-kategorische Theorien sind entweder $\aleph_{0}$-kategorisch oder haben abzahlbar unendlich viele abzahlbare Isomorphietypen von Modellen, die sich in einer Kette von elementaren Einbettungen mit Lange $\omega+1$ anordnen lassen: $\mathfrak{M}_{0}\prec{\mathfrak{M}_{1}}\prec{...}\prec{\mathfrak{M}_{\omega}}$. Kapitel 2 ist eine konzise Einfuhrung in die Rekursionstheorie mit Hauptaugenmerk auf die im weiteren Verlauf der Arbeit benotigten Definitionen und Resultate.\\ In Kapitel 3 werden zunachst die drei zentralen Begriffe der Rekursiven Modelltheorie eingefuhrt: Eine Theorie ist entscheidbar, wenn die Menge der Godelnummern ihrer Satze rekursiv ist. Eine Struktur $\mathfrak{M}$ ist entscheidbar, wenn sie isomorph zu einer Struktur $\mathfrak{N}$ ist, deren Universum N rekursiv ist und deren elementares Diagramm entscheidbar ist. Eine Struktur $\mathfrak{M}$ ist rekursiv darstellbar, wenn sie isomorph zu einer Struktur $\mathfrak{N}$ ist, deren Universum N rekursiv ist und deren atomares Diagramm eine rekursive Menge von Godelnummern von Satzen ist. Im Anschluss werden rekursive Gegenstucke zu klassischen Theoremen der Modelltheorie auf ihre Gultigkeit untersucht und Aussagen uber die Existenz und Anzahl von entscheidbaren Modellen von Theorien wiedergegeben. Mit im Kontext relevanten Resultaten uber Axiomatisierbarkeit von Theorien wird an die Einfuhrung in geometrische Stabilitatstheorie an- und Kapitel 3 abgeschlossen. Kapitel 4, das Herzstuck der Arbeit, beschaftigt sich mit den rekursiv darstellbaren Modellen von vollstandigen, $\aleph_{1}$-kategorischen, nicht $\aleph_{0}$-kategorischen Theorien. Das rekursive Spektrum (RSP) einer solchen Theorie ist definiert als die Menge \[\left\{n\in{(\omega+1)} | \mathfrak{M}_{n} in der Kette elementarer Einbettungen ist rekursiv darstellbar \right\}.\] Es gibt bisher nur einige wenige Beweise, dass bestimmte Mengen tatsachlich als rekursive Spektren auftreten. Diese werden rekonstruiert. Insbesondere werden jene drei Resultate mit ahnlichen Beweise, die sich allesamt der Konstruktion verwandter hoherdimensionaler, wurfelartiger Strukturen und limitenweise monotoner Funktionen bedienen, ausfuhrlich, anschaulich und erstmals gesammelt in einheitlicher Notation und Darstellung prasentiert. Schlieslich wird auf einen in der Literatur verbreiteten Fehler - die Behauptung, die Menge $\left\{1,...,i\right\}$ sei fur $1<i<\omega$ als rekursives Spektrum bestatigt - hingewiesen. Zwei neue Vorschlage des Autors fur eine systematischere Analyse der rekursiv darstellbaren Modelle von Ehrenfeucht Theorien skizzieren ein offenes Forschungsgebiet. Kapitel 5 enthalt eine Einfuhrung in die fur die Zwecke der Arbeit relevanten Gebiete der Komplexitatstheorie, Turinggrade von Modellen und Theorien werden vorgestellt und ein Abschnitt gibt Auskunft uber die mogliche Komplexitat von kategorischen Theorien. Zu guter Letzt wird bewiesen, dass jedes rekursive Spektrum einer Theorie erster Stufe mit rekusiver Signatur eine $\Sigma_{3}(\textbf{0}^{(\omega)})$-Menge ist. Fur bestimmte Gruppen von Theorien lassen sich bessere obere Schranken fur die Komplexitat der rekursiven Spektren angeben. Es bleibt jedoch bis auf Weiteres eine enorme Wissenslucke zwischen den wenigen bestatigten rekursiven Spektren und den bekannten oberen Schranken.