Einiges zur Modelltheorie von (ℚ, <)

Markus Junker

Juli 2004

Axiomatisierbarkeit Sei 𝔔 := (ℚ, <) die Ordnung der rationalen Zahlen. Dies ist eine totale lineare Ordnung, die dicht und offen ist, d.h. 𝔔 erfüllt folgende Axiome einer Theorie T:

∀v_{0} ¬v_{0} < v_{0}  (irreflexiv)
∀v_{0}∀v_{1} (v_{0} < v_{1} ∨ v_{0} = v_{1} ∨ v_{1} < v_{0})  (total)
∀v_{0}∀v_{1}∀v_{2} (v_{0} < v_{1} ∧ v_{1} < v_{2} → v_{0} < v_{2})  (transitiv)
∀v_{0}∀v_{1}∃v_{2} (v_{0} < v_{1} → v_{0} < v_{2} < v_{1})  (dicht)
∀v_{0}∃v_{1}∃v_{2} v_{1} < v_{0} < v_{2}  (offen)

Aus der Offenheit folgt, daß Modelle von T stets unendlich sind. T ist induktiv, aber weder universell (ℚ hat endliche Unterstrukturen) noch existentiell (dies gilt bereits für Ordnungen nicht). T ist ein Beispiel einer endlich axiomatisierten, vollständigen Theorie ohne endliche Modelle (vollständig: siehe Folgerung 3). T ist in L_{3} axiomatisiert, aber nicht in L_{2} axiomatisierbar:

Satz 1 Genau dann gilt (O, <) ≡_{L_{2}} (ℚ, <) für eine lineare Ordnung (O, <), wenn O weder Maximum noch Minimum hat.

□ Offenheit ist in L_{2} ausdrückbar. Die Umkehrung ist offensichtlich mit dem ”Murmel–Spiel“ (Ehrenfeucht–Fraïssé–Spiel für zwei Variablen). □

Quantorenelimination, Modellvervollständigung, Kategorizität

Satz 2 Jeder partielle Isomorphismus zwischen Modellen von T läßt sich fortsetzen.

□ Seien a_{1} < ⋯ < a_{n} in (A, <) und b_{1} < ⋯ < b_{n} in (B, <) gegeben. Ein weiteres Element a ∈ A ist entweder < a_{1} oder > a_{n} oder liegt zwischen einem a_{i} und a_{i+1}. In den beiden ersten Fällen erlaubt es die Offenheit, im letzten Fall die Dichtheit, ein entsprechendes Element in B zu finden. □

Folgerung 3 T ist vollständig, ℵ_{0}-kategorisch und erlaubt Quantorenelimination.

Die ℵ_{0}-Kategorizität wurde bereits von Cantor in [Ct] bewiesen.

Satz 4 T ist die Modellvervollständigung der Theorie linearer Ordnungen.

□ Jede lineare Ordnung (O, <) läßt sich in eine dicht offene Ordnung einbetten, etwa O × ℚ mit der lexikografischen Ordnung, o ↦ (o, 0). Da T Quantoren eliminiert, reicht dies. □

Insbesondere ist T_{∀} gerade die Theorie der linearen Ordnungen.

Satz 5 ℚ ist der Fraïssé–Limes der endlichen Ordnungen.

□ Die Klasse der endlichen Ordnungen hat die Joint Embedding Property und die Amalgamation Porperty: die disjunkte Vereinigung zweier Ordnungen über einer dritten, eventuell leeren, ist eine partielle Ordnung, die man zu einer totalen erweitern kann. Also existiert der Fraïssé–Limes, der abzählbar ist und wegen der Erweiterungseigenschaften offen und dicht. □

Modelle Jedes offene Intervall in einem Modell von T ist wieder ein Modell von T. T ist ℵ_{0}-kategorisch, also ist 𝔔 bis auf Isomorphie einziges abzählbares Modell, somit nichtminimale Primstruktur und saturiert. Als nicht-stabile Theorie hat T hingegen 2^{κ} viele Isomorphietypen von Modellen überabzählbarer Mächtigkeit κ. Solche Modelle kann man explizit angeben: für χ ∈ ^{κ}{±1} setze zum Beispiel O_{χ} als die geordnete disjunkte Vereinigung ⋃_{α∈κ} (ω_{1}^{χ(α)} × (ℚ, <)), wobei ω_{1}^{1} die Ordnung (ω_{1}, ∈)

