Kategorizität

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Kategorizität ist ein Begriff aus der Modelltheorie, einem Teilgebiet der mathematischen Logik. Eine Theorie heißt kategorisch in einer bestimmten unendlichen Mächtigkeit, wenn sie im Wesentlichen nur ein Modell dieser Mächtigkeit hat. Die Bezeichnung „kategorisch“ stammt von Oswald Veblen, der sie von Kant entlehnte.[1]

Definitionen[Bearbeiten]

Zur Präzisierung verstehen wir unter einer Theorie eine Menge T von Sätzen, das heißt Aussagen ohne freie Variable, einer Sprache L_I^S der Prädikatenlogik erster Stufe, die unter der Folgerungsrelation \vDash abgeschlossen ist; das heißt für jeden Satz \varphi folgt aus T\vDash \varphi bereits \varphi \in T. Ist \Phi \subset L_I^S, so ist die Menge \Phi^\vDash := \{\varphi\in L_I^S;\, \varphi \mbox{ Satz}, \Phi\vDash \varphi\} aller aus \Phi herleitbaren Sätze ein Beispiel für eine Theorie.

Hat man eine Theorie T mit unendlichen Modellen, so gibt es nach dem Satz von Löwenheim-Skolem auch Modelle beliebiger unendlicher Mächtigkeit, insbesondere sind nicht je zwei Modelle notwendigerweise isomorph. Es könnte aber der Fall eintreten, dass die Theorie zu einer vorgegebenen unendlichen Kardinalzahl \kappa bis auf Isomorphie genau ein Modell der Mächtigkeit \kappa hat. Dann nennt man die Theorie \kappa-kategorisch.

Satz von Morley[Bearbeiten]

Ein wichtiges Resultat ist folgender auf Michael Morley zurückgehender Satz:

  • Ist T eine abzählbare Theorie, die \kappa-kategorisch ist für ein überabzählbares \kappa, so ist sie \kappa-kategorisch für jedes überabzählbare \kappa[2].

Es gibt für eine abzählbare Theorie daher nur vier Möglichkeiten in Bezug auf die Kategorizität. Diese kommen tatsächlich alle vor, wie durch unten angegebene Beispiele belegt wird.

Satz von Ryll-Nardzewski[Bearbeiten]

Der Satz von Ryll-Nardzewski charakterisiert \aleph_0-kategorische Theorien. Er sagt, dass abzählbare Theorien genau dann \aleph_0-kategorisch sind, wenn die Menge der Typen über jeder endlichen Mengen endlich ist.

Kriterium von Vaught[Bearbeiten]

Eine wichtige Anwendung des hier vorgestellten Begriffs ist das Kriterium von Vaught (auch: Łoś–Vaught-Test), das eine hinreichende, aber nicht notwendige Bedingung zur Vollständigkeit einer Theorie darstellt.

  • Ist T\varsubsetneq L_I^S eine abzählbare Theorie ohne endliche Modelle, die \kappa-kategorisch ist für eine Kardinahlzahl \kappa, so ist diese Theorie vollständig.
  • In einer allgemeineren Form lautet es: Ist T\varsubsetneq L_I^S eine Theorie ohne endliche Modelle, die \kappa-kategorisch ist für eine Kardinahlzahl, die mindestens so groß ist wie die Mächtigkeit der Signatur, so ist diese Theorie vollständig.

Beide Aussagen sind Korollare zum Satz von Löwenheim-Skolem.

Als wichtiges Anwendungsbeispiel erhalten wir die Vollständigkeit der Theorie der algebraisch abgeschlossenen Körper der Charakteristik 0 oder p.

Beispiele[Bearbeiten]

0-kategorisch und ℵ1-kategorisch: Tautologien[Bearbeiten]

Ein sehr einfaches Beispiel ist die Menge aller Tautologien der Sprache L_I = L_I^{\emptyset}, das heißt die Menge \emptyset^\vDash aller Sätze, die keiner weiteren Voraussetzungen bedürfen. Die Modelle zur Mächtigkeit \kappa sind nichts weiter als die Mengen der Mächtigkeit \kappa und die Isomorphismen sind genau die bijektiven Abbildungen. Daher sind je zwei Modelle derselben Mächtigkeit isomorph, das heißt die Theorie der Tautologien ist \kappa-kategorisch.