sei und ω_{1}^{−1} die umgekehrte Ordnung. Jedes Modell ist ℵ_{0}-saturiert. In κ-saturierten Modellen muß die Kofinalität in jedem Schnitt von einer Seite aus mindestens κ sein. ℝ ist stark ℵ_{0}-homogen, aber nicht (schwach) ℵ_{1}-homogen. 𝔔 ist ”selbstähnlich“, das heißt jedes offene Intervall in ℚ ist zu ℚ isomorph. Alle saturierten Modelle sind selbstähnlich. ℝ ist selbstähnlich, aber nicht homogen. Jedes überabzählbare selbstähnliche Modell enthält ℝ.

Stabilität und Ähnliches Aus der Quantorenelimination sieht man sofort:

Satz 6 𝔔 ist o-minimal.

Und zwar ist es eine triviale o-minimale Struktur im Sinne von [PS]. In 𝔔 definierbare Funktionen ℚ^{n} ⊇ D → ℚ sind stückweise aus konstanten Funktionen x̄ ↦ c und Projektionen x̄ ↦ x_{i} zusammengesetzt. Die Zellzerlegung in o-minimalen Strukturen ergibt in diesem Fall also besonders einfache Zellen: mehrdimensionale Quader und durch Gleichungen x_{i} > x_{j} beschränkte Quader.

Satz 7 𝔔 hat nicht die Unabhängigkeitseigenschaft.

□ Andernfalls gäbe es eine Formel φ(x, ȳ) mit der Unabhängigkeitseigenschaft. Aus der o-Minimalität folgt aber eine Schranke n_{φ} für die Anzahl an Zusammenhangskomponenten für φ(ℚ, ā). Da man mit einem Intervall nur die 2-Unabhängigkeitseigenschaft erreicht, hat φ höchstens die 2n_{φ}-Unabhängigkeitseigenschaft. □

Andererseits hat 𝔔 als total geordnete Struktur die starke Ordnungseigenschaft, ist also weder stabil noch simple. 𝔔 ist als o-minimale Struktur mit Imaginärenelimination rosig (siehe Onshuus, Scheuermann) und vermutlich ”superrosig“. 𝔔 ist fast äquational ([JK]).

Typen Sei 𝔄 ⊨ T. Definiere für p ∈ S_{1}(A) die Mengen A_{p}^{−} := {a ∈ A | a < x ∈ p} und A_{p}^{+} := {a ∈ A | x < a ∈ p}. Dann gilt A_{p}^{−} < A_{p}^{+} und, außer wenn p ein realisierter Typ ist, A_{p}^{−} ∪ A_{p}^{+} = A. Es gibt sechs Arten von Typen in S_{1}(A) (sei a ∈ A):

1. die realisierten Typen p_{a}(x/A) = ⟨x ˙=a⟩;

2. der Typ p_{−∞}(x/A) mit A_{p}^{−} = ∅, A_{p}^{+} = A;

3. der Typ p_{+∞}(x/A) mit A_{p}^{−} = A, A_{p}^{+} = ∅;

4. der Typ p_{a}^{+}(x/A) mit A_{p}^{−} = {x ∈ A | x ⩽ a} (A_{p}^{−} hat Maximum);

5. der Typ p_{a}^{−}(x/A) mit A_{p}^{−} = {x ∈ A | x < a} (A_{p}^{+} hat Minimum);

6. der Typ p_{s}(x/A) für einen echten Schnitt s (A_{p}^{−} hat kein Supremum, A_{p}^{+} kein Infimum);