0-kategorisch und nicht ℵ1-kategorisch: Dichte Ordnungen[Bearbeiten]

Die Theorie der dichten linearen Ordnung ohne Extrema besteht aus allen Aussagen der Sprache L_I^{\{<\}}, die in \Q gelten. Man kann zeigen, dass zwei abzählbare Modelle isomorph sind. Allerdings ist \R nicht isomorph zu \R\times\Q (mit der lexikografischen Ordnung), da bei letzterem Modell zwischen zwei Punkten nicht immer überabzählbar viele Punkte liegen. Die Theorie ist daher \aleph_0-kategorisch, aber nicht kategorisch in überabzählbaren Kardinalzahlen.

Nicht ℵ0-kategorisch und ℵ1-kategorisch[Bearbeiten]

Algebraisch abgeschlossene Körper[Bearbeiten]

Die Theorie der algebraisch abgeschlossenen Körper kann in der Sprache L_I^{\{0,1,+,\cdot\}} durch eine Menge \Phi von Axiomen beschrieben werden, die neben den üblichen Körperaxiomen noch die unendliche Reihe von Axiomen

\forall y_0\, y_1 \ldots y_{n-1}\,\exists x\, (x^n + y_{n-1}\cdot x^{n-1} + \ldots + y_1\cdot x + y_0 \equiv 0)

für jedes n>0 hinzunimmt, was inhaltlich offenbar bedeutet, dass jedes Polynom eine Nullstelle hat. Dabei ist x^k eine abkürzende Schreibweise für das k-fache Produkt x\cdot \ldots \cdot x; man beachte, dass das Potenzieren nicht zur hier gewählten Sprache gehört. Dann ist \Phi^\vDash die Theorie der algebraisch abgeschlossenen Körper. Ferner sei \varphi_p der Satz 1+\ldots+1\equiv 0 (p-fache Summe von 1, p Primzahl). Dann axiomatisiert \Phi_p := \Phi \cup \{\varphi_p\} die Theorie der algebraisch abgeschlossenen Körper der Charakteristik p und \Phi_0 := \Phi \cup \{\neg \varphi_p;\,p\mbox{ Primzahl}\} die Theorie der algebraisch abgeschlossenen Körper der Charakteristik 0.

Ein Modell dieser Theorien wird durch die Mächtigkeit einer Transzendenzbasis bis auf Isomorphie bestimmt. Für ein Modell der Mächtigkeit \kappa (mit \kappa > \aleph_0) muss die Mächtigkeit einer Transzendenzbasis schon \kappa sein, für ein abzählbares Modell kann die Mächtigkeit der Transzendenzbasis eine beliebige endliche Zahl oder abzählbar unendlich sein. Die Theorien \Phi_0^\vDash und \Phi_p^\vDash sind daher \aleph_1-kategorisch, aber nicht \aleph_0-kategorisch. [3].

Q-Vektorräume[Bearbeiten]

\Q-Vektorräume lassen sich in der Prädikatenlogik erster Stufe durch die Signatur S=\{\mathbf{0},+,\Q\} beschreiben, wobei 0 ein Konstantensymbol (Nullvektor), + ein zweistelliges Funktionssymbol (Vektoraddition) und jedes r\in \Q ein einstelliges Funktionssymbol (skalare Multiplikation mit r) sei. Es ist klar, dass man mit diesen Symbolen die Axiome für \Q-Vektorräume hinschreiben kann. Man beachte allerdings, dass man nicht über alle Skalarmultiplikationen r\in \Q quantifizieren kann; man muss stattdessen mit unendlichen Folgen von Axiomen arbeiten, zum Beispiel

\forall x\, y\, (r+x\,y \equiv +\, rx\, ry)

für jedes Funktionssymbol r, was man suggestiver natürlich als

\forall x\, y\,( r(x+y) =  rx+ry)

schreibt. Man erhält so die Theorie T_{\Q V} = \Phi^\vDash, wobei \Phi die Menge aller obigen Axiome der \Q-Vektorräume ist[4].

Für natürliche Zahlen 0<n<m sind \Q^n und \Q^m zwei nicht isomorphe Modelle für T_{\Q V} derselben Mächtigkeit \aleph_0, die Theorie ist daher nicht \aleph_0-kategorisch. T_{\Q V} ist aber \kappa-kategorisch für jede Kardinalzahl \kappa > \aleph_0, denn man kann zeigen, dass Basen von \Q-Vektorräumen der Mächtigkeit \kappa > \aleph_0 ebenfalls diese Mächtigkeit haben und die Isomorphieklassen von Vektorräumen durch die Mächtigkeit der Basis eindeutig bestimmt sind.

Nicht ℵ0-kategorisch und nicht ℵ1-kategorisch: Diskrete Ordnungen[Bearbeiten]

Eine Theorie, die keine endlichen Modelle hat und nicht vollständig ist, ist nach dem Kriterium von Vaught (s. u.) in keiner Kardinalzahl kategorisch. Eine vollständige Theorie, die in keiner Kardinalzahl kategorisch ist, ist die Theorie der diskreten Ordnung ohne Extrema. Sie besteht aus allen Aussagen der Sprache L_I^{\{<\}}, die in \Z gelten.

\Z\times\Z und \Z sind zwei nicht-isomorphe abzählbare Modelle. \R\times\Z und 2^\omega\times\Z sind zwei nicht-isomorphe Modelle der Mächtigkeit 2^{\aleph_0}. (Jeweils mit der lexikographischen Ordnung, 2^\omega ist eine wohlgeordnete Ordinalzahl.)

Eine nicht vollständige, aber kategorische Theorie ohne endliche Modelle[Bearbeiten]

Dieses Beispiel zeigt, dass im Kriterium von Vaught nicht auf die Abzählbarkeitsvoraussetzung verzichtet werden kann. Sei I eine überabzählbare Index Menge, a,b \notin I. Für jede natürliche Zahl n sei \varphi_{\ge n} der Satz

\varphi_{\ge n}:= \exists x_1, \dots , x_n \bigwedge_{1\le k<l \le n}\neg x_k \doteq x_l,

der aussagt, dass es mindestens n unterschiedliche Elemente gibt.

Die von der überabzählbaren Menge

\{( c_a \doteq c_b \rightarrow (c_a \doteq c_j \wedge c_i \doteq c_j)) \wedge
( \neg c_a \doteq c_b \rightarrow \neg c_i \doteq c_j)| i,j \in I, i \neq j \}\, \cup \, \{\varphi_{\ge n} | n \in \Bbb N \}

erzeugte Theorie hat keine endlichen Modelle und ist \omega-kategorisch, denn in einem abzählbaren Modell müssen alle Konstanten gleich interpretiert werden. Die Theorie ist aber nicht vollständig, da die Aussage

 c_a \doteq c_b

weder widerlegt noch bewiesen werden kann.

Verallgemeinerungen[Bearbeiten]

Die Spektralfunktion \mathrm{I}(\lambda,\mathrm{T}) ordnet einer Theorie und einer Kardinalzahl die Anzahl der nicht isomorphen Modelle dieser Kardinalzahl zu. Das Spektralproblem besteht darin, die Werte dieser Funktion zu finden. Es wird also nicht nur untersucht, wann eine Theorie kategorisch ist, sondern überhaupt gefragt, wie viele nicht-isomorphe Modelle einer bestimmten Mächtigkeit eine Theorie hat.

Einzelnachweise[Bearbeiten]

  1. Wilfrid Hodges: First Order Model Theory. In: Edward N. Zalta (Hrsg.): Stanford Encyclopedia of Philosophy
  2.  Wolfgang Rautenberg: Einführung in die Mathematische Logik. Vieweg+Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2., Bemerkung nach Kapitel 5.2.
  3.  Wolfgang Rautenberg: Einführung in die Mathematische Logik. Vieweg+Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2., Bemerkung nach Kapitel 5.2, Beispiel 4
  4.  Wolfgang Rautenberg: Einführung in die Mathematische Logik. Vieweg+Teubner, Wiesbaden 2008, ISBN 978-3-8348-0578-2., Bemerkung nach Kapitel 5.5, Satz 5.2