Die Typen 1) – 5) existieren stets; Typ 6) genau dann, wenn 𝔄 keine vollständige Ordnung ist. Falls 𝔄 ⊆ 𝔅, so entsprechen die Fortsetzungen von p ∈ S(A) auf B den Schnitten in p[B]. Falls A dicht in B liegt, so haben die Typen 1) – 5) eine eindeutige Fortsetzung auf B. Typ 6) hat genau dann eine eindeutige Fortsetzung, wenn der Schnitt s nicht realisiert wird. Ansonsten hat er genau drei Fortsetzungen auf eine Realisierung b: p_{b}(x), p_{b}^{−}(x) oder p_{b}^{+}(x). Alle Typen außer den echten Schnitttypen sind definierbar; keine Typen außer den realisierten sind stabil.

• p_{−∞}(x/B) ist Erbe von p_{−∞}(x/A); der Ko-Erbe ist der Typ des Schnitts (p_{−∞}[B]|A); Erbe und Ko-Erbe die einzigen nicht-splittenden Erweiterungen.

• p_{a}^{+}(x/B) ist Erbe von p_{a}^{+}(x/A), der Ko-Erbe ist der Typ des Schnitts (a|p_{a}^{+}[B]); Erbe und Ko-Erbe die einzigen nicht-splittenden Erweiterungen.

• Entsprechend für p_{+∞}(x) und p_{a}^{−}(x).

• Alle nicht-realisierten Erweiterungen eines echten Schnitttypen p_{s}(x/A) sind Erben; Ko-Erben sind die Typen der Schnitte (A_{p_{s}}^{−}|p_{s}[B]) und (p_{s}[B]|A_{p_{s}}^{+}). Nur die Ko-Erben splitten nicht.

Anzahl der Typen:

|S_{n}(∅)| = ∑_{k=1}^{n} |Surj(n, k)| = ∑_{k=1}^{n} k! · S_{n,k} = ∑_{k=1}^{n} ∑_{j=1}^{k}(−1)^{k−j}\binom{k}{j}j^{m}.

Dies ergibt die Folge 1, 1, 3, 13, 75, 541, 4683, 47293, ... (Sloanes A000670, auch geordnete Bell– Zahlen genannt; S_{n,k} sind die Stirling–Zahlen zweiter Art).

|S_{1}(a_{1}, …, a_{n})| = 2n + 1
|S_{2}(a_{1}, …, a_{n})| = n(2n + 1) + (n + 1)(2n + 3) = 4n^{2} + 6n + 3

Über diskreten unendlichen Parametermengen A gibt es |A| viele Typen, z.B. S_{1}(ℤ) = ℵ_{0}. Über Parametermengen, die (in einem Intervall) in sich dicht sind, gibt es mindestens kontinuumsviele Typen, z.B. S_{1}(ℚ) = 2^{ℵ_{0}}.

Imaginären

Satz 8 ([Po], [Pi]) Jede definierbare Menge in 𝔔 besitzt einen kanonischen Parameter. Also hat 𝔔 Imaginärenelimination: Für jedes e ∈ 𝔔^{eq} existiert ein interdefinierbares ā ∈ 𝔔.

□ Falls X ⊆ ℚ^{k} definierbar mit Parametern ā und b̄ ist, dann auch mit Parametern ā∩b̄: denn ein Automorphismus, der b̄ festhält, aber ā\b̄ verschiebt, läßt X fest. Also kommt es nur auf den Typ von ā\b̄ über ā∩b̄ an, und man kann diese zusätzlichen Parameter abquantifizieren. Mithin hat jede definierbare Menge eine kleinste Definitionsmenge. Da die Struktur linear geordnet ist, ist dies bereits kanonischer Parameter. □

𝔔 definiert aber kein Konstanten, daher ist nicht jede definierbare Äquivalenzrelation Faserung einer definierbaren Funktion. 𝔔 mit zwei ausgezeichneten Konstanten bzw. \overline{𝔔} := (ℚ∪\{±∞\}, <) hat in diesem Sinne volle Imaginärenelimination. Aut(𝔔) operiert transitiv auf ℚ, insbesondere ist acl(∅) = ∅. Aus der Imaginärenelimination folgt acl^{eq}(A) = dcl^{eq}(acl(A)) für beliebige Parametermengen A, also ist acl^{eq}(∅) = dcl^{eq}(∅).

Redukte und Expansionen

Satz 9 𝔔 hat genau fünf Redukte: 𝔔 selbst, die triviale Struktur auf ℚ, die dichte offene Zwischenrelation, die dichte zyklische Ordnung und die dichte Trennrelation.

□ Siehe [Cm1], [Cm2], [HLS], [Hi] oder [JZ]. □

(Q, <, a_{1}, …, a_{n}) hat endliche viele Redukte, die vollständig in [JZ] klassifiziert sind. Für n = 1 sind dies 116. Eine grobe untere Schranke ist 5^{n+1}.

Satz 10 Jede ℵ_{0}-kategorische Struktur hat eine ℵ_{0}-kategorische Expansion durch eine dichte lineare Ordnung. Hat die Originalstruktur Quantorenelimination in einer relationalen Sprache, dann hat elmiminert die expandierte Struktur Quantoren in der um die Ordnung erweiterten Sprache.

□ Die Struktur ist der Fraïsé–Limes ihrer algebraisch abgeschlossenen endlich erzeugtenen Unterstrukturen mit der vollen induzierten Struktur (wobei gegebenenfalls die leere Struktur zugelassen ist). Diese Klasse 𝔎 erlaubt freie Amalgamierungen, d.h. ohne den Schnitt zu vergrößern. Dann gestattet auch die Klasse 𝔎_{<} aller total geordneten Strukturen aus 𝔎 freie Amalgamierung, und der Fraïssé–Limes von 𝔎_{<} ist die gesuchte Expansion. □

Beispiel Es gibt ℵ_{0}-kategorische Expansionen von 𝔔 durch einstellige Prädikate, die keine Quantorenelimination in einer Sprache aus < und einstelligen Prädikaten gestattet: Betrachte [0, 1] × ℚ, P = {0} × ℚ, R = {1} × ℚ und S das Komplement. P und R sind dicht ineinander, aber jedes Element in P hat einen direkten Nachfolger in S. Diese Struktur ist in ℚ × ℚ interpretierbar, also ℵ_{0}-kategorisch. Beispiel 𝔔 mit einer streng monoton wachsenden Folge ist eine vollständige Theorie mit drei abzählbaren Modellen. 𝔔 mit einem Prädikat für ein echtes, nicht-leeres Anfangsstück ist eine Theorie mit drei ℵ_{0}-kategorischen Vervollständigungen.

Literatur

[Cm1] Peter Cameron, Transitivity of permutation groups on unordered sets, Math. Z. 148 (1976), pp. 127–139.

[Cm2] Peter Cameron Oligomorphic permutation groups, LMSLN 152, Cambridge University Press 1990.

[Ct] Georg Cantor, Beiträge zur Begründung der transfiniten Mengenlehre, Math. Annalen 46 (1895), pp. 481–512.

[Hi] Graham Higman, Homogeneous relations. Quart. J. Math. 28 no. 109 (1977), pp. 31–39.

[HLS] Wilfrid Hodges, Alistair Lachlan, Saharon Shelah, Possible orderings of an indiscernible sequence, Bull. London Math. Soc. 9 (1977), pp. 212–125.

[JK] Markus Junker, Ingo Kraus, Theories with equational forking, Journal of Symbolic Logic 67 no. 1 (2002) pp. 326-340.

[JZ] Markus Junker, Martin Ziegler, The 116 reducts of (ℚ, <, a), preprint.

[PS] Ya’acov Peterzil, Sergei Starchenko, A trichotomy theorem for o-minimal structures. Proc. London Math. Soc. (3) 77 no. 3 (1998), pp. 481–523.

[Pi] Anand Pillay, Some remarks on definable equivalence relations in o-minimal structures, JSL 51 no. 3 (1986), pp. 709–714

[Po] Bruno Poizat, Une théorie de Galois imaginaire. JSL 48 no. 4 (1983), pp. 1151–1170.