Vorlesung über Modelltheorie^{1}

Martin Ziegler

Freiburg

Wintersemester 1997/98, 2000/2001

1Version 6.2e (8.9.2007)

Inhaltsverzeichnis

1 Grundbegriffe 3 1 Strukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Formeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3 Theorien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2 Elementare Unterstrukturen und der Kompaktheitssatz 19 4 Elementare Unterstrukturen . . . . . . . . . . . . . . . . . . . . . 19 5 Der Kompaktheitssatz . . . . . . . . . . . . . . . . . . . . . . . . 22 6 Der Satz von Löwenheim–Skolem . . . . . . . . . . . . . . . . . . 27

3 Quantorenelimination 29 7 Erhaltungssätze . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 8 Quantorenelimination . . . . . . . . . . . . . . . . . . . . . . . . 34 9 Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

4 Abzählbare Modelle 46 10 Der Omitting Types Satz . . . . . . . . . . . . . . . . . . . . . . 46 11 ℵ_{0}–kategorische Theorien . . . . . . . . . . . . . . . . . . . . . . 49 12 Primmodelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5 ℵ_{1}–kategorische Theorien 59 13 Indiscernibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 14 ω–stabile Theorien . . . . . . . . . . . . . . . . . . . . . . . . . . 62 15 Vaughtsche Paare . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 16 Morley abwärts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 6 Die Baldwin–Lachlan Theorie 72

17 Streng minimale Theorien . . . . . . . . . . . . . . . . . . . . . . 72 18 Der Satz von Baldwin–Lachlan . . . . . . . . . . . . . . . . . . . 78

A Mengenlehre 81 19 Kardinalzahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 20 Ordinalzahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

B Körpertheorie 86 21 Ringe und Körper . . . . . . . . . . . . . . . . . . . . . . . . . . 86 22 Algebraisch abgeschlossene Körper . . . . . . . . . . . . . . . . . 89 23 Reell abgeschlossene Körper . . . . . . . . . . . . . . . . . . . . . 91

Literaturverzeichnis 95

Index 96

Änderungen 102

Kapitel 1

Grundbegriffe

1 Strukturen

Definition Eine Sprache L ist eine Menge von Konstanten, Funktionszeichen und Relationszeichen^{1}.

Funktionszeichen und Relationszeichen haben eine Stelligkeit ≥ 1. Man kann Konstanten auch als 0–stellige Funktionszeichen auffassen. In vielen Diskussionen wird der Fall der Konstanten übergangen, wenn der Fall der Funktionszeichen sich auf den 0–stelligen überträgt.

Eine Liste von Beispielen:

L_{∅} = ∅  Die leere Sprache
L_{AG} = \{\underline{0}, +, −\}  Die abelsche Gruppen–Sprache.
L_{R} = L_{AG} ∪ \{\underline{1}, ·\} Die Ring–Sprache.
L_{G} = \{\underline{e}, ∘,^{−1}\}  Die Gruppen–Sprache.
L_{O} = {<}  Die Ordnungs–Sprache.
L_{AR} = L_{R} ∪ L_{O}  Die angeordneter Ring–Sprache.
L_{N} = \{\underline{0}, S, +, ·, <\} Die Sprache der natürlichen Zahlen.
L_{Me} = {ϵ}  Die Mengenlehre-Sprache.

Dabei sind

Konstanten:  \underline{0}, \underline{1}, \underline{e}
einstellige Funktionszeichen: −, ^{−1}, S
zweistellige Funktionszeichen: +, ·, ∘
zweistellige Relationszeichen: <, ϵ.

Definition Sei L eine Sprache. Eine L–Struktur ist ein Paar 𝔄 = (A, (Z^{𝔄})_{Z∈L}), wobei

1 Wir verwenden Relationszeichen und Prädikat synonym.

A  eine nicht–leere Menge (die Grundmenge^{2} von 𝔄) ist,
Z^{𝔄} ∈ A,  wenn Z eine Konstante ist,
Z^{𝔄} : A^{n} ⟶ A, wenn Z ein n–stelliges Funktionszeichen ist, und
Z^{𝔄} ⊂ A^{n},  wenn Z ein n–stelliges Relationszeichen ist.

Die Mächtigkeit (oder Kardinalität) von 𝔄 ist die Mächtigkeit von A. Wir schreiben dafür |𝔄| .

Definition 𝔄 und 𝔅 seien L–Strukturen. Eine Abbildung h : A → B heißt Homomorphismus, wenn für alle a_{1}, …, a_{n} ∈ A

h(c^{𝔄}) = c^{𝔅}
h(f^{𝔄}(a_{1}, …, a_{n})) = f^{𝔅}(h(a_{1}), …, h(a_{n}))
R^{𝔄}(a_{1}, …, a_{n}) ⇒ R^{𝔅}(h(a_{1}), …, h(a_{n}))

für alle Konstanten c, n-stelligen Funktionszeichen f und Relationszeichen R aus L. Wir schreiben dafür

h : 𝔄 → 𝔅.

Wenn h injektiv ist und immer

R^{𝔄}(a_{1}, …, a_{n}) ⇔ R^{𝔅}(h(a_{1}), …, h(a_{n}))

ist h eine (isomorphe) Einbettung. Ein Isomorphismus ist eine surjektive isomorphe Einbettung. Man notiert Isomorphismen als

h : 𝔄 →^{∼} 𝔅.

Wenn es einen Isomorphismus zwischen 𝔄 und 𝔅 gibt, heißen sie isomorph. In Zeichen

𝔄 ≅ 𝔅.

Man sieht leicht, daß Isomorphie eine Äquivalenzrelation ist.

Lemma 1.1 Sei 𝔄 eine L–Struktur und h : A → B eine Bijektion. Dann läßt sich B auf genau eine Weise zu einer L–Struktur 𝔅 machen, sodaß h ein Isomorphismus

h : 𝔄 →^{∼} 𝔅

wird.

Beweis: Man definiert (Z^{𝔅}) durch

c^{𝔅} = h(c^{𝔄})
f^{𝔅}(h(a_{1}), …, h(a_{n})) = h(f^{𝔄}(a_{1}, …, a_{n}))
R^{𝔅}(h(a_{1}), …, h(a_{n})) ⇔ R^{𝔄}(a_{1}, …, a_{n})
□

2 Wir nennen A auch Universum. Die Forderung, daß A nicht leer sein soll, ist eine reine (und gelegentlich lästige) Konvention.

Definition 𝔄 heißt Unterstruktur von 𝔅, wenn A ⊂ B und die Inklusionsabbildung eine isomorphe Einbettung von 𝔄 nach 𝔅 ist. Schreibweise:

𝔄 ⊂ 𝔅.

Manchmal schreibt man 𝔅 ↾ A für 𝔄.

Lemma 1.2 Sei 𝔅 eine L–Struktur und A eine nicht–leere Teilmenge von B. A ist genau dann Universum einer (eindeutig bestimmten) Unterstruktur 𝔄, wenn A alle c^{𝔅} enthält und unter allen Operationen f^{𝔅} abgeschlossen ist.

Beweis: Klar. □ Manchmal sagt man dann einfach: A ist Unterstruktur von 𝔅.

Folgerung 1.3 Wenn h : 𝔄 → 𝔅, ist h(A) Universum einer Unterstruktur von 𝔅.

Beweis: Man rechnet leicht nach, daß h(A) die Bedingung von 1.2 erfüllt. □

Lemma 1.4 Wenn alle 𝔄_{i} Unterstrukturen von 𝔅 sind, ist der Durchschnitt der A_{i} leer oder eine Unterstruktur von 𝔅.

Beweis: Klar mit 1.2. □

Folgerung 1.5 Sei S eine nicht–leere Teilmenge von 𝔅. Dann gibt es eine kleinste Unterstruktur 𝔄 = ⟨S⟩^{𝔅}, die S enthält.

Beweis: Für A nimmt man den Durchschnitt aller Unterstrukturen von 𝔅, die S enthalten. Dieser Durchschnitt ist nicht leer, weil er S enthält. □ Wir nennen 𝔄 das Erzeugnis von S.

Wenn L eine Konstante enthält, ist der Durchschnitt aller Unterstrukturen von 𝔅 nicht leer, weil er die 𝔅–Interpretation dieser Konstanten enthält. 𝔅 hat also eine kleinste Unterstruktur ⟨∅⟩^{𝔅}.

Lemma 1.6 Wenn 𝔄 von S erzeugt wird, wird ein Homomorphismus h : 𝔄 → 𝔅 durch seine Werte auf S bestimmt.

Beweis: Wenn h′ : 𝔄 → 𝔅 ein anderer Homomorphismus ist, ist C = {b | h(b) = h′(b)} eine Unterstruktur. Wenn h und h′ auf S übereinstimmen, ist S Teilmenge von C, und also C = A. □

Lemma 1.7 Sei h : 𝔄 →^{∼} 𝔄′ ein Isomorphismus und 𝔅 eine Oberstruktur von 𝔄. Dann gibt es eine Oberstruktur 𝔅′ von 𝔄′ und eine Fortsetzung g : 𝔅 →^{∼} 𝔅′ von h.

Beweis: Man setzt zuerst die Bijektion h : A → A′ zu einer Bijektion g : B → B′ fort und wendet dann 1.1 an. □

Definition Sei (I, ≤) eine gerichtete partielle Ordnung^{3}. Eine Familie (𝔄_{i})_{i∈I} von L–Strukturen heißt gerichtet, wenn

i ≤ j ⇒ 𝔄_{i} ⊂ 𝔄_{j}.

Wenn I linear geordnet ist, nennt man (𝔄_{i})_{i∈I} eine Kette. Wenn zum Beispiel eine Struktur 𝔄_{1} isomorph zu einer Unterstruktur 𝔄_{0} ⊂ 𝔄_{1} ist,

h_{0} : 𝔄_{0} →^{∼} 𝔄_{1},

liefert 1.7 eine Erweiterung

h_{1} : 𝔄_{1} →^{∼} 𝔄_{2}.

Wenn wir so fortfahren, ergibt sich eine Kette 𝔄_{0} ⊂ 𝔄_{1} ⊂ 𝔄_{2} … und eine aufsteigende Folge h_{i} : 𝔄_{i} →^{∼} 𝔄_{i+1} von Isomorphismen.

Lemma 1.8 Sei (𝔄_{i})_{i∈I} eine gerichtete Familie von L–Strukturen. Dann ist A = ⋃_{i∈I} A_{i} Universum einer (eindeutig bestimmten) Struktur

𝔄 = ⋃_{i∈I} 𝔄_{i},

die Oberstruktur aller 𝔄_{i} ist.

Beweis: Sei R ein n–stelliges Relationszeichen und a_{1}, …, a_{n} ∈ A. Weil I gerichtet ist, gibt es einen Index k, sodaß alle a_{i} in A_{k} liegen. Man definiert (und das ist die einzige Möglichkeit)

R^{𝔄}(a_{1}, …, a_{n}) ⇔ R^{𝔄_{k}}(a_{1}, …, a_{n}).

Ähnlich verfährt man mit Konstanten und Funktionszeichen. □

Eine Teilmenge K von L nennen wir eine Teilsprache. Eine L–Struktur wird eine K–Struktur, wenn wir die Interpretation der Zeichen aus L \ K vergessen:

𝔄 ↾ K = (A, (Z^{𝔄})_{Z∈K})

Wir nennen diesen Prozeß Restriktion. Umgekehrt heißt 𝔄 Expansion von 𝔄 ↾ K. Dafür einige Beispiele:

Wir halten ein L–Struktur 𝔄 fest. a) Wenn R eine n–stellige Relation auf A ist, führen wir ein neues Relations-

3 Das bedeutet, daß es für alle i, j ∈ I ein k ∈ I gibt mit i ≤ k und j ≤ k.

zeichen \underline{R} ein und bezeichnen mit

(𝔄, R)

die Expansion von 𝔄 zu einer L∪\{\underline{R}\}–Struktur, in der \underline{R} durch R interpretiert wird.

b) Für Elemente a_{1}, …, a_{n} können wir neue Konstanten \underline{a}_{1}, …, \underline{a}_{n} und die L ∪

\{\underline{a}_{1}, …, \underline{a}_{n}\}–Struktur

(𝔄, a_{1}, …, a_{n})

einführen.

c) Sei B eine Teilmenge von A. Wir fassen jedes Element von B als neue Konstante auf, das ergibt die Sprache

L(B) = L ∪ B^{4}

und die L(B)–Struktur

𝔄_{B} = (𝔄, b)_{b∈B} .

4 Wenn C eine Mengen von Konstanten ist, schreiben wir häufig L(C) für L ∪ C.

2 Formeln

L–Terme sind Zeichenfolgen, die aus den Konstanten, den Funktionszeichen von L und den Variablen

v_{0}, v_{1}, …

nach den folgenden Regeln gebildet sind.

Definition Jede Variable v_{i} ist ein L–Term.

Jede Konstante c ist ein L–Term.

Wenn f ein n–stelliges Funktionszeichen ist und wenn t_{1}, …, t_{n} L–Terme sind, dann ist auch ft_{1} … t_{n} ein L–Term.

Um Terme besser lesbar zu machen, schreiben wir häufig f(t_{1}, …, t_{n}) statt ft_{1} … t_{n}. Wenn f einstellig ist, auch t_{1}f, wenn f zweistellig ist, auch t_{1}ft_{2}. Zum Beispiel steht (x + y) · (z + w) für · + xy + zw und (x ∘ y)^{−1} für ^{−1} ∘ xy.

Sei 𝔄 eine L–Struktur und b⃗ = (b_{0}, b_{1}, …) eine Folge von Elementen, die wir als Belegung der Variablen v_{0}, v_{1}, … auffassen. Wenn wir im Term t die Variable v_{i} jeweils durch b_{i} ersetzen, berechnet t in naheliegender Weise ein Element t^{𝔄}[b⃗] von 𝔄:

Definition Für L–Terme t, L–Strukturen 𝔄 und Belegungen b⃗ definieren wir t^{𝔄}[b⃗] durch

v_{i}^{𝔄}[b⃗] = b_{i}
c^{𝔄}[b⃗] = c^{𝔄}
ft_{1} … t_{n}^{𝔄}[b⃗] = f^{𝔄}(t_{1}^{𝔄}[b⃗], …, t_{n}^{𝔄}[b⃗])

Diese (rekursive) Definition ist nur möglich, weil Terme eindeutig lesbar sind: Wenn ft_{1} … t_{n} = ft′_{1} … t′_{n}, ist t_{1} = t′_{1}, …, t_{n} = t′_{n}. Der Beweis ist nicht schwer.

Lemma 2.1 t^{𝔄}[b⃗] hängt von b_{i} nur ab, wenn v_{i} in t vorkommt.

Beweis: Klar. □

Wenn die Variablen x_{1}, …, x_{n} paarweise verschieden sind^{5} und keine anderen Variablen in t vorkommen, schreiben wir

t = t(x_{1}, …, x_{n}).

Sei b⃗ eine Variablenbelegung die x_{i} mit a_{i} belegt. Dann ist

t^{𝔄}[a_{1}, …, a_{n}]

5Beachte x_{i} ∈ {v_{0}, v_{1}, …}.

durch t^{𝔄}[b⃗] nach dem letzten Lemma eindeutig definiert. Wenn t_{1}, …, t_{n} Terme sind, bezeichnen wir mit

t(t_{1}, …, t_{n})

den Term, der aus t entsteht, wenn wir x_{1}, …, x_{n} durch t_{1}, …, t_{n} ersetzen (Substitution). Man zeigt leicht, daß

Lemma 2.2 (Substitutionslemma)

t(t_{1}, …, t_{n})^{𝔄}[b⃗] = t^{𝔄} [t_{1}^{𝔄}[b⃗], …, t_{n}^{𝔄}[b⃗]]
□

Expandiert man 𝔄 zu einer L(A)–Struktur 𝔄_{A} (vgl. S. 7), so hat man den Spezialfall

t(a_{1}, …, a_{n})^{𝔄_{A}} = t^{𝔄}[a_{1}, …, a_{n}].

Lemma 2.3 h : 𝔄 → 𝔅 sei ein Homomorphismus und t(x_{1}, …, x_{n}) ein Term. Dann ist für alle a_{1}, …, a_{n} aus A

t^{𝔅}[h(a_{1}), …, h(a_{n})] = h (t^{𝔄}[a_{1}, …, a_{n}]) .

Beweis: Induktion über den Aufbau von t. □

Lemma 2.4 S sei eine nicht–leere Teilmenge der L–Struktur 𝔄. Dann ist

⟨S⟩^{𝔄} = {t^{𝔄}[s_{1}, …, s_{n}] | t(x_{1}, …, x_{n}) L–Term, s_{1}, …, s_{n} ∈ S} .

Beweis: Aus 2.3 folgt, daß das Universum einer Unterstruktur unter t^{𝔄}[−, …, −] abgeschlossen ist. Daraus folgt, daß die rechte Seite in ⟨S⟩^{𝔄} enthalten ist. Für die Umkehrung zeigt man, daß die rechte Seite unter den Operationen f^{𝔄} abgeschlossen ist. Daraus folgt die Behauptung mit 1.2. □

Ein konstanter Term ist ein Term ohne Variable. Wenn L mindestens eine Konstante enthält, hat man

⟨∅⟩^{𝔄} = {t^{𝔄} | t konstanter L–Term} .

Aus dem letzten Lemma ergibt sich:

Folgerung

|⟨S⟩^{𝔄}| ≤ max{ℵ_{0}, |L|, |S|}

Beweis: Es gibt höchstens max{ℵ_{0}, |L|} viele L–Terme und für jeden Term höchstens max{ℵ_{0}, |S|} viele Einsetzungen aus S. □

L–Formeln sind Zeichenreihen, die aus den Zeichen aus L, den Klammern ( und ) als Hilfszeichen und den folgenden logischen Zeichen gebildet sind:

Variablen  v_{0}, v_{1}, …
Gleichheitszeichen =^{.}
Junktoren (Negationszeichen und Konjunktion) ¬, ∧
Existenzquantor  ∃

Definition L–Formeln sind

t_{1} =^{.} t_{2} , wenn t_{1}, t_{2} L–Terme sind,

Rt_{1} …, t_{n}  , wenn R ein n–stelliges Relationszeichen aus L und t_{1}, …, t_{n} L–Terme sind,

¬ψ , wenn ψ eine L–Formel ist,

(ψ_{1} ∧ ψ_{2}) , wenn ψ_{1} und ψ_{2} L–Formeln sind,

∃x ψ , wenn ψ eine L–Formel und x eine Variable ist.

Formeln der Form t_{1} =^{.} t_{2} oder Rt_{1} …, t_{n} heißen Primformeln^{6}.

Wir verwenden folgende Abkürzungen:

(ψ_{1} ∨ ψ_{2}) = ¬(¬ψ_{1} ∧ ¬ψ_{2})
(ψ_{1} → ψ_{2}) = ¬(ψ_{1} ∧ ¬ψ_{2})
(ψ_{1} ↔ ψ_{2}) = ((ψ_{1} → ψ_{2}) ∧ (ψ_{2} → ψ_{1}))
∀x ψ = ¬∃x¬ψ

für die Disjunktion, die Implikation, die Äquivalenz und den Allquantor.

Statt Rt_{1}t_{2} schreiben wir auch t_{1}Rt_{2} und statt ∃x_{1} … ∃x_{n} schreiben wir ∃x_{1} … x_{n} (ebenso für ∀). Zur besseren Lesbarkeit der Formeln gebrauchen wir überflüssige Klammern. Wir lassen auch Klammern weg und lesen die Formeln gemäß der Bindungsstärke der logischen Zeichen:

Höchste Bindungsstärke:  ¬ ∃ ∀
∧
∨
Niedrigste Bindungsstärke:  → ↔

Definition Sei 𝔄 eine L–Struktur. Wir definieren für Belegungen b⃗ und L– Formeln ϕ die Relation

𝔄 ⊧ ϕ[b⃗]

6Primformeln werden gelegentlich auch atomar genannt. Wir verstehen unter atomaren Formeln aber etwas anderes. (Vgl. Seite 48)

durch Rekursion über den Aufbau von ψ:

𝔄 ⊧ t_{1} =^{.} t_{2} [b⃗] ⇔ t_{1}^{𝔄}[b⃗] = t_{2}^{𝔄}[b⃗]
𝔄 ⊧ Rt_{1} … t_{n} [b⃗] ⇔ R^{𝔄} (t_{1}^{𝔄}[b⃗], …, t_{n}^{𝔄}[b⃗])
𝔄 ⊧ ¬ψ [b⃗] ⇔ 𝔄 |̸= ψ [b⃗]
𝔄 ⊧ (ψ_{1} ∧ ψ_{2}) [b⃗] ⇔ 𝔄 ⊧ ψ_{1} [b⃗] und 𝔄 ⊧ ψ_{2} [b⃗]
𝔄 ⊧ ∃xψ [b⃗] ⇔ es gibt ein a ∈ A mit 𝔄 ⊧ ψ [b⃗\frac{a}{x}]

Dabei ist (wenn x = v_{i})

b⃗\frac{a}{x} = (b_{0}, …, b_{i−1}, a, b_{i+1,...}).

Wenn 𝔄 ⊧ ϕ[b⃗] sagt man „ϕ trifft in 𝔄 auf b⃗ zu“ oder „b⃗ erfüllt ϕ“.

Damit diese Definition sinnvoll wird, muß man sich von der eindeutigen Lesbarkeit von Formeln überzeugen: Wenn Rt_{1}, …, t_{n} = Rt′_{1}, …, t′_{n}, so ist t_{1} = t′_{1}, …, t_{n} = t′_{n}. Und (ψ_{1} ∧ ψ_{2}) = (ψ′_{1} ∧ ψ′_{2}) impliziert ψ_{1} = ψ′_{1} und ψ_{2} = ψ′_{2}.

Es ist klar, daß unsere Abkürzungen die intendierte Interpretation haben. Also, daß z.B.

𝔄 ⊧ (ψ_{1} → ψ_{2})[b⃗] ⟺ wenn 𝔄 ⊧ ψ_{1}[b⃗], dann 𝔄 ⊧ ψ_{2}[b⃗].

Ob ϕ in 𝔄 auf b⃗ zutrifft, hängt nur von den freien Variablen von ϕ ab:

Definition Die Variable x kommt frei in der Formel ϕ vor, wenn sie an einer Stelle vorkommt, die nicht im Wirkungsbereich eines Quantors ∃x liegt. Präzis definiert durch Rekursion nach dem Aufbau von ϕ:

x frei in t_{1} =^{.} t_{2} ⇔ x kommt in t_{1} oder in t_{2} vor.
x frei in Rt_{1} … t_{n} ⇔ x kommt in einem der t_{i} vor.
x frei in ¬ψ ⇔ x frei in ψ
x frei in (ψ_{1} ∧ ψ_{2}) ⇔ x frei in ψ_{1} oder x frei in ψ_{2}
x frei in ∃y ψ ⇔ x ≠ y und x frei in ψ

Zum Beispiel kommt in ∀v_{0}(∃v_{1}R(v_{0}, v_{1}) ∧ P (v_{1})) die Variable v_{0} nicht frei vor. v_{1} kommt gebunden und frei vor.

Satz 2.5 Wenn b⃗ und c⃗ an allen Variablen, die frei in ϕ vorkommen, übereinstimmen, ist

𝔄 ⊧ ϕ[b⃗] ⇔ 𝔄 ⊧ ϕ[c⃗].

Beweis: Durch Induktion über den Aufbau von ϕ. □

Wenn wir eine Formel in der Form ϕ(x_{1}, …, x_{n}) schreiben, meinen wir:

• daß die x_{i} paarweise verschiedene Variable sind,

• daß in ϕ nur Variable aus {x_{1}, …, x_{n}} frei vorkommen.

Wenn dann a_{1}, …, a_{n} Elemente der Struktur 𝔄 sind, ist wegen 2.5

𝔄 ⊧ ϕ[a_{1}, …, a_{n}]

durch 𝔄 ⊧ ϕ[b⃗] für eine Belegung b⃗ mit b⃗(x_{i}) = a_{i} wohldefiniert.

Definition Eine Aussage ϕ ist eine Formel ohne freie Variable. Wir schreiben 𝔄 ⊧ ϕ, wenn 𝔄 ⊧ ϕ[b⃗] für ein (alle) b⃗.

𝔄 heißt dann Modell von ϕ. Man sagt auch ϕ gilt in 𝔄.

Wenn ϕ = ϕ(x_{1}, …, x_{n}), und t_{1}, …, t_{n} Terme sind, bezeichnen wir mit

ϕ(t_{1}, …, t_{n})

die Formel, die aus ϕ entsteht, wenn wir zuerst die gebundenen Variablen so umbenennen, daß sie verschieden sind von allen Variablen, die in den t_{i} vorkommen. Und wenn wir dann alle freien Vorkommen der x_{i} durch t_{i} ersetzen.

Lemma 2.6 (Substitutionslemma)

𝔄 ⊧ ϕ(t_{1}, …, t_{n})[b⃗] ⟺ 𝔄 ⊧ ϕ[t_{1}^{𝔄}[b⃗], …, t_{n}^{𝔄}[b⃗]]

Beweis: Leicht, durch Induktion über den Aufbau von ϕ. □

Beachte den (trivialen) Spezialfall

𝔄_{A} ⊧ ϕ(a_{1}, …, a_{n}) ⟺ 𝔄 ⊧ ϕ[a_{1}, …, a_{n}].

Wir verwenden häufig eine légère Notation und schreiben einfach

𝔄 ⊧ ϕ(a_{1}, …, a_{n}).

Sei P ein neues n–stelliges Relationszeichen und ϕ = ϕ(P) eine L(P) = L ∪ {P }–Aussage. Weiter sei π(x_{1}, …, x_{n}) eine L–Formel. Wir ersetzen jetzt jedes Vorkommen von P in ϕ durch π. Das heißt, daß jede Teilformel P t_{1} … t_{n} durch π(t_{1} … t_{n}) ersetzt wird. Die so gewonnen L–Aussage nennen wir ϕ(π). Man zeigt leicht:

Lemma 2.7

𝔄 ⊧ ϕ(π) ⟺ (𝔄, π(𝔄)) ⊧ ϕ(P)

wobei π(𝔄) = \{\overline{a} | 𝔄 ⊧ π[\overline{a}]\}.

Primformeln und negierte Primformeln nennen wir basic. Formeln ohne Quantoren (wir sagen auch quantorenfreie Formeln) sind boolesche Kombinationen von basic Formeln, das heißt sie entstehen aus basic Formeln durch sukzessives Anwenden von ¬ und ∧. Dieser Aufbauprozeß läßt sich in zwei besonders einfache Formen bringen, die konjunktive und disjunktive Normalform.

Lemma 2.8 Jede quantorenfreie Formel ist äquivalent zu einer Formel der Form

⋀_{i<m} ⋁_{j<m_{i}} π_{ij}

und einer Formel der Form

⋁_{i<m} ⋀_{j<m_{i}} π_{ij},

für basic Formeln π_{ij}. Die erste Form ist die konjunktive Normalform, die zweite die disjunktive Normalform.

Wir nennen dabei zwei Formeln äquivalent, wenn sie in allen Strukturen auf die gleichen Variablenbelegungen zutreffen. ⋀_{i<m} π_{i} ist natürlich die Konjunktion der π_{i} und ⋁_{i<m} π_{i} die Disjunktion. Wir beachten die Konvention, daß ⋀_{i<1} π_{i} = ⋁_{i<1} π_{i} = π_{0}. Es ist manchmal bequem, auch die leere Konjunktion und die leere Disjunktion zuzulassen. Wir führen dazu zwei neue Formeln ein: die immer wahre Aussage ⊤ und immer falsche Aussage ⊥. Dann setzt man sinnvollerweise

⋀_{i<0} π_{i} = ⊤

⋁_{i<0} π_{i} =⊥

Beweis: Um zum Beispiel die konjunktive Normalform zu konstruieren, zieht man mit Hilfe der Äquivalenzen

¬¬ϕ ∼ ϕ
¬(ϕ ∧ ψ) ∼ (¬ϕ ∨ ¬ψ)
¬(ϕ ∨ ψ) ∼ (¬ϕ ∧ ¬ψ)

die Negationszeichen unmittelbar vor die Primformeln und mit Hilfe von

(ϕ ∨ (ψ ∧ ρ)) ∼ ((ϕ ∨ ψ) ∧ (ϕ ∨ ρ))

die Disjunktionen nach innen. □

Lemma 2.9 Jede Formel ist äquivalent zu einer Formel in pränexer Normalform:

Q_{1}x_{1} … Q_{n}x_{n}ϕ

Die Q_{i} sind Quantoren ( ∃ oder ∀) und ϕ ist quantorenfrei.

Beweis: Wir betrachten Formeln, die mit ¬, ∧, ∃, ∀ aufgebaut sind, und ziehen die Quantoren mit

¬∃xϕ ∼ ∀x¬ϕ

¬∀xϕ ∼ ∃x¬ϕ
(ϕ ∧ ∃xψ(x, ȳ)) ∼ ∃z (ϕ ∧ ψ(z, ȳ))
(ϕ ∧ ∀xψ(x, ȳ)) ∼ ∀z (ϕ ∧ ψ(z, ȳ))

nach außen. Wir haben dabei die gebundene Variable x durch eine Variable z ersetzt, die nicht frei in ϕ vorkommt. □

Folgerung Jede Formel läßt sich äquivalent umformen in eine Formel in Negationsnormalform. Das sind Formeln, die sich aus basic Formeln mit ∧, ∨, ∃, ∀ aufbauen. □

Definition Eine Formel in Negationsnormalform, die keine Existenzquantoren enthält, heißt universell oder Allformel. Formeln in Negationsnormalform ohne Allquantoren heißen existentiell oder Existenzformeln.

Man sieht leicht ein, daß ein Isomorphismus h : 𝔄 → 𝔅 die Gültigkeit von Formeln präserviert. Man hat

𝔄 ⊧ ϕ[a_{1}, …, a_{n}] ⟺ 𝔅 ⊧ ϕ[h(a_{1}), …, h(a_{n})].

Isomorphe Einbettungen erhalten nur die Gültigkeit von existentiellen Formeln:

Lemma 2.10 h : 𝔄 → 𝔅 sei eine Einbettung. Dann ist für alle existentiellen^{7} ϕ(x_{1}, …, x_{n}) und alle a_{1}, …, a_{n} ∈ A

𝔄 ⊧ ϕ[a_{1}, …, a_{n}] ⟹ 𝔅 ⊧ ϕ[h(a_{1}), …, h(a_{n})].

Beweis: Leicht durch Induktion über den Aufbau von ϕ: Für basic Formeln folgt die Behauptung aus der Definition einer Einbettung und 2.3. Die Induktionsschritte für ∧ und ∨ sind trivial. Sei schließlich ϕ(\overline{x}) = ∃yψ(\overline{x}, y). Wenn 𝔄 ⊧ ϕ[\overline{a}], gibt es ein a ∈ A mit 𝔄 ⊧ ψ[\overline{a}, a]. Nach Induktion ist dann 𝔅 ⊧ ψ[h(\overline{a}), h(a)]. Es folgt 𝔅 ⊧ ϕ[h(\overline{a})]. □

Sei 𝔄 eine L–Struktur. Das atomare Diagramm von 𝔄 ist

Diag(𝔄) = {ϕ basic L(A)–Aussage | 𝔄_{A} ⊧ ϕ}

die Menge aller basic Aussagen mit Parametern aus A, die in 𝔄 gelten.

Lemma 2.11 Die Modelle von Diag(𝔄) sind genau die Strukturen (𝔅, h(a))_{a∈A} für Einbettungen h : 𝔄 → 𝔅.

7 für universelle ϕ gilt dual 𝔅 ⊧ ϕ[h(a_{1}), …, h(a_{n})] ⟹ 𝔄 ⊧ ϕ[a_{1}, …, a_{n}].

Beweis: Daß die Strukturen (𝔅, h(a))_{a∈A} Modelle des atomaren Diagramms sind, folgt aus 2.10. Die Umkehrung gilt, weil eine Abbildung h genau dann eine Einbettung ist, wenn sie alle Formeln der Form

(¬) x_{1} =^{.} x_{2}

c =^{.} x_{1}

f(x_{1}, …, x_{n}) =^{.} x_{0}

(¬) R(x_{1}, …, x_{n})

präserviert. □

3 Theorien

Definition Eine L–Theorie T ist eine Menge von L–Aussagen.

Eine L–Struktur 𝔄 ist ein Modell von T,

𝔄 ⊧ T,

wenn 𝔄 Modell aller Aussagen aus T ist. Wenn T ein Modell hat, heißt T konsistent, oder widerspruchsfrei.

Lemma 3.1 Sei T eine L–Theorie und K eine Erweiterung von L. Dann ist T genau dann als L–Theorie konsistent, wenn T als K–Theorie konsistent ist.

Beweis: Das folgt aus der (trivialen) Tatsache, daß sich jede L–Struktur zu einer K– Struktur expandieren läßt. □

Beispiele: In den folgenden Beispielen schreiben wir, wie in der Algebra üblich 0 und 1 für die Zeichen \underline{0} und \underline{1}. Den Multiplikationspunkt · lassen wir weg und Punktrechnung geht vor Strichrechnung.

T_{AG}, die Theorie der abelschen Gruppen, hat die Axiome

• ∀x, y, z (x + y) + z =^{.} x + (y + z)

• ∀x 0 + x =^{.} x

• ∀x (−x) + x =^{.} 0

• ∀x, y x + y =^{.} y + x

T_{R}, die Theorie der kommutativen Ringe:

• T_{AG}

• ∀x, y, z (xy)z =^{.} x(yz)

• ∀x 1x =^{.} x

• ∀x, y xy =^{.} yx

• ∀x, y, z x(y + z) =^{.} xy + xz

T_{K}, die Theorie der Körper:

• T_{R}

• ¬0 =^{.} 1

• ∀x (¬x =^{.} 0 → ∃y xy =^{.} 1)

Definition Eine Aussage ϕ folgt aus T, wenn ϕ in allen Modellen von T gilt. Wir schreiben

T ⊢ ϕ.

Aussagen, die aus ∅ folgen, heißen allgemeingültig.

Die wichtigsten Eigenschaften der Folgerungsrelation sind:

{Lemma 3.2 \atop 1.} Wenn T ⊢ ϕ und T ⊢ (ϕ → ψ), ist T ⊢ ψ.

2. Wenn T ⊢ ϕ(c_{1}, …, c_{n}) und die Konstanten c_{1}, …, c_{n} weder in T noch in ϕ(x_{1}, …, x_{n}) vorkommen, ist T ⊢ ∀x_{1} … x_{n} ϕ(x_{1}, …, x_{n}).

Beweis: Wir beweisen 2: Sei L′ = L \ {c_{1}, …, c_{n}}. Wenn die L′–Struktur 𝔄 ein Modell von T ist und a_{1}, …, a_{n} beliebige Elemente, ist (𝔄, a_{1}, …, a_{n}) ⊧ ϕ(c_{1}, …, c_{n}), das heißt 𝔄 ⊧ ∀x_{1} … x_{n}ϕ(x_{1}, …, x_{n}). Also ist T ⊢ ∀x_{1} … x_{n}ϕ(x_{1}, …, x_{n}) (im Sinne von L′ und daher wegen 3.1 auch im Sinne von L). □

Wir verallgemeinern diesen Begriff auf Theorien S: T ⊢ S heißt, daß alle Modelle von T Modelle von S sind. S und T heißen äquivalent, wenn S und T die gleichen Modelle haben. In Zeichen: T ≡ S.

Wir halten eine Sprache L fest. T sei eine L–Theorie und K eine Klasse von L–Strukturen. Wir verwenden folgende Notationen

• Mod(T) = {𝔄 | 𝔄 ⊧ T }, die Modellklasse von T.

• Th(K) = {ϕ | 𝔄 ⊧ ϕ für alle 𝔄 ∈ K}, die Theorie von K.

• Ded(T) = {ϕ | T ⊢ ϕ}, der deduktive Abschluß von T.

T heißt deduktiv abgeschlossen, wenn Ded(T) = T. Klassen der Form Mod(T) heißen elementar.

Satz 3.3 T, S seien Theorien und K ein Klasse von Strukturen.

1. T ist genau dann deduktiv abgeschlossen, wenn T die Theorie einer Klasse von Strukturen ist.

2. T ⊢ S ⇔ Ded(S) ⊂ Ded(T)

3. Ded(T) = Th(Mod(T))

Beweis: Klar. □

Definition Eine konsistente L–Theorie T ist vollständig, wenn für alle L– Aussagen ϕ

T ⊢ ϕ oder T ⊢ ¬ϕ.

Dieser Begriff hängt von L ab! Wenn T vollständig ist und K eine Erweiterung von L ist, wird im allgemeinen T als K–Theorie nicht mehr vollständig sein. Typisches Beispiel einer vollständigen Theorie ist die Theorie Th(𝔄) einer einzelnen Struktur.

Lemma 3.4 Eine konsistente Theorie T ist genau dann vollständig, wenn Ded(T) maximal konsistent ist. Das bedeutet, daß T ⊢ S für jede konsistente Erweiterung S von T.

Beweis: Wenn weder ϕ noch ¬ϕ aus T folgt, nennen wir ϕ unabhängig von T. ϕ ist genau dann unabhängig von T, wenn T ∪ {ϕ} eine im Sinne von ⊢ echte und konsistente Erweiterung von T ist. Daraus folgt die Behauptung sofort. □

Definition Zwei L–Strukturen 𝔄 und 𝔅 heißen elementar äquivalent,

𝔄 ≡ 𝔅,

wenn für alle L–Aussagen ϕ

𝔄 ⊧ ϕ ⟺ 𝔅 ⊧ ϕ.

Isomorphe Strukturen sind immer elementar äquivalent.

Lemma 3.5 T sei eine konsistente Theorie. Dann sind äquivalent

a) T ist vollständig.

b) Alle Modelle von T sind elementar äquivalent.

c) T ≡ Th(𝔄) für eine geeignete Struktur 𝔄.

Beweis: a⇒c: Sei 𝔄 ein beliebiges Modell von T. Wenn ϕ in 𝔄 gilt, ist T ⊬ ¬ϕ und daher T ⊢ ϕ. Also ist Ded(T) = Th(𝔄).

c⇒ b: Wenn 𝔅 ⊧ T ist 𝔅 ⊧ Th(𝔄) und daher 𝔅 ≡ 𝔄. Man beachte, daß ≡ eine Äquivalenzrelation ist.

b⇒a: Sei 𝔄 ein Modell von T. Wenn ϕ in 𝔄 gilt, gilt ϕ in allen Modellen von T, also T ⊢ ϕ. Sonst gilt ¬ϕ und wir haben T ⊢ ¬ϕ. □

Elementare Unterstrukturen und der Kompaktheitssatz

4 Elementare Unterstrukturen

𝔄 und 𝔅 seien zwei L–Strukturen. Eine Abbildung h : A → B heißt elementar, wenn sie die Gültigkeit beliebiger Formeln ϕ(x_{1}, …, x_{n}) präserviert^{1}. Das heißt, daß

𝔄 ⊧ ϕ[a_{1}, …, a_{n}] ⟺ 𝔅 ⊧ ϕ[h(a_{1}), …, h(a_{n})]

für alle a_{1}, …, a_{n} ∈ A. Weil h insbesondere quantorenfreie Aussagen präserviert, ist h eine Einbettung. Man nennt darum h auch elementare Einbettung. Wir schreiben

h : 𝔄 ⟶^{≺} 𝔅

Das folgende Lemma ist klar.

Lemma 4.1 Die Modelle von Th(𝔄_{A}) sind genau die Strukturen der Form (𝔅, h(a))_{a∈A} für elementare Einbettungen h : 𝔄 ⟶^{≺} 𝔅.

Th(𝔄_{A}) ist das elementare Diagramm von 𝔄.

Eine Unterstruktur 𝔄 von 𝔅 ist elementar, wenn die Inklusionsabbildung elementar ist, wenn also

𝔄 ⊧ ϕ[a_{1}, …, a_{n}] ⟺ 𝔅 ⊧ ϕ[a_{1}, …, a_{n}].

Wir schreiben 𝔄 ≺ 𝔅. 𝔅 heißt elementare Erweiterung von 𝔄.

Satz 4.2 (Tarskis Test) Sei 𝔅 eine L–Struktur und A eine Teilmenge von B. Dann ist A genau dann Universum einer elementaren Unterstruktur, wenn jede L(A)–Formel ϕ(x), die in 𝔅 erfüllbar ist, von einem Element von A erfüllt wird.

1 Eigentlich heißt das nur, daß alle Formeln, die in 𝔄 gelten, auch in 𝔅 gelten. Wenn man zur Negation übergeht, sieht man aber, daß daraus die Umkehrung folgt.

Beweis: Wenn 𝔄 ≺ 𝔅 und 𝔅 ⊧ ∃xϕ(x), so gilt auch 𝔄 ⊧ ∃xϕ(x) und es gibt ein a ∈ A mit 𝔄 ⊧ ϕ(a). Es folgt 𝔅 ⊧ ϕ(a).

Sei umgekehrt die Bedingung von Tarskis Test erfüllt. Zuerst müssen wir zeigen, daß A Universum einer Unterstruktur 𝔄 ist. Die L(A)–Formel x =^{.} x ist in 𝔅 erfüllbar, also ist A nicht leer. Wenn f ∈ L ein n–stelliges Funktionszeichen ist (n ≥ 0) und a_{1}, …, a_{n} aus A, betrachten wir die Formel

ϕ(x) = f(a_{1}, …, a_{n}) =^{.} x.

ϕ(x) wird in A erfüllt, also ist A unter den Operationen f^{𝔅} abgeschlossen. Jetzt zeigen wir durch Induktion über den Aufbau der L(A)–Aussage ψ, daß für alle ψ

𝔄 ⊧ ψ ⟺ 𝔅 ⊧ ψ.

Für Primaussagen ist das klar. Die Induktionsschritte für ψ = ¬ϕ und ψ = (ϕ_{1} ∧ ϕ_{2}) sind trivial. Sei schließlich ψ = ∃xϕ(x). Wenn ψ in 𝔄 gilt, gibt es ein a ∈ A, mit 𝔄 ⊧ ϕ(a). Die Induktionsvoraussetzung ergibt 𝔅 ⊧ ϕ(a) und daher 𝔅 ⊧ ψ. Wenn umgekehrt ψ in 𝔅 gilt, finden wir ein a ∈ B mit 𝔅 ⊧ ϕ(a). Tarskis Test erlaubt es anzunehmen, daß a ∈ A. Jetzt schließen wir wieder mit Induktion, daß 𝔄 ⊧ ϕ(a) und daher 𝔄 ⊧ ψ. □

Folgerung 4.3 S sei eine Teilmenge der L–Struktur 𝔅. Dann hat 𝔅 eine elementare Unterstruktur, die S enthält und höchstens die Mächtigkeit

max{|S|, |L|, ℵ_{0}}

hat.

Beweis: Wir setzen S_{0} = S. Wenn S_{i} schon definiert ist, wählen wir für jede L(S_{i})– Formel ϕ(x) ein Element a_{ϕ} ∈ B mit 𝔅 ⊧ ∃xϕ(x) → ϕ(a_{ϕ}) und setzen S_{i+1} = {a_{ϕ} | ϕ L(S_{i})–Formel}. Es ist klar, daß A = ⋃_{i∈ℕ} S_{i} Universum einer elementaren Unterstruktur ist. Wir müssen nur noch die Mächtigkeit von A abschätzen.

Eine L–Formel ist eine Folge aus Zeichen aus L, Hilfszeichen und logischen Zeichen. Das sind insgesamt |L| + ℵ_{0} = max(|L|, ℵ_{0}) viele Zeichen. Also gibt es nach A.19.4 genau max(|L|, ℵ_{0}) viele L–Formeln. Sei κ = max(|S|, |L|, ℵ_{0}). Es gibt κ viele L(S)–Formeln, also ist |S_{1}| ≤ κ. Es ergibt sich induktiv, daß |S_{i}| ≤ κ für alle i. Schließlich ist |A| ≤ κ · ℵ_{0} = κ. □

Ein gerichtete Familie (𝔄_{i})_{i∈I} von Strukturen heißt elementar, wenn 𝔄_{i} ≺ 𝔄_{j} für alle i ≤ j. Das folgende Lemma heißt Kettenlemma, weil es hauptsächlich auf elementare Ketten angewendet wird.

Satz 4.4 (Tarskis Kettenlemma) Die Vereinigung einer elementaren gerichteten Familie ist elementare Erweiterung aller ihrer Mitglieder.

Beweis: Sei 𝔄 = ⋃_{i∈I} (𝔄_{i})_{i∈I}. Wir zeigen durch Induktion über den Aufbau von ϕ(\overline{x}), daß für alle i und alle \overline{a} ∈ 𝔄_{i}

𝔄_{i} ⊧ ϕ(\overline{a}) ⟺ 𝔄 ⊧ ϕ(\overline{a}).

Wenn ϕ prim ist, ist nichts zu zeigen. Wenn ϕ eine Negation oder eine Konjunktion ist, folgt die Behauptung sofort per Induktion. Sei ϕ(\overline{x}) = ∃yψ(\overline{x}, y). ϕ(\overline{a}) gilt genau dann in 𝔄, wenn es ein b ∈ A mit 𝔄 ⊧ ψ(\overline{a}, b) gibt. Weil die Familie gerichtet ist, liegt b immer in A_{j} für ein genügend großes j ≥ i. Nach Induktionsvoraussetzung ist aber 𝔄 ⊧ ψ(\overline{a}, b) ⟺ 𝔄_{j} ⊧ ψ(\overline{a}, b). Also gilt ϕ(\overline{a}) in 𝔄 genau dann, wenn es in einem 𝔄_{j} (j ≥ i) gilt. Aus 𝔄_{i} ≺ 𝔄_{j} folgt jetzt die Behauptung. □

5 Der Kompaktheitssatz

Eine Theorie T heißt endlich erfüllbar, wenn jede endliche Teilmenge von T ein Modell hat.

Satz 5.1 (Kompaktheitssatz) Endlich erfüllbare Theorien sind konsistent.

Sei L eine Sprache und C eine Menge von neuen Konstanten. Wir nennen eine L(C)–Theorie T′ eine Henkin–Theorie, wenn es für alle L(C)–Formeln ϕ(x) eine Konstante c ∈ C gibt mit

∃xϕ(x) → ϕ(c) ∈ T′.

Die Elemente von C sind die Henkin–Konstanten von T′.

Eine L′–Theorie T′ ist „vollständig“, wenn sie endlich erfüllbar ist und ϕ ∈ T′ oder ¬ϕ ∈ T′ für alle L′–Aussagen ϕ. Eine konsistente Theorie ist genau dann „vollständig“, wenn sie vollständig und deduktiv abgeschlossen ist.

Der Kompaktheitssatz folgt aus den nächsten beiden Hilfssätzen.

Hilfssatz Jede endlich erfüllbare L–Theorie T läßt sich zu einer „vollständigen“ Henkin–Theorie T^{∗} erweitern.

Der Hilfssatz folgt sofort aus dem Kompaktheitssatz: Wähle ein Modell 𝔄 von T. Dann ist Th(𝔄_{A}) eine vollständige Henkin–Theorie mit A als der Menge der Henkin–Konstanten.

Beweis: Wir definieren eine aufsteigende Folge ∅ = C_{0} ⊂ C_{1} … von neuen Konstanten, indem wir jeder L(C_{i})–Formel ϕ(x) eine Konstante c_{ϕ(x)} zuordnen und

C_{i+1} = {c_{ϕ(x)} | ϕ(x) L(C_{i})–Formel}

setzen. C sei die Vereinigung der C_{i} und T^{H} die Menge aller Henkin–Axiome

∃xϕ(x) → ϕ(c_{ϕ(x)})

für L(C)–Formeln ϕ(x). Man sieht leicht, daß man jede L–Struktur zu einem Modell von T^{H} expandieren kann. Daraus folgt, daß T ∪ T^{H} eine endlich erfüllbare Henkin–Theorie ist.

Weil die Vereinigung einer Kette von endlich erfüllbaren Theorien wieder endlich erfüllbar ist, können wir Zorns Lemma anwenden und erhalten eine endliche erfüllbare L(C)–Theorie T^{∗}, die T ∪T^{H} enthält und maximal ist mit dieser Eigenschaft. Wie in 3.4 zeigen wir, daß T^{∗} „vollständig“ sein muß: Wenn weder ϕ noch ¬ϕ zu T^{∗} gehörten, wären weder T^{∗}∪{ϕ} noch T^{∗}∪{¬ϕ} endlich erfüllbar. T^{∗} hätte also eine endliche Teilmenge Δ, die weder mit ϕ noch mit ¬ϕ konsistent ist. Δ wäre also selbst inkonsistent und T^{∗} wäre nicht endlich erfüllbar. Damit ist der Hilfssatz bewiesen. □

Hilfssatz Jede „vollständige“ Henkin–Theorie T^{∗} hat ein bis auf Isomorphie eindeutig bestimmtes Modell aus Konstanten. Das ist ein Modell

(𝔄, a_{c})_{c∈C} ⊧ T^{∗},

für das zusätzlich A = {a_{c} | c ∈ C}.

Beweis:

Wir sagen, daß ϕ aus T^{∗} „folgt“, wenn ϕ aus einer endlichen Teilmenge von T^{∗} folgt. Weil T „vollständig“ ist, gehören alle Aussagen, die aus T^{∗} „folgen“ wieder zu T^{∗}.

Wir definieren für c, d ∈ C

c ≃ d ⟺ c =^{.} d ∈ T^{∗}

Weil c =^{.} c allgemeingültig ist, und weil d =^{.} c aus c =^{.} d folgt und c =^{.} e aus c =^{.} d und d =^{.} e folgt, ist ≃ eine Äquivalenzrelation. Wir bezeichnen mit a_{c} die Äquivalenzklasse von c und setzen

A = {a_{c} | c ∈ C}.

Wir machen A zu einer L–Struktur 𝔄 durch die Definitionen

(1)  R^{𝔄}(a_{c_{1}}, …, a_{c_{n}}) ⟺ R(c_{1}, …, c_{n}) ∈ T^{∗}
(2)  f^{𝔄}(a_{c_{1}}, …, a_{c_{n}}) = a_{c_{0}} ⟺ f(c_{1}, …, c_{n}) =^{.} c_{0} ∈ T^{∗}

für Relationszeichen R und Funktionszeichen (n ≥ 0–stellig) aus L.

Wir müssen die Wohldefiniertheit zeigen: Für (1) ist zu zeigen, daß

a_{c_{1}} = a_{d_{1}}, …, a_{c_{n}} = a_{d_{n}}, R(c_{1}, …, c_{n}) ∈ T^{∗}

zur Folge hat, daß R(d_{1}, …, d_{n}) ∈ T^{∗}. Das ist in der Tat der Fall, weil R(d_{1}, …, d_{n}) aus

c_{1} =^{.} d_{1}, …, c_{n} =^{.} d_{n}, R(c_{1}, …, c_{n})

folgt. Für (2) ist einerseits zu zeigen, daß a_{c_{0}} = a_{d_{0}}, wenn

a_{c_{1}} = a_{d_{1}}, …, a_{c_{n}} = a_{d_{n}}, f(c_{1}, …, c_{n}) =^{.} c_{0} ∈ T^{∗}, f(d_{1}, …, d_{n}) =^{.} d_{0} ∈ T^{∗}.

Das geht so wie eben. Andererseits ist zu zeigen, daß es für alle c_{1}, …, c_{n} ein c_{0} mit f(c_{1}, …, c_{n}) =^{.} c_{0} ∈ T^{∗} gibt. Weil T^{∗} eine Henkin–Theorie ist, gibt es ein c_{0} mit

∃xf(c_{1}, …, c_{n}) =^{.} x → f(c_{1}, …, c_{n}) =^{.} c_{0} ∈ T^{∗}.

Weil aber die allgemeingültige Aussage ∃xf(c_{1}, …, c_{n}) =^{.} x zu T^{∗} gehört, gehört auch f(c_{1}, …, c_{n}) =^{.} c_{0} zu T^{∗}. Damit ist die Wohldefiniertheit gezeigt.

Sei 𝔄^{∗} die L(C)–Struktur (𝔄, a_{c})_{c∈C}. Wir zeigen durch Induktion über die Komplexität^{2} von ϕ, daß

𝔄^{∗} ⊧ ϕ ⟺ ϕ ∈ T^{∗}

für alle L(C)–Aussagen ϕ. Es gibt vier Fälle: a) ϕ ist prim.

2Die Anzahl der logischen Zeichen + die Zahl der Funktionszeichen und Konstanten aus L

Wenn ϕ die Gestalt c =^{.} d oder R(c_{1}, …, c_{n}) hat, gilt die Behauptung, weil wir 𝔄^{∗} gerade so konstruiert haben. Andere Primaussagen enthalten Funktionszeichen f (bzw. Konstanten) aus L und lassen sich schreiben als

ϕ = ψ(f(c_{1}, …, c_{n}))

für eine L(C)–Formel ψ(x_{1}, …, x_{n}). Wir wählen uns ein c_{0} mit f(c_{1}, …, c_{n}) =^{.} c_{0} ∈ T^{∗}. Nach Konstruktion gilt f(c_{1}, …, c_{n}) =^{.} c_{0} in 𝔄^{∗}. Es folgt 𝔄^{∗} ⊧ ϕ ⟺ 𝔄^{∗} ⊧ ψ(c_{0}) und ϕ ∈ T^{∗} ⟺ ψ(c_{0}) ∈ T^{∗}. Also bleibt zu zeigen, daß 𝔄^{∗} ⊧ ψ(c_{0}) ⟺ ψ(c_{0}) ∈ T^{∗}. Das gilt aber nach Induktionsvoraussetzung.

b) ϕ = ¬ψ.

Weil T^{∗} „vollständig“ ist, ist ϕ ∈ T^{∗} ⟺ ψ ∉ T^{∗} und mit der Induktionsannahme folgt

𝔄^{∗} ⊧ ϕ ⟺ 𝔄^{∗} |̸= ψ ⟺ ψ ∉ T^{∗} ⟺ ϕ ∈ T^{∗}.

c) ϕ = (ψ_{1} ∧ψ_{2}). Weil T^{∗} unter „Folgerungen“ abgeschlossen ist, gehört ϕ genau dann zu T^{∗}, wenn ψ_{1} und ψ_{2} zu T^{∗} gehören. Es folgt

𝔄^{∗} ⊧ ϕ ⟺ 𝔄^{∗} ⊧ ψ_{i} (i = 1, 2) ⟺ ψ_{i} ∈ T^{∗} (i = 1, 2) ⟺ ϕ ∈ T^{∗}.

d) ϕ = ∃xψ(x) Es ist

𝔄^{∗} ⊧ ϕ ⇔ 𝔄^{∗} ⊧ ψ(c) für ein c ∈ C ⇔ ψ(c) ∈ T^{∗} für ein c ∈ C ⇔ ϕ ∈ T^{∗}.

Die zweite Äquivalenz ist die Induktionsvoraussetzung, die dritte sieht man so ein: Wenn ϕ ∈ T^{∗}, wählen wir ein c mit ϕ → ψ(c) ∈ T^{∗}. Wenn dann ϕ ∈ T^{∗}, muß auch ψ(c) zu T^{∗} gehören.

□

Folgerung 5.2 T ⊢ ϕ genau dann wenn, Δ ⊢ ϕ für eine endliche Teilmenge Δ von T.

Beweis: ϕ folgt genau dann aus T, wenn T ∪ {¬ϕ} inkonsistent ist. □

Definition Sei 𝔄 eine L–Struktur und B eine Teilmenge von A. Eine Menge Σ(x) von L(B)–Formeln (mit höchstens der freien Variable x) heißt endlich erfüllbar in 𝔄, wenn für alle ϕ_{1}(x) … ϕ_{n}(x) aus Σ(x)

𝔄 ⊧ ∃x (ϕ_{1}(x) ∧ … ∧ ϕ_{n}(x)) .

a ∈ A realisiert Σ(x), wenn a alle Formeln aus Σ(x) erfüllt. Man schreibt auch

𝔄 ⊧ Σ(a)

𝔄 läßt Σ(x) aus, wenn Σ(x) nicht in 𝔄 realisiert wird.

Lemma 5.3 Wenn Σ(x) endlich erfüllbar in 𝔄 ist, wird Σ(x) in einer geeigneten elementaren Erweiterung von 𝔄 realisiert.

Beweis: Sei c eine neue Konstante. Σ(x) ist genau dann endlich erfüllbar in 𝔄, wenn

T^{∗} = Th(𝔄_{A}) ∪ Σ(c)

endlich erfüllbar ist. Die Modelle von T^{∗} sind gerade elementare Erweiterungen von 𝔄 mit einem ausgezeichneten Element, das Σ(x) realisiert. □

Definition Eine Menge p(x) von L(B)–Formeln ist ein Typ über B, wenn p(x) maximal endlich erfüllbar ist. Wir bezeichnen mit

S(B) = S_{1}^{𝔄}(B)

die Menge der Typen über B. Maximal endlich erfüllbare Mengen von Formeln in den Variablen x_{1}, …, x_{n} heißen n–Typen. S_{n}(B) = S_{n}^{𝔄}(B) ist die Menge der n–Typen über B.

Jedes Element a bestimmt einen Typ

tp(a/B) = tp^{𝔄}(a/B) = {ϕ(x) | 𝔄 ⊧ ϕ(a), ϕ eine L(B)–Formel}

a realisiert den Typ p genau dann, wenn p = tp(a/B).

Folgerung 5.4 Jede Struktur 𝔄 hat eine elementare Erweiterung 𝔅, in der alle Typen über A realisiert sind.

Beweis: Wir wählen für jedes p ∈ S(A) eine neue Konstante c_{p}. Gesucht ist ein Modell von

Th(𝔄_{A}) ∪ ⋃_{p∈S(A)} p(c_{p}).

Man sieht leicht, daß diese Theorie endlich erfüllbar ist, weil die p endlich erfüllbar sind.

Ich gebe einen zweiten Beweis der nur von 5.3 Gebrauch macht: Sei (p_{α})_{α<λ} eine Aufzählung von S(A), dabei sei λ eine Ordinalzahl (siehe A.20). Wir konstruieren mit A.20.1 eine elementare Kette

𝔄 = 𝔄_{0} ≺ 𝔄_{1} ≺ … 𝔄_{β} … (β ≤ λ)

in der p_{α} in 𝔄_{α+1} realisiert ist.

Nehmen wir an, daß die elementare Kette (𝔄_{α′})_{α′<β} schon konstruiert sind. Wenn β eine Limeszahl ist, nehmen wir für 𝔄_{β} die Vereinigung der Kette^{3}. Die verlängerte Kette (𝔄_{α′})_{α′≤β} ist elementar wegen 4.4. Wenn β = α + 1, beachten wir, daß p_{α} auch in 𝔄_{α} endlich erfüllbar ist. Wir können also p_{α} in einem 𝔄_{β} ≻ 𝔄_{α} realisieren. 𝔅 = 𝔄_{λ} leistet das Gewünschte. □

3 Man nennt eine nach Ordinalzahlen indizierte elementare Kette (𝔄_{α}) stetig, wenn 𝔄_{β} = ⋃_{α<β} 𝔄_{α} für alle Limeszahlen β.

6 Der Satz von Löwenheim–Skolem

Satz 6.1 (Löwenheim–Skolem) Sei 𝔅 eine L–Struktur und S eine Teilmenge von B. κ sei eine Kardinalzahl.

1. Wenn

max{|L|, |S|, ℵ_{0}} ≤ κ ≤ |𝔅|,

gibt es eine elementare Unterstruktur 𝔄 ≺ 𝔅 der Mächtigkeit κ, die S enthält.

2. Wenn 𝔅 unendlich ist und

max{|L|, |𝔅|} ≤ κ,

hat 𝔅 eine elementare Erweiterung der Mächtigkeit κ.

Beweis: 1: Wähle ein Menge S ⊂ S′ ⊂ B der Mächtigkeit κ und wende 4.3 an.

2: Zuerst verschaffen wir uns eine elementare Erweiterung 𝔅′, die mindestens die Mächtigkeit κ hat. Dazu wählen wir uns eine Menge C von neuen Konstanten, die die Mächtigkeit κ hat. Die Theorie

Th(𝔅_{B}) ∪ {¬c =^{.} d | c, d ∈ C, c ≠ d}

ist endlich erfüllbar, weil 𝔅 unendlich ist^{4}. Ein Modell (𝔅′_{B}, b_{c})_{c∈C} liefert eine elementare Erweiterung von 𝔄 mit κ–vielen verschiedenen Elementen (b_{c}). Schließlich wenden wir auf 𝔅′ und S = B den ersten Teil des Satzes an. □

Folgerung 6.2 Eine Theorie, die ein unendliches Modell hat, hat Modelle in jeder Mächtigkeit κ ≥ max(|L|, ℵ_{0}). □

Definition^{5} κ sei eine unendliche Kardinalzahl. Eine Theorie T heißt κ–kategorisch, wenn alle Modelle von T der Mächtigkeit κ isomorph sind.

Satz 6.3 (Vaughts Test) κ–kategorische Theorien T sind vollständig, wenn man noch voraussetzt daß

a) T konsistent ist,

b) T keine endlichen Modelle hat,

c) und |L| ≤ κ.

4 Man findet Modelle durch geeignete Interpretation der neuen Konstanten in 𝔅

5 Vorläufige Definition (siehe S. 28)

Beweis: Wir müssen zeigen, daß alle Modelle 𝔄 und 𝔅 von T elementar äquivalent sind. Weil 𝔄 und 𝔅 unendlich sind, haben Th(𝔄) und Th(𝔅) Modelle 𝔄′ und 𝔅′ der Mächtigkeit κ. Weil 𝔄′ und 𝔅′ isomorph sind, folgt

𝔄 ≡ 𝔄′ ≡ 𝔅′ ≡ 𝔅.
□

Wir nehmen 6.3 zum Anlaß, unsere Definition zu verschärfen. Eine κ–kategorische Theorie soll ab jetzt immer vollständig sein.

Quantorenelimination

7 Erhaltungssätze

Wir halten eine Sprache L fest.

Lemma 7.1 (Trennungslemma) T_{1} und T_{2} seien zwei Theorien. H sei eine Menge von Aussagen, die abgeschlossen ist unter ∧ und ∨ und ⊤ und ⊥ enthält, die wahre und die falsche Aussage. Dann sind äquivalent:

a) Es gibt ein ϕ ∈ H mit

T_{1} ⊢ ϕ und T_{2} ⊢ ¬ϕ.

b) Für alle Modelle 𝔄_{1} von T_{1} und 𝔄_{2} von T_{2} gibt es ein ϕ ∈ H mit

𝔄_{1} ⊧ ϕ und 𝔄_{2} ⊧ ¬ϕ.

Wir sagen in a), daß ϕ T_{1} und T_{2} trennt. Und in b), daß ϕ 𝔄_{1} und 𝔄_{2} trennt. Beweis:

a) ⇒ b): Wenn ϕ T_{1} und T_{2} trennt, trennt ϕ auch alle Modelle von T_{1} und T_{2}.

b) ⇒ a): Sei 𝔄_{1} ein Modell von T_{1} und H_{𝔄_{1}} die Menge aller Aussagen aus H, die in 𝔄_{1} gelten. Wegen b) haben H_{𝔄_{1}} und T_{2} kein gemeinsames Modell. Der Kompaktheitssatz hat zur Folge, daß schon eine endliche Konjunktion ϕ_{𝔄_{1}} von Aussagen aus H_{𝔄_{1}} mit T_{2} unverträglich ist. Weil jedes 𝔄_{1} ein Modell von ϕ_{𝔄_{1}} ist, ist

T_{1} ∪ {¬ϕ_{𝔄_{1}} | 𝔄_{1} ⊧ T_{1}}

inkonsistent. Daraus folgt mit dem Kompaktheitssatz, daß T_{1} schon eine endliche Disjunktion ϕ der ϕ_{𝔄_{1}} impliziert. Dieses ϕ trennt T_{1} und T_{2}. □

Satz 7.2 T_{1} und T_{2} seien Theorien. Dann sind äquivalent: a) Es gibt eine universelle Aussage, die T_{1} und T_{2} trennt.

b) Wenn 𝔄_{1} ein Modell von T_{1} ist und 𝔄_{2} ein Modell von T_{2}, kann 𝔄_{2} keine Unterstruktur von 𝔄_{1} sein.

Beweis:

a) ⇒ b): Sei ϕ eine universelle Aussage, die T_{1} und T_{2} trennt. Sei 𝔄_{1} ein Modell von T_{1} und 𝔄_{2} eine Unterstruktur. Weil 𝔄_{1} ein Modell von ϕ ist, ist auch 𝔄_{2} ein Modell von ϕ (2.10). 𝔄_{2} kann daher kein Modell von T_{2} sein.

b) ⇒ a): Wir wenden das Trennungslemma an. Seien 𝔄_{1} und 𝔄_{2} Modelle von T_{1} und T_{2}, die man nicht durch eine universelle Aussage trennen kann. Das kann man als

𝔄_{2} ⇒_{∃} 𝔄_{1}

notieren. Aus dem nächsten Lemma (7.3, mit Δ = Menge der Existenzformeln) folgt, daß 𝔄_{2} eine Oberstruktur 𝔄′_{1} hat, die elementar äquivalent zu 𝔄_{1} ist. 𝔄′_{1} ist wieder ein Modell von T_{1}. Das widerspricht b). □

Sei Δ eine Menge von Formeln. Für eine Abbildung f : A → B bedeutet

f : 𝔄 →_{Δ} 𝔅,

daß f alle Formeln aus Δ präserviert.

Lemma 7.3 Sei T eine Theorie, 𝔄 eine Struktur und Δ eine Menge von Formeln, die unter Existenzquantifizierung, Konjunktion und Variablensubstitution^{1} abgeschlossen ist. Dann sind äquivalent:

a) Alle Aussagen ϕ ∈ Δ, die in 𝔄 gelten, sind konsistent mit T.

b) Es gibt ein Modell 𝔅 ⊧ T und eine Abbildung f : 𝔄 →_{Δ} 𝔅.

Wenn Δ eine Menge von Formeln ist, bedeutet

𝔄 ⇒_{Δ} 𝔅,

daß alle Aussagen aus Δ, die in 𝔄 gelten, auch in 𝔅 gelten. Wenn man das Lemma auf T = Th(𝔅) anwendet, sieht man, daß genau dann 𝔄 ⇒_{Δ} 𝔅, wenn es ein

f : 𝔄 →_{Δ} 𝔅′ ≡ 𝔅

gibt.

Beweis:

b) ⇒ a): Sei f : 𝔄 →_{Δ} 𝔅 ⊧ T gegeben. Wenn ϕ ∈ Δ in 𝔄 gilt, gilt ϕ auch in 𝔅 und ist folglich mit T konsistent. a) ⇒ b): Wir betrachten Th_{Δ}(𝔄_{A}), die Menge aller Aussagen δ(\overline{a}), (δ(\overline{x}) ∈ Δ), die in 𝔄 gelten. Die Modelle (𝔅, f(a)_{a∈A}) dieser Theorie entsprechen gerade den f : 𝔄 →_{Δ} 𝔅. Wir suchen also ein Modell von T ∪ Th_{Δ}(𝔄_{A}). Dazu zeigen wir die endliche Erfüllbarkeit. Wenn T ∪ Th_{Δ}(𝔄_{A}) nicht endlich erfüllbar wäre, gäbe es (weil Δ unter Konjunktionen und Variablensubstitutionen abgeschlossen ist) ein δ(\overline{a}) ∈ Th_{Δ}(𝔄_{A}) mit T ⊢ ¬δ(\overline{a}). Wegen 3.2 ist T ⊢ ∀\overline{x} ¬δ(\overline{x}). ϕ = ∃\overline{x} δ(\overline{x}) ist eine Δ–Aussage, die in 𝔄 gilt, aber inkonsistent mit T ist. □

1Freie Variable dürfen umbenannt werden.

Folgerung 7.4 T sei ein Theorie.

1. Sei ϕ(x_{1}, …, x_{n}) eine Formel. Dann sind äquivalent:

a) Es gibt eine universelle Formel, die modulo T zu ϕ(x_{1}, …, x_{n}) äquivalent ist.

b) 𝔄 ⊂ 𝔅 seien Modelle von T und a_{1}, …, a_{n} ∈ A. Dann gilt ϕ(a_{1}, …, a_{n}) in 𝔄, wenn ϕ(a_{1}, …, a_{n}) in 𝔅 gilt.

2. Wir nennen eine Theorie aus universellen Aussagen universell. T ist genau dann äquivalent zu einer universellen Theorie, wenn mit einem Modell 𝔅 von T auch alle Unterstrukturen von 𝔅 Modell von T sind.

Beweis: 1): Nehmen wir an, daß b) gilt. Wir erweitern L um ein n–Tupel \overline{c} von neuen Konstanten c_{1}, …, c_{n} und betrachten die Theorien

T_{1} = T ∪ \{ϕ(\overline{c})\} und T_{2} = T ∪ \{¬ϕ(\overline{c})\}.

b) besagt gerade, daß Unterstrukturen von Modellen von T_{1} keine Modelle von T_{2} sein können. Nach 7.2 können wir T_{1} und T_{2} durch eine universelle L(\overline{c})– Aussage ψ(\overline{c}) trennen. Aus T_{1} ⊢ ψ(\overline{c}) folgt

T ⊢ ∀\overline{x} (ϕ(\overline{x}) → ψ(\overline{x}))

und aus T_{2} ⊢ ¬ψ(\overline{c}) folgt

T ⊢ ∀\overline{x} (¬ϕ(\overline{x}) → ¬ψ(\overline{x})).

2): Unterstrukturen von Modellen einer universellen Theorie sind natürlich wieder Modelle dieser Theorie. Jetzt nehmen wir an, daß T diese Eigenschaft hat. Sei ϕ ein Axiom von T. Wenn 𝔄 eine Unterstruktur von 𝔅, kann nicht 𝔅 ein Modell von T und gleichzeitig 𝔄 ein Modell von ¬ϕ sein. Nach 7.2 gibt es eine universelle Aussage ψ mit T ⊢ ψ und ¬ϕ ⊢ ¬ψ. Alle Axiome von T folgen also aus

T_{∀} = {ψ | T ⊢ ψ, ψ universell}.
□

Definition ∀∃–Formeln haben die Form

∀x_{1} … x_{n}ψ

für existentielle Formeln ψ.

Definition Eine Theorie T ist induktiv, wenn die Vereinigung jeder gerichteten Familie von Modellen von T wieder ein Modell von T ist.

Satz 7.5 T_{1} und T_{2} seien Theorien. Dann sind äquivalent:

a) Es gibt eine ∀∃–Aussage, die T_{1} und T_{2} trennt.

b) Kein Modell von T_{2} ist Vereinigung einer Kette (oder einer gerichteten Familie) von Modellen von T_{1}.

Beweis:

a) ⇒ b): Sei ϕ eine ∀∃–Aussage, die T_{1} und T_{2} trennt, (𝔄_{i})_{i∈I} ein gerichtete Familie von Modellen von T_{1} und 𝔅 die Vereinigung der 𝔄_{i}. Weil die 𝔄_{i} Modelle von ϕ sind, ist auch 𝔅 ein Modell von ϕ. Um das einzusehen, schreiben wir

ϕ = ∀\overline{x} ψ(\overline{x})

für existentielles ψ. Wenn \overline{a} ∈ B, gibt es ein A_{i}, in dem die \overline{a} enthalten sind. Weil ϕ in 𝔄_{i} gilt, gilt ψ(\overline{a}) in 𝔄_{i}. ψ(\overline{a}) ist aber eine Existenzaussage und gilt somit auch in 𝔅. Weil 𝔅 ⊧ ϕ, kann 𝔅 kein Modell von T_{2} sein.

¬a) ⇒ ¬b): Wenn a) nicht gilt, gibt es nach dem Trennungslemma Modelle 𝔄 und 𝔅^{0} von T_{1} und T_{2}, die man nicht durch eine ∀∃–Aussage trennen kann, also^{2}

𝔅^{0} ⇒_{∃∀} 𝔄.

Nach 7.3 gibt es ein

f : 𝔅^{0} →_{∀} 𝔄^{0}

mit 𝔄^{0} ≡ 𝔄. Wir können annehmen, daß 𝔅^{0} ⊂ 𝔄^{0} und f die Inklusionsabbildung ist. Dann ist

𝔄_{B}^{0} ⇒_{∃} 𝔅_{B}^{0}.

Wir wenden nochmal 7.3 an und erhalten eine Oberstruktur 𝔅_{B}^{1} von 𝔄_{B}^{0} mit 𝔅_{B}^{1} ≡ 𝔅_{B}^{0}, das heißt 𝔅^{0} ≺ 𝔅^{1}.

𝔅^{0} ⊂ 𝔄^{0} ⊂ 𝔅^{1} ≺

Jetzt wenden wir das gleiche Verfahren auf 𝔄 und 𝔅^{1} an und erhalten zwei Oberstrukturen 𝔄^{1} ⊂ 𝔅^{2} mit 𝔄^{1} ≡ 𝔄 und 𝔅^{1} ≺ 𝔅^{2}. Schließlich ergibt sich eine unendliche Kette

2 ∃∀–Formeln sind ∃–quantifizierte universelle Formeln, und äquivalent zu negierten ∀∃– Formeln.

𝔅^{0} ⊂ 𝔄^{0} ⊂ 𝔅^{1} ≺  ⊂ 𝔄^{1} ⊂ 𝔅^{2} ≺  ⊂ … ≺

mit 𝔄^{i} ≡ 𝔄 und 𝔅^{i} ≺ 𝔅^{i+1}. Sei nun 𝔅 die Vereinigung der 𝔄^{i}. Weil 𝔅 auch die Vereinigung der elementaren Kette (𝔅^{i}) ist, ist 𝔅 elementare Erweiterung von 𝔅^{0} und damit ein Modell von T_{2}. Die 𝔄^{i} sind aber Modelle von T_{1} und wir haben einen Gegenbeispiel zu b). □

Folgerung 7.6 T sei ein Theorie.

1. Sei ϕ eine Aussage. Dann sind äquivalent:

a) Es gibt eine ∀∃–Aussage, die modulo T zu ϕ äquivalent ist.

b) Seien

𝔄^{0} ⊂ 𝔄^{1} ⊂ …

Modelle von T und ihre Vereinigung 𝔅 ebenfalls ein Modell von T. Dann gilt ϕ in 𝔅, wenn ϕ in allen 𝔄^{i} gilt.

2. T ist genau dann induktiv, wenn T sich mit ∀∃–Aussagen axiomatisieren läßt.

Beweis: 1): Wir haben in 7.5 bewiesen, daß sich ∀∃–Formeln auf die Vereinigung von Ketten vererben. Also gilt a) ⇒ b). Nehmen wir umgekehrt an, daß b) gilt. Wir betrachten die Theorien

T_{1} = T ∪ {ϕ} und T_{2} = T ∪ {¬ϕ}.

b) besagt gerade, daß die Vereinigung einer Kette von Modellen von T_{1} kein Modell von T_{2} sein kann. Nach 7.5 können wir T_{1} und T_{2} durch eine ∀∃–Aussage ψ trennen. Aus T_{1} ⊢ ψ folgt T ⊢ ϕ → ψ und aus T_{2} ⊢ ¬ψ folgt T ⊢ ¬ϕ → ¬ψ.

2): Daß ∀∃–axiomatisierte Theorien induktiv sind, ist klar. Sei umgekehrt T induktiv und ϕ ein Axiom von T. Wenn 𝔅 Vereinigung von Modellen von T ist, kann 𝔅 kein Modell von ¬ϕ sein. Nach 7.5 gibt es eine ∀∃ Aussage ψ mit T ⊢ ψ und ¬ϕ ⊢ ¬ψ. Alle Axiome von T folgen also aus

T_{∀∃} = {ψ | T ⊢ ψ, ψ ∀∃–Formel}.
□

8 Quantorenelimination

Definition Eine Theorie T hat Quantorenelimination , wenn es zu jeder L– Formel ϕ(x_{1}, …, x_{n}) eine quantorenfreie Formel ρ(x_{1}, …, x_{n}) gibt mit

T ⊢ ∀x_{1}, …, x_{n} ( ϕ(x_{1}, …, x_{n}) ↔ ρ(x_{1}, …, x_{n}) ).

Für n = 0 besagt das, daß modulo T jede Aussage zu einer quantorenfreien Aussage äquivalent ist. Wenn L keine Konstanten enthält, sind ⊤ und ⊥ die einzigen quantorenfreien Aussagen. T ist dann entweder inkonsistent oder vollständig.

Definition Eine einfache Existenzformel hat die Gestalt

ϕ(\overline{x}) = ∃y ρ(\overline{x}, y)

für eine quantorenfreie Formel ρ. Wenn ρ eine Konjunktion von basic Formeln ist, nennt man ϕ primitiv.

Lemma 8.1 T hat genau dann Quantorenelimination, wenn jede primitive Existenzformel modulo T zu einer quantorenfreien Formel äquivalent ist.

Beweis: Weil jede einfache Existenzformel ∃y ⋁_{i<n} ρ_{i} äquivalent ist zu einer Disjunktion ⋁_{i<n}(∃y ρ_{i}) von primitiven Existenzformeln (vgl. 2.8), können wir annehmen, daß jede einfache Existenzformel modulo T äquivalent zu einer quantorenfreien Formel ist. Jetzt können wir Quantoren in beliebigen Formeln (in pränexer Normalform)

Q_{1}x_{1} … Q_{n}x_{n}ρ

eliminieren. Wenn Q_{n} = ∃, wählen wir eine quantorenfreie Formel ρ_{0}, die modulo T zu ∃x_{n}ρ äquivalent ist. Dann fahren wir mit der Formel Q_{1}x_{1} … Q_{n−1}x_{n−1}ρ_{0} fort. Sonst finden wir ein quantorenfreies ρ_{1}, das modulo T mit ∃x_{n}¬ρ äquivalent ist und fahren mit Q_{1}x_{1} … Q_{n−1}x_{n−1}¬ρ_{1} fort. □

Der folgende Satz ist das modelltheoretische Kriterium für Quantorenelimination.

Satz 8.2 Für eine Theorie T sind äquivalent:

a) T hat Quantorenelimination.

b) Für alle Modelle 𝔐^{1} und 𝔐^{2} von T mit gemeinsamer Unterstruktur 𝔄

gilt

𝔐_{A}^{1} ≡ 𝔐_{A}^{2}.

c) Für alle Modelle 𝔐^{1} und 𝔐^{2} von T mit gemeinsamer endlich erzeugter Unterstruktur 𝔄 = ⟨a_{1}, …, a_{n}⟩ und alle primitiven Existenzformeln ϕ(x_{1}, …, x_{n}) gilt

𝔐^{1} ⊧ ϕ(a_{1}, …, a_{n}) ⇒ 𝔐^{2} ⊧ ϕ(a_{1}, …, a_{n}).

Wenn L keine Konstanten enthält, ist für 𝔄 ausnahmsweise die leere Struktur zugelassen.

Beweis:

a) ⇒ b): Sei ϕ(\overline{a}) eine L(A)–Aussage, die in 𝔐^{1} gilt. Sei ρ(\overline{x}) quantorenfrei und modulo T äquivalent zu ϕ(\overline{x}). Dann ist

𝔐^{1} ⊧ ϕ(\overline{a}) ⇒ 𝔐^{1} ⊧ ρ(\overline{a})
⇒ 𝔄 ⊧ ρ(\overline{a}) ⇒
𝔐^{2} ⊧ ρ(\overline{a}) ⇒ 𝔐^{2} ⊧ ϕ(\overline{a}).

b) ⇒ c): Klar.

c) ⇒ a): Sei ϕ(\overline{x}) eine primitive Existenzformel. Um zu zeigen, daß ϕ(\overline{x}) modulo T zu einer quantorenfreien ρ(\overline{x}) Formel äquivalent ist, erweitern wir L um ein n– Tupel \overline{c} von neuen Konstanten c_{1}, …, c_{n}. Wir müssen zeigen, daß wir T ∪\{ϕ(\overline{c})\} und T ∪ \{¬ϕ(\overline{c})\} mit einer quantorenfreien Aussage ρ(\overline{c}) trennen können. Wir wenden das Trennungslemma an. Seien 𝔐^{1} und 𝔐^{2} zwei Modelle von T mit zwei ausgezeichneten n–Tupeln \overline{a}^{1} und \overline{a}^{2}. Nehmen wir an, daß in (𝔐^{1}, \overline{a}^{1}) und (𝔐^{2}, \overline{a}^{2}) die gleichen quantorenfreien L(\overline{c})–Aussagen gelten. Wir haben zu zeigen, daß

𝔐^{1} ⊧ ϕ(\overline{a}^{1}) ⇒ 𝔐^{2} ⊧ ϕ(\overline{a}^{2}).

Seien jeweils 𝔄^{i} = ⟨\overline{a}^{i}⟩^{𝔐^{i}} die von den \overline{a}^{i} erzeugten Unterstrukturen. Wenn wir zeigen können, daß es einen Isomorphismus

h : 𝔄^{1} → 𝔄^{2}

gibt, der \overline{a}^{1} auf \overline{a}^{2} abbildet, können wir (nach einer Anwendung von 1.7) annehmen, daß 𝔄^{1} = 𝔄^{2} = 𝔄 und \overline{a}^{1} = \overline{a}^{2} = \overline{a}. c) liefert dann das Gewünschte. Jedes Element von 𝔄^{1} hat die Form t^{𝔐^{1}}[\overline{a}^{1}] für einen L–Term t(\overline{x}), (2.4). Für den gesuchten Isomorphismus muß gelten:

h(t^{𝔐^{1}}[\overline{a}^{1}]) = t^{𝔐^{2}}[\overline{a}^{2}].

Wir verwenden also diese Gleichung als Definition. h ist sicherlich surjektiv. Zu zeigen ist aber noch die Wohldefiniertheit und Injektivität: Sei

s^{𝔐^{1}}[\overline{a}^{1}] = t^{𝔐^{1}}[\overline{a}^{1}].

Dann gilt s(\overline{c}) =^{.} t(\overline{c}) in (𝔐^{1}, \overline{a}^{1}), und daher nach Voraussetzung auch in (𝔐^{2}, \overline{a}^{2}). Das bedeutet dann, daß

s^{𝔐^{2}}[\overline{a}^{2}] = t^{𝔐^{2}}[\overline{a}^{2}].

Wenn man in dieser Überlegung 𝔐^{1} und 𝔐^{2} vertauscht, erhält man die Injektivität von h.

Schließlich ist noch zu zeigen, daß h mit der Interpretation der Relations– und Funktionszeichen vertauscht. Dazu zeigen wir, daß h die Gültigkeit von quantorenfreien Formeln ρ(x_{1}, …, x_{m}) erhält: Daß

𝔐^{1} ⊧ ρ[t_{1}^{𝔐^{1}}[\overline{a}^{1}], …, t_{m}^{𝔐^{1}}[\overline{a}^{1}]],

ist gleichbedeutend mit (𝔐^{1}, \overline{a}^{1}) ⊧ ρ(t_{1}(\overline{c}), …, t_{m}(\overline{c})) und also auch mit (𝔐^{2}, \overline{a}^{2}) ⊧ ρ(t_{1}(\overline{c}), …, t_{m}(\overline{c})), was wiederum äquivalent ist mit

𝔐^{2} ⊧ ρ[t_{1}^{𝔐^{2}}[\overline{a}^{2}], …, t_{m}^{𝔐^{2}}[\overline{a}^{2}]].
□

Definition T ist modellvollständig, wenn für alle Modelle 𝔐^{1} und 𝔐^{2} von T

𝔐^{1} ⊂ 𝔐^{2} ⇒ 𝔐^{1} ≺ 𝔐^{2}.

Es ist klar, daß Theorien mit Quantorenelimination modellvollständig sind^{3}. Modellvollständige Theorien sind induktiv. Das folgt aus 4.4.

Lemma 8.3 (Robinsons Test) Sei T ein Theorie. Dann sind äquivalent:

a) T ist modellvollständig.

b) Für alle Modelle 𝔐^{1} ⊂ 𝔐^{2} und jede Existenzaussage ϕ aus L(M^{1}) ist

𝔐^{2} ⊧ ϕ ⇒ 𝔐^{1} ⊧ ϕ.

c) Modulo T ist jede Formel äquivalent zu einer Allformel.

Beweis: a)⇒b) ist trivial. a)⇔c) folgt aus 7.4.1. Aus b) folgt, daß jede Existenzformel modulo T zu einer Allformel äquivalent ist. Wie im Beweis von 8.1 folgt daraus c). □

Wenn 𝔐^{1} ⊂ 𝔐^{2}, die Eigenschaft b) haben, nennt man 𝔐^{1} existentiell abgeschlossen in 𝔐^{2}. Man schreibt dafür

𝔐^{1} ≺_{1} 𝔐^{2}.

Definition Sei T eine Theorie. Eine Theorie T^{∗} heißt Modellbegleiter von T, wenn die folgenden drei Bedingungen erfüllt sind.

a) Jedes Modell von T läßt sich zu einem Modell von T^{∗} erweitern.

b) Jedes Modell von T^{∗} läßt sich zu einem Modell von T erweitern. c) T^{∗} ist modellvollständig.

3 Verwende 8.2.b) für 𝔄 = 𝔐^{1}.

Satz 8.4 Eine Theorie T hat, bis auf Äquivalenz, höchstens einen Modellbegleiter T^{∗}.

Beweis: Wenn T^{+} ein weiterer Modellbegleiter von T ist, läßt sich jedes Modell von T^{+} in ein Modell von T^{∗} einbetten und umgekehrt. Sei 𝔄_{0} ein Modell von T^{+}. 𝔄_{0} ist in ein Modell 𝔅_{0} von T^{∗} einbettbar. 𝔅_{0} ist wiederum enthalten in einem Modell 𝔄_{1} von T^{+}. Auf diese Weise finden wir zwei elementare Ketten (𝔄_{i}) und (𝔅_{i}), die eine gemeinsame Vereinigung ℭ haben. Aus 𝔄_{0} ≺ ℭ und 𝔅_{0} ≺ ℭ folgt 𝔄_{0} ≡ 𝔅_{0}. Also ist 𝔄_{0} ein Modell von T^{∗}. Wenn man die Rollen von T^{∗} und T^{+} vertauscht, sieht man, daß auch jedes Modell von T^{∗} ein Modell von T^{+} ist. □

Exkurs: Existentiell abgeschlossene Modelle und die Kaiserhülle

Sei T eine L–Theorie. Aus 7.3 folgt, daß die Modelle von T_{∀} genau die L–Strukturen sind, die sich in Modelle von T einbetten lassen. Die Bedingungen a) und b) in der Definition des Modellbegleiters lassen daher auch ausdrücken durch

T_{∀} = T _{∀}^{∗}.

Der Modellbegleiter einer Theorie T hängt also nur von T_{∀} ab.

Definition Eine L–Struktur 𝔄 heißt T –existentiell abgeschlossen (oder kurz: T -e.a), wenn

a) 𝔄 sich in ein Modell von T einbetten läßt,

b) 𝔄 existentiell abgeschlossen in jeder Oberstruktur ist, die ein Modell von T ist.

Eine Struktur ist genau dann T –e.a, wenn sie T_{∀}–e.a ist. Denn jede Erweiterung 𝔅 von 𝔄, die ein Modell von T_{∀} ist, läßt sich in ein Modell 𝔐 von T einbetten. Wenn 𝔄 existentiell abgeschlossen in 𝔐 ist, ist 𝔄 auch existentiell abgeschlossen in 𝔅.

Lemma 8.5 Sei T eine Theorie. Dann läßt sich jedes Modell von T in eine T –e.a Struktur einbetten.

Beweis: Sei 𝔄 ein Modell von T_{∀}. Wir wählen eine Aufzählung (ϕ_{α})_{α<κ} aller existentiellen L(A)–Aussagen und konstruieren eine aufsteigende Kette (𝔄_{α})_{α≤κ} von Modellen von T_{∀}. Wir beginnen mit 𝔄_{0} = 𝔄. Sei 𝔄_{α} konstruiert. Wenn ϕ_{α} in einer Erweiterung von 𝔄_{α} gilt, die ein Modell von T ist, wählen wir für 𝔄_{α+1} ein solches Modell. Sonst setzen wir 𝔄_{α+1} = 𝔄_{α}. Für Limeszahlen λ nehmen wir für 𝔄_{λ} die Vereinigung aller 𝔄_{α}, (α < λ) (die wieder ein Modell von T_{∀} ist). Die Struktur 𝔄^{1} = 𝔄_{κ} hat die folgende Eigenschaft: Jede existentielle L(A)–Aussage, die in einer Erweiterung von 𝔄^{1}, die ein Modell von T ist, gilt, gilt in 𝔄^{1}. Wir konstruieren in der gleichen Weise 𝔄^{2} aus 𝔄^{1} etc. Die Vereinigung der Kette 𝔄^{0} ⊂ 𝔄^{1} ⊂ 𝔄^{2} … ist die gesuchte T –e.a Struktur. □

Die im Beweis konstruierte Struktur 𝔐 kann sehr groß sein. Man sieht aber leicht, daß jede elementare Unterstruktur 𝔑 einer T –e.a 𝔐 wieder T –e.a ist: Sei 𝔑 ⊂ 𝔄 ein Modell von T. Weil 𝔐_{N} ⇒_{∃} 𝔄_{N}, gibt es eine Einbettung von 𝔐 in eine elementare Erweiterung 𝔅 von 𝔄, die N festhält. Weil 𝔐 existentiell abgeschlossen in 𝔅 ist, ist 𝔑 ebenfalls in 𝔅 existentiell abgeschlossen und daher auch in 𝔄.

[figure: 𝔑; 𝔄; 𝔐; 𝔅; ≺_{1}; ≺; ≺; ≺_{1}]

Lemma 8.6 Sei T eine Theorie. Dann gibt es eine größte induktive Theorie T^{KH} mit T_{∀} = T _{∀}^{KH}. Man nennt T^{KH} die Kaiserhülle von T.

Beweis: Seien T^{1} und T^{2} zwei induktive Theorien mit T _{∀}^{1} = T _{∀}^{2} = T_{∀}. Wir müssen zeigen, daß (T^{1} ∪ T^{2})_{∀} = T_{∀}. Sei 𝔐 ein Modell von T. Wir erweitern wie im Beweis von 8.4 𝔐 durch eine Kette 𝔄_{0} ⊂ 𝔅_{0} ⊂ 𝔄_{1} ⊂ 𝔅_{1} … von Modellen von T^{1} und T^{2}. Die Vereinigung der Kette ist ein Modell von T^{1} ∪ T^{2}. □

Lemma 8.7 T^{KH} ist der ∀∃–Teil der Theorie der T -e.a Strukturen.

Beweis: Sei T^{∗} dieser ∀∃–Teil. Weil T –e.a Strukturen Modelle von T_{∀} sind, ist T_{∀} ⊂ T _{∀}^{∗}. Aus 8.5 folgt T _{∀}^{∗} ⊂ T_{∀}. Also ist T^{∗} in der Kaiserhülle enthalten. Es bleibt zu zeigen, daß jede T –e.a Struktur 𝔐 ein Modell der Kaiserhülle ist. Wir wählen dazu ein Modell 𝔑 von T^{KH}, das 𝔐 enthält. Dann ist 𝔐 ≺_{1} 𝔑. Daraus folgt 𝔑 ⇒_{∀∃} 𝔐 und daraus die Behauptung. □

Aus dem Lemma folgt sofort, daß T –e.a. Strukturen immer Modelle von T_{∀∃} sind.

Satz 8.8 Sei T eine Theorie. Dann sind äquivalent:

a) T hat einen Modellbegleiter T^{∗}

b) Alle Modelle von T^{KH} sind T –e.a.

c) Die T –e.a Strukturen bilden eine elementare Klasse.

Wenn T^{∗} existiert, ist

T^{∗} = T^{KH} = Theorie der T –e.a Strukturen.

Beweis:

a) ⇒ b): Sei T^{∗} der Modellbegleiter von T. Als modellvollständige Theorie ist T^{∗} induktiv. Also ist T^{∗} in der Kaiserhülle enthalten und es genügt zu zeigen, daß jedes Modell 𝔐 von T^{∗} T –e.a ist. Sei 𝔄 ein Modell von T, daß 𝔐 enthält. 𝔄 ist in ein Modell 𝔑 von T^{∗} einbettbar. Aus 𝔐 ≺ 𝔑 folgt 𝔐 ≺_{1} 𝔄. b) ⇒ c): Nach dem letzten Lemma sind alle T –e.a Strukturen Modelle von T^{KH}. Aus der Annahme folgt also, daß die Klasse der T –e.a Strukturen genau die Modellklasse von T^{KH} ist.

c) ⇒ a): Nehmen wir an, daß die T -e.a Strukturen gerade die Modelle der Theorie T^{+} sind. Aus 8.5 folgt T_{∀} = T _{∀}^{+}. Mit dem Kriterium 8.3 ergibt sich, daß T^{+} modellvollständig ist. Also ist T^{+} Modellbegleiter von T.

Die letzte Behauptung des Satzes ergibt sich sofort aus unserer Argumentation. □

9 Beispiele

Die Modelle der Theorie T_{∞} der unendlichen Mengen sind genau die unendlichen Mengen ohne weitere Struktur. Die Sprache L_{∅} ist leer, die Axiome sind (für n = 1, 2, …)

• ∃x_{0} … x_{n−1} ⋀_{i<j<n} ¬x_{i} =^{.} x_{j}

Satz 9.1 Die Theorie T_{∞} der unendlichen Mengen hat Quantorenelimination und ist vollständig.

Beweis: Klar. □

Die Theorie T_{DLO} der dichten linearen Ordnungen ohne Endpunkte hat die Axiome (in L_{O})

• ∀x ¬x < x

• ∀x, y, z (x < y ∧ y < z → x < z)

• ∀x, y (x < y ∨ x =^{.} y ∨ y < x)

• ∀x, z (x < z → ∃y (x < y ∧ y < z))

• ∀x∃y x < y

• ∀y∃x x < y

Satz 9.2 T_{DLO} hat Quantorenelimination und ist vollständig.

Beweis: Sei A eine endliche Teilmenge der beiden Modelle O_{1} und O_{2}. Wir wählen eine aufsteigende Aufzählung A = {a_{1}, …, a_{n}}. Sei ∃y ρ(y) eine einfache Existenz– L(A)–Aussage, die in O_{1} gilt und sei O_{1} ⊧ ρ(b_{1}). Wir wollen die ordnungstreue Abbildung a_{i} ↦ a_{i} auf A ∪ {b_{1}} fortsetzen. Es gibt vier Fälle

i) b_{1} ∈ A. Dann setzen wir b_{2} = b_{1}.

ii) b_{1} liegt zwischen a_{i} und a_{i+1}. Dann wählen wir b_{2} in O_{2} mit der gleichen Eigenschaft.

iii) b_{1} ist kleiner als alle Elemente von A. Wir wählen ein ebensolches b_{2} ∈ O_{2}.

iv) b_{1} ist größer als alle a_{i}. Wähle b_{2} ebenso.

Wenn wir b_{1} auf b_{2} abbilden, haben wir einen Isomorphismus A∪{b_{1}} → A∪{b_{2}}, der zeigt, daß O_{2} ⊧ ρ(b_{2}).

T_{DLO} muß vollständig sein, weil die Sprache keine Konstanten enthält. □

Sei R ein (nicht notwendig kommutativer) Ring mit Einselement. Ein R– Modul

𝔐 = (M, 0, +, −, r)_{r∈R}

ist eine abelsche Gruppe (M, 0, +, −) mit einer Operation r : M → M für jedes Ringelement r, die gewisse Axiome erfüllen. Die Axiome formulieren wir in der Sprache L_{M(R)} = L_{AG} ∪ {r | r ∈ R}. Die Theorie T_{M(R)} der R–Moduln besteht dann aus

• T_{AG}

• ∀x, y r(x + y) =^{.} rx + ry

• ∀x (r + s)x =^{.} rx + sx

• ∀x (rs)x =^{.} r(sx)

• ∀x 1x =^{.} x

für beliebige Ringelemente r, s. T_{∞} ∪ T_{M(R)} ist die Theorie der unendlichen R–Moduln.

Satz 9.3 Sei K ein Körper. Dann hat die Theorie der unendlichen K–Moduln Quantorenelimination und ist vollständig.

Ein K–Modul ist natürlich nichts anderes als ein Vektorraum.

Beweis: Sei A eine endlich erzeugte Unterstruktur (also ein Untervektorraum) der beiden unendlichen K–Vektorräume V_{1} und V_{2} und ∃y ρ(y) eine einfache Existenz– L(A)–Aussage, die in V_{1} gilt. Sei b_{1} ein Element von V_{1}, das ρ(y) erfüllt. Wenn b_{1} zu A gehört, sind wir fertig, weil dann V_{2} ⊧ ρ(b_{1}). Sonst wählen wir ein b_{2} ∈ V_{2}\A. Dabei müssen wir eventuell zu einer elementaren Erweiterung von V_{2} übergehen. Die beiden Vektorräume A+Kb_{1} und A+Kb_{2} sind über A isomorph, unter einem Isomorphismus, der b_{1} auf b_{2} abbildet. Also ist V_{2} ⊧ ρ(b_{2}).

Die Theorie ist vollständig, weil eine quantorenfreie Aussage in einem Vektorraum genau dann gilt, wenn sie im Null–Vektorraum gilt. □

Die Klasse der algebraisch abgeschlossenen Körper (vgl. Abschnitt B.22) läßt sich axiomatisieren durch die Theorie T_{AAK}:

• T_{K} (Körperaxiome)

• Für jedes n > 0:

∀x_{0}, … x_{n−1} ∃y x_{0} + x_{1}y + … + x_{n−1}y^{n−1} + y^{n} =^{.} 0

Satz 9.4 (Tarski) Die Theorie T_{AAK} der algebraisch abgeschlossenen Körper hat Quantorenelimination.

Beweis: K_{1} und K_{2} seien zwei algebraisch abgeschlossene Körper und R ein gemeinsamer Unterring. ∃y ρ(y) sei eine einfache Existenzaussage mit Parametern in R, die in K_{1} gilt. Wir müssen zeigen, daß ∃y ρ(y) auch in K_{2} gilt.

Zuerst gehen wir in K_{1} und K_{2} jeweils zu den Quotientenkörpern F_{1} und F_{2} von R über. Nach B.21.1 gibt es einen Isomorphismus f : F_{1} → F_{2}, der R elementweise festläßt. Dann bilden wir die relativen Abschlüsse G_{i} der F_{i} in den K_{i}, (i = 1, 2). Nach B.22.3 setzt sich f zu einem Isomorphismus g : G_{1} → G_{2} fort.

[figure: R; R; id; F_{1}; F_{2}; f; G_{1}; G_{2}; g; G_{1}(b_{1}); K_{1}; K_{2}]

Sei b_{1} ein Element von K_{1}, das ρ(y) erfüllt. Es gibt zwei Fälle:

Fall 1 : b_{1} ∈ G_{1} Dann erfüllt b_{2} = g(b_{1}) die Formel ρ(y) in K_{2}.

Fall 2: b_{1} ∉ G_{1}: Dann ist b_{1} transzendent über G_{1} und die Körpererweiterung G_{1}(b_{1}) ist isomorph zum rationalen Funktionenkörper G_{1}(X). Wenn K_{2} eine echte Erweiterung von G_{2} ist, wählen wir für b_{2} irgendein Element aus K_{2} \ G_{2}. Dann setzt sich g zu einem Isomorphismus zwischen G_{1}(b_{1}) und G_{2}(b_{2}) fort, der b_{1} auf b_{2} abbildet. Also erfüllt auch b_{2} die Formel ρ(y) in K_{2}. Wenn K_{2} = G_{2}, wählen wir eine echte elementare Erweiterung K′_{2} von K_{2}. (K′_{2} existiert nach 6.1.2, weil K_{2} unendlich ist (B.22.4).) Dann gilt (aus dem gleichen Grund) ∃y ρ(y) in K′_{2} und daher in K_{2}. □

Für Primzahlen p sei

T_{AAK_{p}} = T_{AAK} ∪ {p · 1 =^{.} 0}

die Theorie der algebraisch abgeschlossen Körper der Charakteristik p,

T_{AAK_{0}} = T_{AAK} ∪ {¬n · 1 =^{.} 0 | n = 1, 2, …}

die Theorie der algebraisch abgeschlossen Körper der Charakteristik 0.

Folgerung 9.5 Die Theorien T_{AAK_{p}} und T_{AAK_{0}} sind vollständig.

Beweis: Konsistente Theorien mit Quantorenelimination, die eine Primstruktur haben, sind vollständig. Eine Primstruktur von T ist eine Struktur, die sich in alle Modelle von T isomorph einbetten läßt. □

Folgerung 9.6 T_{AAK} ist modellvollständig. □

Folgerung (Hilbertscher Nullstellensatz) Sei K ein Körper und

I ◁ K[X_{1}, …, X_{n}]

ein Polynomideal. Dann sind äquivalent:

a) I hat eine Nullstelle im algebraischen Abschluß acl(K).

b) 1 ∉ I

Beweis: Wenn 1 ∉ I, ist I in einem maximalen Ideal P enthalten (vgl. Abschnitt B.21.2). L = K[X_{1}, …, X_{n}]/P ist ein Erweiterungskörper von K, in dem die Restklassen der X_{i} eine Nullstelle von I bilden. Nach dem Hilbertschen Basissatz ist I endlich erzeugt, sagen wir von f_{0}, …, f_{k−1}. Betrachte die Formel

ϕ = ∃x_{1}, … x_{n} ⋀_{i<k} f_{i}(x_{1}, …, x_{n}) =^{.} 0

Dann gilt ϕ in L und daher in acl(L). Wir können annehmen, daß acl(K) in acl(L) liegt. Wegen acl(K) ≺ acl(L) gilt dann ϕ in acl(K). □

Die für den nächsten Satz gebrauchte Theorie der reell abgeschlossenen Körper findet man im Abschnitt B.23. Wir formulieren T_{RAK}, die Theorie der reell abgeschlossenen Körper, in der Sprache L_{AR} für angeordnete Ringe.

Satz 9.7 T_{RAK} hat Quantorenelimination und ist vollständig.

Beweis: (K_{1}, <) und (K_{2}, <) seien zwei reell abgeschlossene Körper und R ein gemeinsamer Unterring. ∃y ρ(y) (für ein quantorenfreies ρ) sei eine L_{AR}(R)–Aussage, die in (K_{1}, <) gilt. Wir müssen zeigen, daß ∃y ρ(y) auch in (K_{2}, <) gilt.

Zuerst gehen wir in K_{1} und K_{2} jeweils zu den Quotientenkörpern F_{1} und F_{2} von R über. Nach B.21.1 und B.23.1 gibt es einen Isomorphismus f : (F_{1}, <) → (F_{2}, <), der R elementweise festläßt. Die relativen algebraischen Abschlüsse G_{i} der F_{i} in den K_{i}, (i = 1, 2) sind reelle Abschlüsse der (F_{i}, <). Nach B.23.4 setzt sich f zu einem Isomorphismus g : (G_{1}, <) → (G_{2}, <) fort.

Sei b_{1} ein Element von K_{1}, das ρ(y) erfüllt. Es gibt zwei Fälle:

Fall 1 : b_{1} ∈ G_{1} Dann erfüllt b_{2} = g(b_{1}) die Formel ρ(y) in K_{2}.

Fall 2: b_{1} ∉ G_{1}: Dann ist b_{1} transzendent über G_{1} und die Körpererweiterung G_{1}(b_{1}) ist isomorph zum rationalen Funktionenkörper G_{1}(X). Sei G_{1}^{l} die Menge der Elemente von G_{1}, die kleiner als b_{1} sind, G_{1}^{r} die Menge der Elemente von G_{1}, die größer als b_{1} sind. Die Elemente von G_{2}^{l} = g(G_{1}^{l}) sind kleiner als die Elemente von G_{2}^{r} = g(G_{1}^{r}). Weil Körper dicht geordnet sind, finden wir in einer elementaren Erweiterung (K′_{2}, <) von (K_{2}, <) ein b_{2}, das zwischen den Elementen von G_{2}^{l} und den Elementen von G_{2}^{r} liegt. Weil b_{2} nicht in G_{2} liegt, ist b_{2} transzendent über G_{2}. Also setzt sich g zu einem Isomorphismus h zwischen G_{1}(b_{1}) und G_{2}(b_{2}) fort, der b_{1} auf b_{2} abbildet.

Es bleibt noch zu zeigen, daß h ordnungstreu ist. Es genügt zu zeigen, daß h ordnungstreu auf G_{1}[b_{1}] ist (B.23.1). Sei p(b_{1}) ein Element von G_{1}[b_{1}]. Nach B.23.6 hat man eine Zerlegung

p(X) = ϵ ∏_{i<m}(X − a_{i}) ∏_{j<n}((X − c_{j})^{2} + d_{j}),

mit positiven d_{j}. Ob p(b_{1}) positiv ist, hängt nur davon ab, wieviele der Faktoren ϵ, b_{1} − a_{0}, …, b_{1} − a_{m−1} negativ sind. Ob h(p(b_{1})) positiv ist, hängt in der gleichen Weise davon ab, wieviele der Faktoren g(ϵ), b_{2}−g(a_{0}), …, b_{2}−g(a_{m−1}) negativ sind. b_{2} ist aber so gewählt, daß

b_{1} < a_{i} ⇔ b_{2} < g(a_{i}).

Also ist p(b_{1}) genau dann positiv, wenn h(p(b_{1})) positiv ist.

Schließlich haben wir

\begin{aligned}(K_{1}, <) ⊧ ρ(b_{1}) & ⇒ & (G_{1}(b_{1}), <) ⊧ ρ(b_{1}) & ⇒ & (G_{2}(b_{2}), <) ⊧ ρ(b_{2}) & ⇒ \\ & ⇒ & (K′_{2}, <) ⊧ ∃y ρ(y) & ⇒ & (K_{2}, <) ⊧ ∃y ρ(y) \end{aligned}

T_{RAK} ist vollständig, weil der angeordnete Körper der rationalen Zahlen eine Primstruktur ist. □

Folgerung (17. Hilbertsches Problem) Sei (K, <) ein reell abgeschlossener Körper. Ein Polynom f ∈ K[X_{1}, …, X_{n}] ist genau dann eine Summe von Quadraten

f = g_{1}^{2} + … + g_{k}^{2}

von rationalen Funktionen aus K(X_{1}, …, X_{n}), wenn

f(a_{1}, …, a_{n}) ≥ 0

für alle n–tupel a_{1}, …, a_{n} aus K.

Beweis: Sei f eine Summe von Quadraten von rationalen Funktionen, also

f = (\frac{g_{1}}{h_{1}} )^{2} + ⋯ + (\frac{g_{k}}{h_{k}} )^{2}.

Sei D die Menge aller \overline{a} ∈ K^{n}, für die keiner der Nenner h_{i}(\overline{a}) Null ist. Für die \overline{a} ∈ D ist

f(\overline{a}) = (\frac{g_{1}(\overline{a})}{h_{1}(\overline{a})})^{2} + ⋯ + (\frac{g_{k}(\overline{a})}{h_{k}(\overline{a})})^{2} ≥ 0.

In der natürlichen Topologie des K^{n} ist D dicht (und offen). Die Menge aller \overline{a} mit f(\overline{a}) ≥ 0 ist abgeschlossen und enthält D. Also ist f(\overline{a}) ≥ 0 für alle \overline{a}.

Für die Umkehrung nehmen wir an, daß f keine Summe von Quadraten ist. Dann hat K(X_{1}, …, X_{n}) nach B.23.3 eine Anordnung, bezüglich der f negativ wird. Weil in K die positiven Elemente Quadrate sind, setzt diese Anordnung, die wir wieder mit < bezeichnen, die Anordnung von K fort. Sei (L, <) der reelle Abschluß von (K(X_{1}, …, X_{n}), <). Weil in (L, <) die Aussage ∃ x_{1}, …, x_{n}f(x_{1}, …, x_{n}) < 0 wahr ist, gilt sie auch in (K, <). □

Abzählbare Modelle

10 Der Omitting Types Satz

Definition Sei T eine L–Theorie und Σ(x) eine Menge von L–Formeln. Eine Formel ϕ(x) realisiert Σ(x) lokal, wenn

a) ϕ(x) mit T konsistent^{1} ist,

b) T ⊢ ∀x (ϕ(x) → σ(x)) für alle σ(x) aus Σ(x)

T läßt Σ(x) lokal aus, wenn Σ(x) nicht lokal realisiert wird.

Satz 10.1 (Omitting Types) Wenn T abzählbar^{2} und konsistent ist und Σ(x) von T lokal ausgelassen wird, hat T ein Modell, das Σ(x) ausläßt.

Wenn Σ(x) von ϕ(x) lokal realisiert wird, wird Σ(x) in Modellen von T von allen Realisierungen von ϕ(x) realisiert. Wenn T vollständig ist, gilt also auch die Umkehrung des Satzes: Wenn Σ(x) von T lokal realisiert wird, wird Σ(x) in allen Modellen von T realisiert.

Beweis: Wir fixieren eine abzählbare Menge C von neuen Konstanten und erweitern T zu einer konsistenten Theorie T^{∗} mit den folgenden Eigenschaften:

a) T^{∗} ist eine Henkin–Theorie. Das heißt: für alle L(C)–Formeln ψ(x) gibt es ein c ∈ C mit ∃x ψ(x) → ψ(c) ∈ T^{∗}.

b) Für alle c ∈ C gibt es ein σ(x) ∈ Σ(x) mit ¬σ(c) ∈ T^{∗}.

Wir konstruieren T^{∗} als Vereinigung einer aufsteigenden Folge

T = T_{0} ⊂ T_{1} ⊂ …

1 Das heißt, daß T ∪ {∃x ϕ(x)} konsistent ist. Allgemeiner heißt eine Formelmenge Φ(x)

konsistent mit T, wenn T ein Modell hat, in dem Φ realisiert wird.

2 Eine L–Theorie heißt abzählbar, wenn L höchstens abzählbar ist.

von konsistenten Erweiterungen von T durch jeweils endlich viele Axiome. Dabei erfüllen wir schließlich alle oben aufgeführten Bedingungen. Sei T_{i} schon konstruiert und sei eine der Aufgaben a) oder b) gestellt und demgemäß ψ(x) oder ein c vorgegeben.

Fall a): Wir wählen ein c ∈ C, das weder in T_{i} noch in ψ(x) vorkommt. Dann ist T_{i+1} = T_{i} ∪ {∃x ψ(x) → ψ(c)} konsistent.

Fall b): Sei T_{i} äquivalent zu T ∪ \{δ(c, \overline{c})\}. Setze ϕ(x) = ∃ȳδ(x, ȳ). Dann ist ϕ(x) mit T konsistent. Wenn nun T_{i} ∪ {¬σ(c)} inkonsistent ist, das heißt, wenn T ⊢ δ(c, \overline{c}) → σ(c), so folgt

T ⊢ ∀x (ϕ(x) → σ(x)).

Weil Σ(x) nicht lokal realisiert wird, gibt es also immer ein σ(x) ∈ Σ(x), für das T_{i+1} = T_{i} ∪ {¬σ(c)} konsistent ist.

Sei nun (𝔄′, a_{c})_{c∈C} ein Modell von T^{∗}. Weil T^{∗} eine Henkin–Theorie ist, ist A = {a_{c} | c ∈ C} Universum einer elementaren Unterstruktur 𝔄 (siehe Tarskis Test 4.2 oder den Hilfssatz auf Seite 23). Wegen Eigenschaft b) wird Σ(x) von 𝔄 ausgelassen. □

Folgerung 10.2 (aus dem Beweis) Sei T abzählbar und konsistent und (Σ_{i}(x_{1}, …, x_{n_{i}})) eine höchstens abzählbare Familie von Formelmengen, die alle von T lokal ausgelassen werden. Dann gibt es ein Modell, das alle Σ_{i} ausläßt.

Beweis: Klar. □

Sei T eine Theorie. Ein n–Typ ist eine maximale Formelmenge p(x_{1}, …, x_{n}), die konsistent mit T ist. Wir bezeichnen mit S_{n}(T) die Menge aller n–Typen von T. Wenn T vollständig ist und 𝔄 irgendein Modell von T, ist

S_{n}(T) = S_{n}^{𝔄}(∅).

Sei p(x_{1}, …, x_{n}) ein n–Typ von T und ϕ(x_{1}, …, x_{n}) eine Formel. Dann sind äquivalent

a) ϕ(x_{1}, …, x_{n}) realisiert p(x_{1}, …, x_{n}) lokal.

b) p(x_{1}, …, x_{n}) ist der einzige Typ, der ϕ(x_{1}, …, x_{n}) enthält. Man sagt dazu, daß ϕ(x_{1}, …, x_{n}) den Typ p isoliert..

c) p(x_{1}, …, x_{n}) = ⟨ϕ(x_{1}, …, x_{n})⟩, wobei

⟨ϕ(\overline{x})⟩ = \{ψ(\overline{x}) | T ⊢ ∀\overline{x} (ϕ(\overline{x}) → ψ(\overline{x}))\}.

Typen dieser Form heißen Haupttypen. ⟨ϕ(\overline{x})⟩ ist der von ϕ erzeugte Haupttyp.

Wegen b) heißen lokal realisierte Typen auch isolierte Typen. Wenn ⟨ϕ(\overline{x})⟩ ein Typ ist, heißt ϕ(\overline{x}) vollständig. Man sieht leicht, daß eine Formel genau dann vollständig ist, wenn sie atomar ist. Das heißt, daß ϕ(\overline{x}) konsistent mit T ist und daß für alle ψ(\overline{x}) entweder ϕ∧ψ oder ϕ∧¬ψ mit T inkonsistent ist. Haupttypen heißen darum auch atomar.

11 ℵ_{0}–kategorische Theorien

Satz 11.1 (Ryll–Nardzewski) Sei T eine abzählbare vollständige Theorie ohne endliches Modell. Dann ist T genau dann ℵ_{0}–kategorisch, wenn es für jedes n bis auf T –Äquivalenz nur endliche viele Formeln ϕ(x_{1}, …, x_{n}) gibt.

Beweis: Zum Beweis brauchen wir einen neuen Begriff.

Definition Eine L–Struktur 𝔄 ist ℵ_{0}–saturiert, wenn in 𝔄 jeder Typ^{3} über jeder endlichen Teilmenge realisiert ist.

Der Satz folgt nun aus den folgenden drei Behauptungen:

Behauptung 1: Wenn es für jedes n nur endlich viele ϕ(x_{1}, …, x_{n}) modulo T gibt, sind alle Modelle von T ℵ_{0}–saturiert.

Beweis: Sei 𝔄 ein Modell von T und B eine n–elementige Teilmenge. Wenn es bis auf Äquivalenz nur N–viele Formeln in den Variablen x_{1}, …, x_{n+1} gibt, gibt es bis auf Äquivalenz in 𝔄 höchstens N–viele L(B)–Formeln ϕ(x). Also enthält jeder Typ p(x) ∈ S(B) eine „kleinste“ Formel ϕ_{p}(x)^{4}. Jedes Element von A, das ϕ_{p}(x) realisiert, realisiert auch p(x).

Behauptung 2: Wenn alle abzählbaren Modelle von T ℵ_{0}–saturiert sind, ist T ℵ_{0}–kategorisch.

Beweis: Weil T vollständig ist, sind alle Modelle von T elementar äquivalent. Wende jetzt das nächste Lemma (11.2) an.

Behauptung 3: Wenn T ℵ_{0}–kategorisch ist, gibt es für jedes n nur endlich viele Formeln ϕ(x_{1}, …, x_{n}) modulo T.

Wenn T ℵ_{0}–kategorisch ist, kann es keine Typen geben, die in einem Modell ausgelassen werden können und (natürlich) in anderen realisiert. Wegen des Omitting Types Satzes (10.1) bedeutet das, daß alle Typen aus S_{n}(T) atomar sind. Das bedeutet, daß es keinen Typ gibt, der

Δ = {¬ϕ(x_{1}, …, x_{n}) | ϕ(x_{1}, …, x_{n}) atomar}

enthält, Δ ist also nicht konsistent mit T. Es folgt, daß T eine Disjunktion ϕ_{1}(x_{1}, …, x_{n}) ∨ … ∨ ϕ_{k}(x_{1}, …, x_{n}) von vollständigen Formeln impliziert. Es gibt dann modulo T höchstens 2^{k}–viele Formeln ψ(x_{1}, …, x_{n}), weil

T ⊢ ∀\overline{x} (ψ(\overline{x}) ↔ ⋁\{ϕ_{i}(\overline{x}) | ϕ_{i}(\overline{x}) ∧ ψ(\overline{x}) konsistent mit T \}).
□

3Hier sind Typen in einer Variablen gemeint. Man sieht aber leicht, daß in ℵ_{0}–saturierten Strukturen auch alle n–Typen über endlichen Parametermengen realisiert sind (siehe Beweis von 11.4).

4 p(x) ist also atomar bezüglich Th(𝔄_{B}).

Lemma 11.2 Zwei elementar äquivalente, höchstens abzählbare und ℵ_{0}–saturierte Strukturen sind isomorph.

Beweis: 𝔄 und 𝔅 seien wie im Lemma. Wie wählen Aufzählungen A = {a_{0}, a_{1}, …} und B = {b_{0}, b_{1}, …}. Dann konstruieren wir eine aufsteigende Folge f_{0} ⊂ f_{1} ⊂ … von endlichen elementaren Abbildungen^{5}

f_{i} : A_{i} → B_{i}.

Dabei sind A_{i} und B_{i} endliche Teilmengen von A und B und f_{i} präserviert die Gültigkeit von Formeln:

𝔄 ⊧ ϕ(\overline{a}) ⇒ 𝔅 ⊧ ϕ(f_{i}(\overline{a})).

Wir werden dafür sorgen, daß A die Vereinigung der A_{i} und B die Vereinigung der B_{i} ist. Die Vereinigung der f_{i} ist dann der gesuchte Isomorphismus zwischen 𝔄 und 𝔅.

f_{0} = ∅ ist elementar, weil 𝔄 und 𝔅 elementar äquivalent sind. Nehmen wir an, daß f_{i} schon konstruiert ist. Es gibt zwei Fälle:

i = 2n ist gerade Dann versuchen wir f_{i} auf A_{i+1} = A_{i} ∪ {a_{n}} fortzusetzen. Dazu betrachten wir den Typ

p(x) = tp(a_{n}/A_{i}).

Weil f_{i} elementar ist, ist (wie man leicht sieht)

f_{i}(p)(x) = \{ϕ(x, f_{i}(\overline{a})) | ϕ(x, \overline{a}) ∈ p(x)\}

in 𝔅 ein Typ über B_{i}. Weil 𝔅 ℵ_{0}–saturiert ist, gibt es eine Realisierung b′_{n} dieses Typs. Es ist dann für \overline{a} ∈ A_{i}

𝔄 ⊧ ϕ(a_{n}, \overline{a}) ⇒ 𝔅 ⊧ ϕ(b′_{n}, f_{i}(\overline{a})).

Wir können also f_{i} durch f_{i+1}(a_{n}) = b′_{n} fortsetzen.

i = 2n + 1 ist ungerade Wir vertauschen rechts und links: Weil 𝔄 ℵ_{0}–saturiert ist, finden wir f_{i+1} mit B_{i+1} = B_{i} ∪ {b_{n}}. □

Folgerung 11.3 L sei eine höchstens abzählbare Sprache, 𝔄 eine L–Struktur und a_{1}, …, a_{n} Elemente von 𝔄. Dann ist Th(𝔄) genau dann ℵ_{0}–kategorisch, wenn Th(𝔄, a_{1}, …, a_{n}) ℵ_{0}–kategorisch ist.

Beispiele: Die folgenden Theorien sind ℵ_{0}–kategorisch:

5Eine Abbildung f von einer Teilmenge einer Struktur 𝔄 in eine andere Struktur 𝔅 heißt elementar, wenn sie die Gültigkeit von Formeln präserviert. Dieser Begriff hängt nicht nur von f sondern auch von 𝔄 und 𝔅 ab!

T_{∞} die Theorie der unendlichen Mengen

Für jeden endlichen Körper 𝔽_{q} die Theorie der unendlichen 𝔽_{q}–Vektorräume

Die Theorie der T_{DLO} der dichten linearen Ordnungen ohne Endpunkte (Satz von Cantor).

Das folgt aus 11.1, weil T_{DLO} Quantorenelimination hat: Es gibt für jedes n nur endlich viele (sagen wir N_{n}) Möglichkeiten n (nicht notwendig verschiedene) Elemente anzuordnen. Für n = 2 zum Beispiel gibt es die drei Möglichkeiten a_{1} < a_{2}, a_{1} = a_{2} und a_{2} < a_{1}. Jede dieser Möglichkeiten entspricht einer vollständigen Formel ψ(x_{1}, …, x_{n}) (bis auf Äquivalenz). Also gibt es bis auf Äquivalenz genau 2^{N_{n}} viele Formeln ϕ(x_{1}, …, x_{n}).

Wir studieren das Problem der Existenz von ℵ_{0}–saturierten Strukturen:

Definition Eine Theorie T heißt schmal, wenn S_{n}(T) für alle n höchstens abzählbar ist.

Eine abzählbare Theorie mit höchstens abzählbar vielen nicht–isomorphen höchstens abzählbaren Modellen ist zum Beispiel immer schmal. Die Umkehrung gilt nicht.

Lemma 11.4 Eine abzählbare^{6} vollständige konsistente Theorie hat genau dann ein höchstens abzählbares ℵ_{0}–saturiertes Modell, wenn sie schmal ist.

Beweis: Wenn alle Typen in einem einzigen höchstens abzählbaren Modell realisiert werden, kann es nur höchstens abzählbar viele Typen geben.

Wenn umgekehrt S_{n+1}(T) höchstens abzählbar ist, gibt es in Modellen von T über jeder n–elementigen Menge ebenfalls höchstens abzählbar viele Typen. Wir konstruieren eine elementare Kette

𝔄_{0} ≺ 𝔄_{1} ≺ …

von Modellen von T. Für 𝔄_{0} nehmen wir ein beliebiges höchstens abzählbares Modell. Wenn 𝔄_{i} konstruiert ist, wählt man 𝔄_{i+1} so, daß alle Typen über endlichen Teilmengen von A_{i} in 𝔄_{i+1} realisiert werden. Nach Voraussetzung gibt es höchstens abzählbar viele solche Typen. Also kann man 𝔄_{i+1} höchstens abzählbar wählen, vgl. 5.4 und 6.1.1. Die Vereinigung 𝔄 = ⋃_{i∈ℕ} 𝔄_{i} ist ℵ_{0}–saturiert, weil jeder Typ über einer endlichen Teilmenge von 𝔄 schon über einer endlichen Teilmenge eines A_{i} definiert ist, und dann in 𝔄_{i+1} realisiert wird. □

Satz 11.5 (Vaught) Eine abzählbare vollständige Theorie kann nicht genau zwei nicht–isomorphe abzählbare Modelle haben.

6 Die Behauptung gilt auch, wenn L überabzählbar ist.

Beweis: Wir können annehmen, daß T schmal ist und nicht ℵ_{0}–kategorisch. Wir zeigen, daß T mindestens drei nicht–isomorphe abzählbare Modelle hat. T hat ein abzählbares ℵ_{0}–saturiertes Modell 𝔄 und ein abzählbares Modell 𝔅, in dem ein Typ p(\overline{x}) nicht realisiert wird. p(\overline{x}) sei in 𝔄 durch \overline{a} realisiert. Weil Th(𝔄, \overline{a}) nicht ℵ_{0}–kategorisch ist, hat Th(𝔄, \overline{a}) ein abzählbares Modell (ℭ, \overline{c}), das nicht ℵ_{0}–saturiert ist. ℭ ist nicht ℵ_{0}–saturiert und daher nicht isomorph zu 𝔄. ℭ realisiert aber p(\overline{x}) und ist darum nicht isomorph zu 𝔅. □

Sei T eine L–Theorie und ϕ(x_{1}, …, x_{n}) eine L–Formel. Wir führen ein neues n–stelliges Relationszeichen R_{ϕ} ein und setzen

L′ = L ∪ {R_{ϕ}}
T′ = T ∪ {∀x_{1} … x_{n} (R_{ϕ}(x_{1}, …, x_{n}) ↔ ϕ(x_{1}, …, x_{n}))}.

T′ ist eine definitorische Erweiterung von T (um ein Relationszeichen). Theorien, die eine gemeinsame definitorische Erweiterung haben, nennt man definitorisch äquivalent. Man sieht leicht, daß T genau dann vollständig (oder ℵ_{0}– kategorisch) ist, wenn T′ vollständig (oder ℵ_{0}–kategorisch) ist.

Wenn man für jede Formel ϕ ein neues Relationszeichen einführt, erhält man eine definitorische Erweiterung T^{∗}, die offensichtlich Quantorenelimination hat^{7}.

Wir untersuchen im Rest dieses Abschnitts vollständige Theorien, die definitorisch äquivalent zu Theorien sind, die Quantorenelimination haben und deren Sprache endlich und relational ist (das heißt, keine Konstanten und Funktionszeichen enthält). Aus 11.6.1 folgt, daß solche Theorien ℵ_{0}–kategorisch sind.

Definition Eine L-Struktur 𝔄 ist algebraisch ω–homogen, wenn sich jeder Isomorphismus

f_{0} : B_{0} →^{∼} C_{0}

zwischen endlichen Unterstrukturen von 𝔄 auf jede endliche Oberstruktur von B_{0} fortsetzen läßt. Das bedeutet, daß es zu jedem b ∈ A ein c ∈ A gibt, für das

f = f_{0} ∪ {⟨b, c⟩}

ein Isomorphismus ist ^{8}.

Wir halten für den Rest des Abschnitts eine endliche relationale Sprache L fest.

Lemma 11.6 T sei eine vollständige Theorie und 𝔐 ein unendliches Modell von T.

1) Wenn T Quantorenelimination hat, ist T ℵ_{0}–kategorisch.

2) T hat genau dann Quantorenelimination, wenn 𝔐 algebraisch ω–homogen ist.

7Man nennt T^{∗} die Morleyisierung von T.

8Die Definition von ω–homogen findet sich auf Seite 66.

Beweis: 1): Es gibt für jedes n nur endlich viele nicht–äquivalente quantorenfreie Formeln ρ(x_{1}, …, x_{n}). Wenn T Quantorenelimination hat, gibt es also für jedes n nur endlich viele Formeln ϕ(x_{1}, …, x_{n}) modulo T.

2): Nehmen wir an, daß T Quantorenelimination hat. Dann ist T ℵ_{0}–kategorisch und 𝔐 ℵ_{0}–saturiert. Wie im Beweis von 11.2 sieht man, daß 𝔐 ω–homogen ist. Weil Isomorphismen zwischen Teilmengen von A elementar sind, bedeutet das, daß 𝔐 algebraisch ω–homogen ist. Sei schließlich 𝔐 algebraisch ω–homogen. In 𝔐 erfüllen n–Tupel \overline{a}, die denselben quantorenfreien Typ

tp_{qf}(\overline{a}) = \{ρ(\overline{x}) | 𝔐 ⊧ ρ(\overline{a}), ρ(\overline{x}) quantorenfrei\}

haben, dieselben einfachen Existenzformeln. Wir wollen zeigen, daß jede einfache Existenzformel ϕ(x_{1}, …, x_{n}) = ∃y ρ(x_{1}, …, x_{n}, y) modulo T zu einer quantorenfreien Formel äquivalent ist. Seien r_{1}(\overline{x}), …, r_{k−1}(\overline{x}) die quantorenfreien Typen aller n–Tupel in 𝔐, die ϕ(\overline{x}) erfüllen. Sei ρ_{i}(\overline{x}) äquivalent zur Konjunktion aller Formeln aus r_{i}(\overline{x}). Dann ist

T ⊢ ∀\overline{x} (ϕ(\overline{x}) ↔ ⋁_{i<k} ρ_{i}(\overline{x})).

□

Definition Das Skelett einer L–Struktur 𝔐 ist die Klasse aller endlichen L– Strukturen, die isomorph zu einer Unterstruktur von 𝔐 sind. Die leere Struktur ist dabei zugelassen.

Bemerkung Sei K das Skelett von 𝔐. Dann ist 𝔐 genau dann algebraisch ω– homogen, wenn 𝔐 K–saturiert ist: Für alle 𝔄, 𝔅 aus K und alle Einbettungen f_{0} : 𝔄 → 𝔐 und f_{1} : 𝔄 → 𝔅 gibt es eine Einbettung g_{1} : 𝔅 → 𝔐 mit f_{0} = g_{1}∘f_{1}.

Beweis: Seien 𝔄, 𝔅, f_{0} und f_{1} gegeben und g_{1} gesucht. Weil 𝔅 in K liegt, können wir annehmen, daß 𝔅 ⊂ 𝔐. Darüberhinaus können wir annehmen, daß 𝔄 ⊂ 𝔅 und f_{1} die Inklusionsabbildung ist. Das gesuchte g_{1} ist jetzt nichts anderes als eine Fortsetzung des Isomorphismus f_{0} : 𝔄 → f_{0}(𝔄) auf 𝔅. □

Satz 11.7 Höchstens abzählbare algebraisch ω–homogene Strukturen sind durch ihr Skelett bis auf Isomorphie eindeutig bestimmt.

Beweis: 𝔐 und 𝔑 seien höchstens abzählbar, algebraisch ω–homogen und mit dem gleichen Skelett K. Ähnlich wie im Beweis von 11.2 konstruieren wir einen Isomorphismus zwischen 𝔐 und 𝔑 als Vereinigung einer aufsteigenden Folge von Isomorphismen zwischen endlichen Teilmengen von M und N. Dazu genügt offenbar die folgende Tatsache (und ihr Pendant mit vertauschten 𝔐 und 𝔑), die sofort aus der K–Saturierheit folgt.

Behauptung: Jede isomorphe Einbettung f_{1} : A → 𝔑 einer endlichen Teilmenge A von 𝔐 nach 𝔑 läßt sich, für jedes a ∈ M, zu einer Einbettung g_{1} : A ∪ {a} → 𝔑 fortsetzen. □

Satz 11.8 Sei K eine Klasse von endlichen L–Strukturen. Dann gibt es genau dann eine höchstens abzählbare, algebraisch ω–homogene L–Struktur 𝔐 mit dem Skelett K, wenn

a) K enthält die leere Struktur.

b) Wenn 𝔄_{0} zu K gehört, gehören auch alle Elemente des Skelettes von 𝔄_{0} zu K.

c) (Amalgamation) Seien 𝔄, 𝔅_{0}, 𝔅_{1} ∈ K und f_{i} : 𝔄 → 𝔅_{i}, (i = 0, 1) isomorphe Einbettungen. Dann gibt es ein ℭ ∈ K und zwei Einbettungen g_{i} : 𝔅_{i} → ℭ, sodaß g_{0} ∘ f_{0} = g_{1} ∘ f_{1}.

[figure: 𝔄; 𝔅_{0}; 𝔅_{1}; ℭ; f_{0}; f_{1}; g_{0}; g_{1}]

Beweis: Wir wollen zeigen, daß das Skelett von 𝔐 die Amalgamationseigenschaft hat, wenn 𝔐 algebraisch ω–homogen ist. Dazu seien 𝔄, 𝔅_{0}, 𝔅_{1}, f_{0} und f_{1} gegeben. Wir können annehmen, daß 𝔅_{0} ⊂ 𝔐. Nach der obigen Bemerkung gibt es ein g_{1} : 𝔅_{1} → 𝔐 mit f_{0} = g_{1} ∘ f_{1}. Wähle für ℭ eine endliche Unterstruktur von 𝔐, die 𝔅_{0} und das Bild von g_{1} enthält. Schließlich nimmt man für g_{0} : 𝔅_{0} → ℭ die Inklusion.

Nehmen wir umgekehrt an, daß K die Eigenschaften a,b,c hat. Wir wählen eine Aufzählung (𝔅_{i})_{i∈ω} aller Isomorphietypen aus K. 𝔐 konstruieren wir als Vereinigung einer aufsteigenden Folge

∅ = 𝔐_{0} ⊂ 𝔐_{1} ⊂ …

von Elementen von K. Nehmen wir an, daß 𝔐_{i} schon konstruiert ist. Wenn i = 2n gerade ist, wählen wir 𝔐_{i+1} als Spitze des Diagramms

[figure: ∅; 𝔐_{i}; 𝔅_{n}; ,; 𝔐_{i+1}; ∅; ∅; g_{0}; g_{1}]

wobei wir annehmen, daß g_{0} die Inklusionsabbildung id_{𝔐_{i}} ist. Wenn i = 2n + 1 ungerade ist, geben wir uns zwei Strukturen 𝔄 und 𝔅 aus K und zwei Einbettungen f_{0} : 𝔄 → 𝔐_{i} und f_{1} : 𝔄 → 𝔅 vor. 𝔐_{i+1} wählen wir dann mit dem Diagramm

[figure: 𝔄; 𝔐_{i}; 𝔅; 𝔐_{i+1}; f_{0}; f_{1}; id_{𝔐_{i}}; g_{1}]

Welche Einbettungen man sich vorgeben muß, werden wir gleich sehen. Es ist klar, daß 𝔐 das richtige Skelett hat. Denn die endliche Unterstrukturen von 𝔐 sind die Unterstrukturen der 𝔐_{i}. Weil die 𝔐_{i} zu K gehören, gehören auch ihre Unterstrukturen zu K. Andererseits ist 𝔅_{n} jeweils isomorph zu einer Unterstruktur von 𝔐_{2n+1}.

Zu zeigen bleibt, daß 𝔐 algebraisch ω–homogen ist. Seien dazu 𝔄, 𝔅 aus K und Einbettungen f_{0} : 𝔄 → 𝔐 und f_{1} : 𝔄 → 𝔅 gegeben. Das Bild von f_{0} liegt für genügend großes j in 𝔐_{j}. Während der Konstruktion der 𝔐_{i} achten wir darauf, daß irgendwann, für ein ungerades i ≥ j bei der Konstruktion von 𝔐_{i+1} die Einbettungen f_{0} : 𝔄 → 𝔐_{i} und f_{1} : 𝔄 → 𝔅 behandelt worden sind. (Das geht, weil es – bis auf Isomorphie – für festes j höchstens abzählbar viele Möglichkeiten gibt.) Es gibt dann eine Einbettung g_{1} : 𝔅 → 𝔐_{i+1} mit f_{0} = g_{1}∘f_{1}. □

Beispiel: Die Klasse der endlichen Graphen^{9} hat offensichtlich die Amalgamationseigenschaft. Die zugehörige höchstens abzählbare algebraisch ω–homogene Struktur ist der Randomgraph.

9 Ein Graph (G, R) ist eine Menge G mit einer symmetrischen, irreflexiven binären Relation.

12 Primmodelle

Wir halten in diesem Abschnitt eine abzählbare, vollständige Theorie ohne endliche Modelle fest.

Definition 𝔄_{0} ist ein Primmodell von T, wenn 𝔄_{0} in alle Modelle von T elementar einbettbar ist.

Weil T immer abzählbare Modelle hat, müssen Primmodelle abzählbar sein. Weil nicht–isolierte Typen in geeigneten Modelle ausgelassen werden (10.1), werden in Primmodellen nur isolierte Typen realisiert.

Definition Ein Modell 𝔄 von T heißt atomar, wenn alle n–Tupel \overline{a} von Elementen von 𝔄 atomar sind. Das wiederum bedeutet, daß die Typen^{10}

tp(a_{1}, …, a_{n})

atomar sind.

Ein Tupel \overline{a} ist genau dann atomar, wenn es eine vollständige Formel erfüllt.

Satz 12.1 Ein Modell von T ist genau dann prim, wenn es abzählbar und atomar ist.

Beweis: Sei 𝔐_{0} abzählbar und atomar und 𝔐 ein beliebiges Modell von T. Wir konstruieren eine elementare Einbettung von 𝔐_{0} nach 𝔐 als Vereinigung einer aufsteigenden Folge von elementaren Abbildungen

f : A → B

zwischen endlichen Teilmengen A von M_{0} und B von M. Wir beginnen mit der leeren Abbildung, die elementar ist, weil 𝔐_{0} und 𝔐 elementar äquivalent sind. Es genügt zu zeigen, daß wir jedes f fortsetzen können auf jede vorgegebene Erweiterung A ∪ {a}. Wir zeigen zuerst, daß der Typ p(x) von a über A atomar (bezüglich der Theorie Th((𝔐_{0})_{A})) ist. Das heißt, daß p von einer L(A)–Formel π(x) erzeugt wird:^{11}

p(x) = ⟨ϕ(x, \overline{a})⟩_{A} = \{ψ(x) | ψ(x) L(A)–Formel, 𝔐_{0} ⊧ ∀x (π(x) → ψ(x))\}

Sei \overline{a} ein Tupel, das die Elemente von A aufzählt und ϕ(x, \overline{x}) eine L–Formel, die den Typ von a\overline{a} erzeugt, dann wird offensichtlich p(x) von ϕ(x, \overline{a}) erzeugt.

Das Bild f(p) von p unter f (vgl. S. 50) ist ein über B definierter atomarer Typ, der von ϕ(x, f(\overline{a})) erzeugt wird. Atomare Typen lassen sich immer realisieren (nämlich durch jede Realisierung der erzeugenden Formel). Sei b ∈ M eine Realisierung von f(p). Dann ist f ∪ {⟨a, b⟩} ein elementare Fortsetzung von f. □

10 tp(\overline{a}) = tp(\overline{a}/∅)

11ϕ(\overline{x}) heißt dann atomar, oder vollständig, über A.

Satz 12.2 Alle Primmodelle von T sind isomorph.

Beweis: Seien 𝔐_{0} und 𝔐′_{0} zwei Primmodelle. Weil Primmodelle atomar sind, können wir endliche elementare Abbildungen zwischen 𝔐_{0} und 𝔐′_{0} auf beliebig vorgegebene Elemente aus beiden Modellen fortsetzen. Weil 𝔐_{0} und 𝔐′_{0} abzählbar sind, folgt daraus (wie im Beweis von 11.2) die Isomorphie. □

Definition In T liegen die isolierten Typen dicht, wenn eine der beiden folgenden äquivalenten Bedingungen erfüllt ist:

1. Jede konsistente L–Formel ψ(x_{1}, …, x_{n}) gehört zu einem isolierten Typ p(x_{1}, …, x_{n}) ∈ S_{n}(T)

2. Jede konsistente L–Formel ψ(x_{1}, …, x_{n}) wird von einer vollständigen Formel ϕ(x_{1}, …, x_{n}) impliziert:

T ⊢ ∀\overline{x} (ϕ(\overline{x}) → ψ(\overline{x}))

Satz 12.3 T hat genau dann ein Primmodell, wenn die isolierten Typen dicht liegen.

Beweis: Konsistente Formeln ψ(\overline{x}) werden in allen Modellen realisiert. Wenn es ein atomares Modell gibt, wird ψ(\overline{x}) von einem atomaren Tupel \overline{a} realisiert. ψ(\overline{x}) gehört also zum atomaren Typ tp(ā).

𝔐_{0} ist genau dann atomar, wenn es für alle n die Formelmenge

Σ_{n}(x_{1}, …, x_{n}) = {¬ϕ(x_{1}, …, x_{n}) | ϕ(x_{1}, …, x_{n}) vollständig}

ausläßt. Wenn alle Σ_{n} lokal ausgelassen werden, gibt es also (nach der Folgerung aus 10.1) ein abzählbares atomares Modell. Σ_{n} wird genau dann lokal ausgelassen, wenn es für alle konsistenten ψ(x_{1}, …, x_{n}) eine vollständige Formel ϕ(x_{1}, …, x_{n}) gibt, für die T ⊬ ∀\overline{x} (ψ(\overline{x}) → ¬ϕ(\overline{x})). Weil ϕ(\overline{x}) vollständig ist, bedeutet das aber T ⊢ ∀\overline{x} (ϕ(\overline{x}) → ψ(\overline{x})). Σ_{n} wird also genau dann lokal ausgelassen, wenn die isolierten n–Typen dicht liegen. □

Beispiel: L besitzt für jedes s ∈ ^{<ω}2 ein einstelliges Prädikat P_{s}. Die Axiome von T drücken aus, daß die P_{s} das Universum binär zerlegen: (s durchläuft alle endlichen 0 –1–Folgen)

• ∀x P_{∅}(x)

• ∃x P_{s}(x)

• ∀x ((P_{s0}(x) ∨ P_{s1}(x)) ↔ P_{s}(x))

• ∀x ¬(P_{s0}(x) ∧ P_{s1}(x))

T ist eine vollständige Theorie mit Quantorenelimination. Weil es keine vollständigen Formeln gibt, gibt es auch kein Primmodell.

Definition Eine Familie von Formeln ϕ_{s}(\overline{x}), (s ∈ ^{<ω}2) heißt binärer Baum, wenn für alle s

a) ∀\overline{x} ((ϕ_{s0} ∨ ϕ_{s1}) → ϕ_{s})

b) ∀\overline{x} ¬(ϕ_{s0} ∧ ϕ_{s1})

Satz 12.4 Eine schmale Theorie hat keinen binären Baum von konsistenten Formeln. Wenn T keinen binären Baum von konsistenten Formeln hat, liegen die isolierten Typen dicht.

Tatsächlich gilt auch die Umkehrung der ersten Behauptung: Theorien ohne binäre Bäume von konsistenten Formeln sind schmal.

Beweis: (des Satzes) Sei (ϕ_{s}(x_{1}, …, x_{n})) ein binärer Baum von konsistenten Formeln. Dann ist für jedes η ∈ ^{ω}2 die Menge

\{ϕ_{s}(\overline{x}) | s ⊂ η\}

konsistent, läßt sich also zu einem p_{η}(\overline{x}) ∈ S_{n}(T) erweitern. Die p_{η}(\overline{x}) müssen alle verschieden sein, und T ist nicht schmal.

Wenn die isolierten Typen nicht dicht liegen, gibt es eine konsistente Formel ϕ(x_{1}, …, x_{n}), die von keiner vollständigen Formel impliziert wird. Solche Formeln nennen wir perfekt. Weil perfekte Formeln nicht vollständig sind, kann man sie in zwei „disjunkte“ konsistente Formeln zerlegen, die natürlich selbst wieder perfekt sind. So läßt sich ein binärer Baum aus perfekten Formeln konstruieren. □

ℵ_{1}–kategorische Theorien

13 Indiscernibles

Definition I sei eine lineare Ordnung und 𝔄 eine L–Struktur. Eine Familie (a_{i})_{i∈I} von Elementen von A heißt Folge von Indiscernibles, wenn für alle L– Formeln ϕ(x_{1}, …, x_{n}) und alle i_{1} < … < i_{n} und j_{1} < … < j_{n} aus I

𝔄 ⊧ ϕ(a_{i_{1}}, …, a_{i_{n}}) ↔ ϕ(a_{j_{1}}, …, a_{j_{n}}).

Wenn zwei der a_{i} gleich sind, müssen alle a_{i} gleich sein. Man nimmt also im allgemeinen an, daß die a_{i} paarweise verschieden sind.

Satz 13.1 Wenn T unendliche Modelle hat, hat T ein Modell mit einer Folge (a_{i})_{i∈I} von (verschiedenen) Indiscernibles. Die lineare Ordnung I läßt sich beliebig vorgeben.

Wir brauchen aus der Kombinatorik den Satz von Ramsey. Dabei verwenden wir die Notation [A]^{n} für die Menge aller n–elementigen Teilmengen von A.

Hilfssatz (Satz von Ramsey) Sei A unendlich, n ∈ ℕ. [A]^{n} sei zerlegt in die Klassen C_{1}, … C_{k}. Dann gibt es eine unendliche Teilmenge von A, deren n–elementige Teilmengen alle in derselben Klasse liegen.

Beweis: (von 13.1) Wir nehmen uns eine linear geordnete Menge C von neuen Konstanten, die isomorph zu I ist. Wir betrachten die Theorie

T_{C} = T ∪ \{¬c =^{.} d | c ≠ d ∈ C\} ∪ \{ϕ(\overline{c}) ↔ ϕ(d̄) | ϕ(\overline{x}) L–Formel, \overline{c}, d̄∈ C\}.

Dabei durchlaufen die \overline{c} und d̄ aufsteigend geordnete Tupel aus C. Wir haben zu zeigen, daß T_{C} konsistent ist. Dazu sei C_{0} eine endliche Teilmenge von C und Δ eine endliche Menge von L–Formeln. Es genügt zu zeigen, daß

T_{C_{0},Δ} = T ∪ \{¬c =^{.} d | c ≠ d ∈ C_{0}\} ∪ \{ϕ(\overline{c}) ↔ ϕ(d̄) | ϕ(\overline{x}) ∈ Δ, \overline{c}, d̄∈ C_{0}\}

konsistent ist. Wir können annehmen, daß die Elemente von Δ Formeln in den freien Variablen x_{1}, …, x_{n} sind und daß alle Tupel \overline{c} und d̄ dieselbe Länge n haben.

Jetzt sei 𝔐 ein unendliches Modell von T und A eine unendliche Teilmenge von M. Wir versehen A mit einer linearen Ordnung und definieren mit

\overline{a} ∼ \overline{b} ⇔ 𝔐 ⊧ ϕ(\overline{a}) ↔ ϕ(\overline{b}) für alle ϕ(x_{1}, …, x_{n}) ∈ Δ,

wobei \overline{a} und \overline{b} aufsteigend geordnete n–Tupel aus A, eine Äquivalenzrelation auf [A]^{n}, die höchstens 2^{|Δ|} viele Klassen hat. Nach dem Satz von Ramsey gibt es eine unendliche Teilmenge B von A, deren n–elementige Teilmengen alle in derselben Äquivalenzklasse liegen. Wir interpretieren die c ∈ C_{0} durch b_{c} in B, die ebenso geordnet sind wie die c. Dann ist (𝔐, b_{c})_{c∈C_{0}} ein Modell von T_{C_{0},Δ}. □

Lemma 13.2 Wenn T abzählbar ist und das Modell 𝔐 von einer wohlgeordneten Folge (a_{i}) von Indiscernibles erzeugt wird, werden über jeder abzählbaren Teilmenge von M nur abzählbar viele Typen realisiert.

Beweis: Wenn A = \{a_{i} | i ∈ I\}, hat jedes Element b von M die Form b = t(\overline{a}) für einen L–Term t und ein Tupel \overline{a} aus A. S sei eine abzählbare Teilmenge von M. Wir schreiben

S = \{t_{n}^{𝔐}(\overline{a}^{n}) | n ∈ ℕ\}.

Sei A_{0} = \{a_{i} | i ∈ I_{0}\} die (abzählbare) Menge der Elemente, die in den \overline{a}^{n} vorkommen. Dann ist jeder Typ tp(b/S) bestimmt durch tp(b/A_{0}), weil jede L(S)–Formel

ϕ(x, t_{n_{1}}^{𝔐}(a^{n_{1}}), …)

als L(A_{0})–Formel ϕ(x, t_{n_{1}}(a^{n_{1}}), …) aufgefaßt werden kann.

Der Typ von b = t(\overline{a}) über A_{0} wiederum hängt nur von t(\overline{x}) (abzählbar viele Möglichkeiten) und dem Typ tp(\overline{a}/A_{0}) ab. Wir schreiben \overline{a} = aī für ein Tupel ī aus I. Weil die a_{i} Indiscernibles sind, hängt der Typ nur vom quantorenfreien Typ tp_{qf}(ī/I_{0}) in der Struktur (I, <) ab. Dieser Typ wiederum von tp_{qf}(ī) (endlich viele Möglichkeiten) und von den Typen p(x) = tp_{qf}(i/I_{0}) der Elemente i von ī. Es gibt drei Arten solcher Typen:

1. i ist größer als alle Elemente von I_{0}

2. i ist ein Element i_{0} von I_{0}

3. Für ein i_{0} ∈ I_{0} ist i kleiner als i_{0} aber größer als alle Elemente von {j | j < i_{0}}.

Im ersten Fall liegt der Typ schon fest, in den anderen Fällen wird der Typ von i_{0} bestimmt. Das ergibt für jede Komponente von ī abzählbar viele Möglichkeiten. □ Definition Sei L eine Sprache. Eine Skolemtheorie T_{Sk}(L) ist eine Theorie in einer Spracherweiterung L_{Sk} mit folgenden Eigenschaften:

a) T_{Sk}(L) hat Quantorenelimination.

b) T_{Sk}(L) ist universell.

c) Jede L–Struktur läßt sich zu einem Modell von T_{Sk}(L) expandieren.

d) |L_{Sk}| ≤ max{|L|, ℵ_{0}}

Satz 13.3 Für jedes L gibt es eine Skolemtheorie.

Beweis: Wir definieren eine aufsteigende Folge von Sprachen

L = L_{0} ⊂ L_{1} ⊂ L_{2} ⊂ …,

indem wir für jede L_{i}–Formel ϕ(x_{1}, …, x_{n}, y) eine n–stellige Skolemfunktion f_{ϕ} einführen und L_{i+1} definieren als die Vereinigung von L_{i} und der Menge dieser Funktionszeichen. L_{Sk} ist die Vereinigung allerL_{i}. Wir setzen

T_{Sk} = \{∀\overline{x} (∃y ϕ(\overline{x}, y) → ϕ(\overline{x}, f_{ϕ}(\overline{x}))) | ϕ(\overline{x}, y) L_{Sk}–Formel\}.
□

Folgerung 13.4 Wenn T abzählbar ist und unendliche Modelle hat, hat T in jeder Mächtigkeit ein Modell, in dem über jeder abzählbaren Teilmenge nur abzählbar viele Typen realisiert werden.

Beweis: Betrachte die Theorie T^{∗} = T ∪ T_{Sk}(L). Es ist klar, daß T^{∗} abzählbar ist, ein unendliches Modell hat und Quantorenelimination hat.

Behauptung: T^{∗} ist universell

Beweis: Modulo T_{Sk}(L) ist jedes Axiom ϕ von T zu einer quantorenfreien L_{Sk}– Aussage ϕ^{∗} äquivalent. T^{∗} ist also äquivalent zu der universellen Theorie {ϕ^{∗} | ϕ ∈ T } ∪ T_{Sk}(L).

Sei I eine Wohlordnung der Mächtigkeit κ und 𝔑^{∗} ein Modell von T^{∗} mit Indiscernibles (a_{i})_{i∈I}. Weil T^{∗} universell ist, ist die von den a_{i} erzeugte Unterstruktur 𝔐^{∗} ein Modell von T^{∗}. 𝔐^{∗} hat die Mächtigkeit κ. Weil T^{∗} Quantorenelimination hat, ist 𝔐^{∗} ≺ 𝔑^{∗}, also ist die Familie (a_{i}) auch indiscernible in 𝔐^{∗}. Mit 13.2 schließen wir, daß in 𝔐^{∗} über jeder abzählbaren Menge nur abzählbar viele Typen realisiert sind. Das gleiche gilt dann für 𝔐 = 𝔐^{∗} ↾ L. □

14 ω–stabile Theorien

Wir halten in diesem Abschnitt eine abzählbare, vollständige Theorie ohne endliche Modelle fest.

Definition T heißt ω–stabil, wenn für alle 𝔐 ⊧ T und alle abzählbaren Teilmengen A ⊂ M die Menge S(A) der Typen über A abzählbar ist.

Satz 14.1 Wenn T in einer überabzählbaren Kardinalzahl κ kategorisch ist, ist T ω–stabil.

Beweis: Sei 𝔑 ein Modell mit einer abzählbaren Parametermenge A, über der es überabzählbar viele Typen gibt. Seien (b_{i})_{i∈I} ℵ_{1}–viele Elemente mit paarweise verschiedenen Typen über A. (Wir können annehmen, daß alle Typen über A in 𝔑 realisiert sind.) Wir wählen zuerst eine elementare Unterstruktur 𝔐_{0}, die A und die b_{i} enthält und die Mächtigkeit ℵ_{1} hat. Dann wählen wir eine elementare Erweiterung 𝔐 von 𝔐_{0} der Mächtigkeit κ. 𝔐 ist ein Modell der Mächtigkeit κ, in dem über einer abzählbaren Menge überabzählbar viele Typen realisiert sind. Nach 13.4 hat T auch ein Modell, in dem es so etwas nicht gibt. T kann also nicht κ–kategorisch sein. □

Definition T heißt total transzendent, wenn es in keinem Modell 𝔐 von T einen binären Baum von konsistenten L(M)–Formeln gibt.

Satz 14.2 ω–stabile Theorien sind total transzendent.

Für abzählbare Theorien gilt auch die Umkehrung (16.1).

Beweis: Sei 𝔐 ein Modell mit einem binären Baum von konsistenten L(M)–Formeln. Sei A die Menge der in den Formeln des Baumes vorkommenden Parameter. Dann gibt es (siehe 12.4) über A überabzählbar viele Typen. □

Definition Ein Modell 𝔐 von T heißt Primerweiterung der Teilmenge A, wenn sich jede elementare Abbildung A → 𝔑 zu einer elementaren Einbettung 𝔐 → 𝔑 fortsetzen läßt.

[figure: A; 𝔐; 𝔑; id_{A}]

Satz 14.3 Wenn T total transzendent ist, hat jede Teilmenge eines Modells von T eine Primerweiterung. Primerweiterungen sind atomar.

Beweis: Sei 𝔐 ein Modell von T und A eine Teilmenge von M. Wir nennen ein n–Tupel \overline{b} ∈ M atomar über A, wenn der Typ tp(\overline{b}/A) atomar ist.

Wir konstruieren jetzt eine elementare Unterstruktur 𝔐_{0} ≺ 𝔐, die A enthält und konstruktibel über A ist. Das heißt, daß für eine Ordinalzahl λ

M_{0} = A ∪ {a_{α} | α < λ},

wobei jeweils a_{α} atomar über

A_{α} = A ∪ {a_{β} | β < α}

ist. Dazu nehmen wir an, daß (a_{α})_{α<λ} eine Konstruktion ist, die sich nicht mehr um ein Element a_{λ} ∈ M \ A_{λ} verlängern läßt, und zeigen mit Tarskis Test, daß A_{λ} Universum einer elementaren Unterstruktur 𝔐_{0} ist. Sei dazu ϕ(x) eine L(A_{λ})–Formel und 𝔐 ⊧ ∃x ϕ(x). Weil die isolierten Typen über A_{λ} dicht liegen (14.4), gibt es einen isolierten Typ p(x) ∈ S(A_{λ}), der ϕ(x) enthält. Sei b eine Realisierung von p(x) in 𝔐. Wir könnten mit a_{λ} = b unsere Konstruktion fortsetzen, also ist b ∈ A_{λ}.

Konstruktible Erweiterungen sind immer prim. Denn sei f : A → 𝔑 eine elementare Abbildung. Wir definieren induktiv eine aufsteigende Folge von elementaren Abbildungen f_{α} : A_{α} ∪ {a_{α}} → 𝔑. Wenn die f_{β} für alle β < α definiert sind, ist ihre Vereinigung^{1} eine elementare Abbildung f′_{α} : A_{α} → 𝔑. Sei p(x) = tp(a_{α}/A_{α}). Weil p isoliert ist, ist q(x) = f′_{α}(p) (über dem Bild von f′_{α}) isoliert. Also gibt es eine Realisierung b von q(x) in 𝔑. Wir setzen f_{α} = f′_{α} ∪ {⟨a_{α}, b⟩}. Schließlich ist die Vereinigung aller f_{α} (α < λ) eine elementare Einbettung 𝔐_{0} → 𝔑.

Konstruktible Erweiterungen sind atomar. Sei nämlich \overline{a} ein Tupel von Elementen aus M_{0}. Wir wollen zeigen, daß \overline{a} atomar über A ist. Es ist klar, daß wir annehmen können, daß die Elemente von \overline{a} paarweise verschieden sind und nicht alle zu A gehören. Außerdem kommt es auf die Reihenfolge der Elemente nicht an. Also können wir annehmen, daß

\overline{a} = a_{α}\overline{b}

für ein Tupel \overline{b} aus A_{α}. Sei ϕ(x, \overline{c}) eine Formel, die a_{α} über A_{α} isoliert. Dann ist a_{α} auch atomar über A ∪ \{\overline{b}\overline{c}\}. Wenn wir induktiv vorgehen, wissen wir, daß \overline{b}\overline{c} atomar über A ist. Lemma 14.5 liefert, daß a_{α}\overline{b}\overline{c} atomar über A ist^{2}, woraus wiederum folgt, daß \overline{a} = a_{α}\overline{b} atomar über A ist.

Weil es mindestens eine konstruktible Erweiterung 𝔐_{0} von A gibt und weil alle Primerweiterungen von A in 𝔐_{0} stecken^{3}, sind alle Primerweiterungen atomar. □

Lemma 14.4 Wenn T total transzendent ist, liegen über jeder Parametermenge die isolierten Typen dicht.

1 Für f′_{0} nehmen wir f.

2 Wir wenden das Lemma auf (𝔐_{0})_{A} an.

3Sie sind über A isomorph zu elementaren Unterstrukturen von 𝔐_{0}.

Beweis: Sei A eine Teilmenge von 𝔐. Th(𝔐_{A}) hat keinen binären Baum von konsistenten Formeln (in einer Variablen). Daraus folgt, daß in Th(𝔐_{A}) die isolierten 1– Typen dicht liegen (12.4). □

Lemma 14.5 a und b seien zwei endliche Tupel von Elementen eines Modells 𝔐. Dann ist tp(a, b) genau dann atomar, wenn tp(a/b) und tp(b) atomar sind.

Beweis: Zuerst nehmen wir an, daß tp(a, b) von ϕ(x, y) isoliert wird. Dann wird, erstens, tp(a/b) von ϕ(x, b) isoliert. Denn einerseits ist ϕ(x, b) ∈ tp(a/b). Wenn andererseits ρ(x, b) ∈ tp(a/b), ist ρ(x, y) ∈ tp(a, b) und es folgt 𝔐 ⊧ ∀x, y (ϕ(x, y) → ρ(x, y)) und darum 𝔐 ⊧ ∀x (ϕ(x, b) → ρ(x, b)). Zweitens wird p(y) = tp(b) von ∃x ϕ(x, y) isoliert. Denn einerseits ist ∃x ϕ(x, y) ∈ p(y). Andererseits, wenn σ(y) ∈ p(y), so ist 𝔐 ⊧ ∀x, y (ϕ(x, y) → σ(y)), was bedeutet, daß 𝔐 ⊧ ∀y (∃xϕ(x, y) → σ(y)).

Dann sei, umgekehrt, tp(a/b) isoliert von ρ(x, b) und p(y) = tp(b) isoliert von σ(y). Dann wird tp(a, b) von ρ(x, y) ∧ σ(y) isoliert. Denn einerseits ist klar, daß ρ(x, y) ∧ σ(y) ∈ tp(a, b). Sei andererseits ϕ(x, y) ∈ tp(a, b). Dann gehört ϕ(x, b) zu tp(a/b) und es folgt 𝔐 ⊧ ∀x (ρ(x, b) → ϕ(x, b)). Also ist

∀x (ρ(x, y) → ϕ(x, y)) ∈ p(y)

und es folgt

𝔐 ⊧ ∀y (σ(y) → ∀x (ρ(x, y) → ϕ(x, y))).

Also 𝔐 ⊧ ∀x, y (ρ(x, y) ∧ σ(y) → ϕ(x, y)). □

Satz 14.6 (Lachlan) T sei total transzendent und 𝔐 ein überabzählbares Modell von T. Dann hat 𝔐 für jedes κ ≥ |𝔐| eine elementare Erweiterung der Mächtigkeit κ, in der jede abzählbare Menge von L(M)–Formeln ausgelassen wird, die in 𝔐 ausgelassen wird.

Beweis: Wir nennen eine L(M)–Formel ϕ(x) überabzählbar, wenn die Erfüllungsmenge

ϕ(𝔐) = {m ∈ M | 𝔐 ⊧ ϕ(m)}

überabzählbar ist. Weil es keinen binären Baum aus überabzählbaren Formeln gibt, gibt es eine minimale überabzählbare Formel ϕ_{0}(x). Das heißt, daß für jede L(M)–Formel ψ(x) entweder ϕ_{0}(x) ∧ ψ(x) oder ϕ_{0}(x) ∧ ¬ψ(x) höchstens abzählbar ist. Man sieht nun leicht, daß

p(x) = {ψ(x) | ϕ_{0}(x) ∧ ψ(x) überabzählbar}

ein Typ aus S(M) ist.

p(x) enthält nur überabzählbare Formeln, also keine Formel der Form x =^{.} a für ein a aus M. p(x) wird also nicht in M realisiert. Andererseits wird jede abzählbare Teilmenge Π(x) von p(x) in 𝔐 realisiert. Denn die ϕ_{0}(𝔐) \ ψ(𝔐) sind für alle ψ(x) ∈ Π(x) höchstens abzählbar. Die Elemente von ϕ_{0}(𝔐), die außerhalb der Vereinigung dieser Mengen liegen, realisieren Π(x).

Sei a eine Realisierung von p(x) in einer (echten) elementaren Erweiterung 𝔑. Wegen 14.3 können wir annehmen, daß 𝔑 atomar über M ∪ {a} ist.

Wir halten ein b ∈ N fest. Sei q(y) = tp(b/M ∪ {a}) durch χ(a, y) isoliert (χ(x, y) eine L(M)–Formel). Wenn b eine L(M)–Formel σ(y) erfüllt, ist also 𝔑 ⊧ ∀y (χ(a, y) → σ(y)). Die Formel

σ^{∗}(x) = ∀y (χ(x, y) → σ(y))

gehört also zu p(x). Wir vermerken außerdem, daß auch ∃y χ(x, y) zu p(x) gehört.

Sei nun Σ(y) eine abzählbare Menge von L(M)–Formeln, die alle auf b zutreffen. Wir wählen uns ein a′ ∈ M, das alle σ^{∗}(x) (σ ∈ Σ) und dazu ∃y χ(x, y) erfüllt. Dazu gibt es dann ein b′ ∈ M mit 𝔐 ⊧ χ(a′, b′). Die Gültigkeit von σ^{∗}(a′) hat zu Folge, daß 𝔐 ⊧ σ(b′). Also wird Σ(y) von b′ realisiert.

Wir haben gezeigt, daß 𝔐 eine echte elementare Erweiterung hat, in der keine neuen abzählbaren Mengen von L(M)–Formeln realisiert werden. Durch Iteration erhält man beliebig lange Ketten von elementaren Erweiterungen mit der behaupteten Eigenschaft. □

15 Vaughtsche Paare

Wir halten in diesem Abschnitt eine abzählbare, vollständige Theorie T ohne endliche Modelle fest.

Definition Eine L–Struktur 𝔐 heißt ω–homogen, wenn sich jede elementare Abbildung zwischen endlichen Teilmengen von 𝔐 auf jede endliche Erweiterung des Definitionsbereichs fortsetzen läßt.

𝔐 ist genau dann ω–homogen, wenn für alle endlichen Teilmengen A, alle elementaren Abbildungen f : A → M und alle p(x) ∈ S(A)

p in 𝔐 realisiert ⇒ f(p) in 𝔐 realisiert .

Satz 15.1 T sei eine vollständige, abzählbare Theorie ohne endliche Modelle.

1. Jedes abzählbare Modell von T hat eine abzählbare, ω–homogene elementare Erweiterung.

2. Die Vereinigung einer elementaren Kette von ω–homogenen Modellen ist wieder ω–homogen.

3. Zwei ω–homogene abzählbare Modelle von T sind isomorph, wenn sie dieselben n–Typen realisieren.

Beweis:

1. Sei 𝔐_{0} ein abzählbares Modell von T. Die abzählbar vielen Typen

{f(tp(a/A)) | A ⊂ M_{0} endlich, f : A → M_{0} elementar}

realisieren wir in der abzählbaren elementaren Erweiterung 𝔐_{1}. Dann wenden wir auf 𝔐_{1} dasselbe Verfahren an, etc. Wir erhalten eine elementare Kette

𝔐_{0} ≺ 𝔐_{1} ≺ …,

deren Vereinigung offensichtlich ω–homogen ist. Man vergleiche den ähnlichen Beweis von 11.8.

2. Klar

3. Wie der Beweis von 11.7. □

Definition Zwei Modelle 𝔐 ≺ 𝔑 von T bilden ein Vaughtsches Paar^{4} für die L–Formel ϕ(x), wenn

a) 𝔐 ≠ 𝔑, b) ϕ(𝔐) unendlich ist,

4Man vergleiche die Definition auf Seite 68.

c) ϕ(𝔐) = ϕ(𝔑)

Sei 𝔑 ein Modell von T, in dem ϕ(𝔑) unendlich ist, aber kleinere Mächtigkeit als 𝔑 hat. Der Satz von Löwenheim–Skolem liefert uns eine elementare Unterstruktur 𝔐 von 𝔑, die ϕ(𝔐) enthält und die gleiche Mächtigkeit wie ϕ(𝔐) hat. 𝔐 ≺ 𝔑 ist ein Vaughtsches Paar für ϕ(x). Der nächste Satz zeigt, daß man diese Überlegung umkehren kann.

Satz 15.2 (Vaughtscher Zwei-Kardinalzahlsatz) Wenn T ein Vaughtsches Paar für ϕ(x) hat, hat T ein Modell 𝔐 der Mächtigkeit ℵ_{1}, in dem ϕ(𝔐) abzählbar ist.

Beweis: Sei P ein neues Prädikat. Man kann leicht eine L(P)–Theorie T_{VP} angeben, deren Modelle (𝔑, M) aus einer L–Struktur 𝔑 und einer Teilmenge M bestehen, die Universum einer elementaren Unterstruktur 𝔐 ist und zusammen mit 𝔑 ein Vaughtsches Paar für ϕ(x) bildet. Wir können daraus schließen, daß T ein abzählbares Vaughtsches Paar 𝔐_{0} ≺ 𝔑_{0} (für ϕ(x)) hat.

Jetzt konstruieren wir eine elementare Kette

(𝔑_{0}, M_{0}) ≺ (𝔑_{1}, M_{1}) ≺ …

von abzählbaren Vaughtschen Paaren, mit dem Ziel, daß beide Komponenten des Vereinigungspaares

𝔐 ≺ 𝔑

ω–homogen sind und dieselben n–Typen realisieren. Wenn (𝔑_{i}, M_{i}) gegeben ist, wählen wir zuerst eine abzählbare elementare Erweiterung (𝔑′, M′) mit: in 𝔐′ werden alle n–Typen realisiert, die in 𝔑_{i} realisiert sind. Dann wählen wir, wie im Beweis von 15.1 (1) eine abzählbare elementare Erweiterung (𝔑_{i+1}, M_{i+1}) von (𝔑′, M′), in der sowohl 𝔑_{i+1} als auch 𝔐_{i+1} ω–homogen sind.

Aus 15.1 (3) folgt, daß 𝔐 und 𝔑 isomorph sind.

Dann konstruieren wir eine stetige elementare Kette

𝔐^{0} ≺ 𝔐^{1} ≺ … ≺ 𝔐^{α} ≺ … (α < ℵ_{1})

mit (𝔐^{α+1}, M^{α}) ≅ (𝔑, M) für alle α. Wir starten mit 𝔐^{0} = 𝔐. Wenn 𝔐^{α} konstruiert ist, wählen wir einen Isomorphismus 𝔐 → 𝔐^{α} und setzen ihn zu einem Isomorphismus 𝔑 → 𝔐^{α+1} fort (siehe 1.7). Für abzählbare Limeszahlen λ nehmen für 𝔐^{λ} die Vereinigung der 𝔐^{α} (α < λ). 𝔐^{λ} ist abzählbar, ω–homogen und erfüllt die gleichen n–Typen, wie 𝔐. Also ist 𝔐^{λ} ≅ 𝔐.

Schließlich setzen wir

\overline{𝔐} = ⋃_{α<ℵ_{1}} 𝔐^{α}.

Weil die 𝔐^{α} echt wachsen, hat \overline{𝔐} die Mächtigkeit ℵ_{1}. Weil ϕ(𝔐^{α}) = ϕ(𝔐^{0}) für alle α, ist ϕ(\overline{𝔐}) = ϕ(𝔐^{0}) abzählbar. □

Folgerung 15.3 Wenn T total transzendent ist und ein Vaughtsches Paar für ϕ(x) hat, hat T für alle überabzählbaren κ ein Modell der Mächtigkeit κ, in dem ϕ(𝔐) abzählbar ist.

Beweis: Sei 𝔐 ein Modell der Mächtigkeit ℵ_{1} mit abzählbaren A = ϕ(𝔐). Sei 𝔑 eine elementare Erweiterung der Mächtigkeit κ wie in 14.6. Die Formelmenge {ϕ(x)} ∪ {x ≠^{.} a | a ∈ A} wird in 𝔐 und darum auch in 𝔑 ausgelassen. Es folgt ϕ(𝔑) = ϕ(𝔐). □

Definition T hat ein Vaughtsches Paar, wenn es ein Modell 𝔐 gibt und eine L(M)–Formel ϕ(x, \overline{a}), für die Th(𝔐, \overline{a}) ein Vaughtsches Paar^{5} hat.

T hat also genau dann ein Vaughtsches Paar, wenn es zwei Modelle 𝔐 ≺ 𝔑 von T gibt und eine L(M)–Formel ϕ(x) mit

a) 𝔐 ≠ 𝔑,

b) ϕ(𝔐) unendlich ist,

c) ϕ(𝔐) = ϕ(𝔑)

Folgerung 15.4 Wenn T in einer überabzählbaren Mächtigkeit kategorisch ist, hat T kein Vaughtsches Paar.

Beweis: Wenn T in einer überabzählbaren Mächtigkeit κ kategorisch ist, ist T total transzendent (14.1). Wenn T ein Vaughtsches Paar für ϕ(x) hätte, gäbe es ein Modell 𝔐 der Mächtigkeit κ, in dem ϕ(𝔐) abzählbar ist. Andererseits gibt es aber immer ein Modell 𝔐 der Mächtigkeit κ, in dem die Erfüllungsmenge aller L(M)–Formeln entweder endlich ist oder ebenfalls die Mächtigkeit κ hat. Man konstruiert 𝔐 als Vereinigung einer stetigen elementaren Kette (𝔐_{α})_{α<κ} von Modellen der Mächtigkeit κ, wobei 𝔐_{α+1} so gewählt ist, daß für alle L(M_{α})– Formeln ϕ(x) mit unendlicher Erfüllungsmenge

ϕ(𝔐_{α}) ⊊ ϕ(𝔐_{α+1}).

T wäre also nicht κ–kategorisch. □

Wir werden im nächsten Kapitel sehen, daß ein κ–kategorisches T auch ℵ_{1}–kategorisch ist (16.4). Für 15.4 hätte es also genügt zu zeigen, daß ℵ_{1}– kategorische Theorien keine Vaughtschen Paare haben.

5Im Sinne der Definition auf Seite 66.

16 Morley abwärts

Wir werden im nächsten Kapitel zeigen, daß eine total transzendente Theorie ohne Vaughtsche Paare kategorisch in jeder überabzählbaren Mächtigkeit κ ist (18.3). Daraus folgt insbesondere, daß κ–kategorische Theorien ℵ_{1}–kategorisch sind. Wir geben hier einen separaten Beweis dafür.

Wir fixieren wieder eine abzählbare vollständige Theorie T ohne endliche Modelle.

Definition Sei κ eine unendliche Kardinalzahl. T heißt κ–stabil , wenn es in jedem Modell von T über jeder Parametermenge, die höchstens die Mächtigkeit κ hat, höchstens κ–viele Typen gibt.

ℵ_{0}-stabil ist ein Synonym für ω–stabil.

Lemma 16.1 Wenn T total transzendent ist, ist T κ–stabil für alle κ.

Beweis: Nehmen wir an, daß es über der Menge A mehr als κ–viele Typen gibt. Eine große Formel ist eine L(A)–Formel, die zu mehr all κ–vielen Typen aus S(A) gehört. Unsere Annahme bedeutet, daß x =^{.} x groß ist. Wenn wir zeigen können, daß sich jede große Formel in zwei große Formeln zerlegen läßt, können wir einen binären Baum aus großen Formeln konstruieren und sind fertig. Sei also ϕ groß. Weil jede kleine Formel höchstens zu κ–vielen Typen gehört, und weil es höchstens κ–viele Formeln gibt, gibt es höchstens κ–viele Typen, die kleine Formeln enthalten. ϕ gehört also zu zwei verschiedenen Typen p und q, die nur große Formeln enthalten. Wir trennen p und q durch ψ ∈ p und ¬ψ ∈ q und haben ϕ zerlegt in ϕ ∧ ψ und ϕ ∧ ¬ψ. □

Definition Ein Modell 𝔐 der Mächtigkeit κ heißt saturiert, wenn in 𝔐 alle Typen über Parametermengen, die eine kleinere Mächtigkeit als κ haben, realisiert sind.

Lemma 16.2 Elementar äquivalente, saturierte Strukturen von gleicher Mächtigkeit sind isomorph.

Beweis: 𝔄 und 𝔅 seien elementar äquivalent, saturiert und beide von der Mächtigkeit κ. Wir wählen Aufzählungen^{6} (a_{α})_{α<κ} und (b_{α})_{α<κ} von A und B und konstruieren eine aufsteigende Folge von elementaren Abbildungen f_{α} : A_{α} → B_{α}. Wenn die f_{β} schon für alle β < α konstruiert sind, bilden wir zunächst die Vereinigung dieser f_{β} und nennen sie f_{α}^{∗}. f_{α}^{∗} : A_{α}^{∗} → B_{α}^{∗} ist elementar^{7}. Wir sehen aus der Konstruktion, daß A_{α}^{∗} und B_{α}^{∗} höchstens die Mächtigkeit |α|, also eine kleinere Mächtigkeit als κ haben. Wir schreiben α = λ + n (wie auf S. 85) und unterscheiden zwei Fälle: n = 2i. Dann betrachten wir p(x) = tp(a_{λ+i}/A_{α}^{∗}). Wir realisieren f_{α}^{∗}(p) durch b ∈ N und setzen

6Kardinalzahlen sind Ordinalzahlen. Vgl. S. 84.

7Wenn α = 0 ist f_{α}^{∗} = ∅ elementar, weil 𝔄 und 𝔅 elementar äquivalent sind.

f_{α} = f_{α}^{∗} ∪ {⟨a_{λ+i}, b⟩}.

n = 2i + 1. Wir finden in der gleichen Weise eine Fortsetzung

f_{α} = f_{α}^{∗} ∪ {⟨a, b_{λ+i}⟩}.

Die Vereinigung der f_{α}, (α < κ), ist der gesuchte Isomorphismus zwischen 𝔄 und 𝔅. □

Satz 16.3 T ist genau dann κ–kategorisch, wenn alle Modelle der Mächtigkeit κ saturiert sind.

Beweis: Für κ = ℵ_{0} folgt der Satz aus (dem Beweis von) 11.1. Nehmen wir also an, daß κ überabzählbar ist.

Wenn alle Modelle der Mächtigkeit κ saturiert sind, ist wegen 16.2 T κ–kategorisch. Sei, umgekehrt, T κ–kategorisch. Dann ist T total transzendent (14.1 und 14.2) und daher κ–stabil (16.1).

Daraus folgt, daß T für alle λ < κ ein λ^{+}–saturiertes Modell 𝔐 der Mächtigkeit κ hat. Um das einzusehen konstruieren wir eine stetige elementare Kette

𝔐_{0} ≺ 𝔐_{1} … ≺ 𝔐_{α} ≺ … (α < λ^{+}),

aus Modellen von T, die die Mächtigkeit κ haben. Dabei realisieren wir in 𝔐_{α+1} alle p ∈ S(M_{α}). Das ist möglich, weil S(M_{α}) die Mächtigkeit κ hat und T κ– stabil ist. Schließlich sei das Modell 𝔐 die Vereinigung dieser Kette. Dann ist 𝔐 λ^{+}–saturiert in folgendem Sinn: Jeder Typ über einer Teilmenge A ⊂ M, die eine kleinere Mächtigkeit als λ^{+} hat^{8}, wird in 𝔐 realisiert. Denn wenn a ∈ A in M_{α(a)} liegt, ist Λ = ⋃_{a∈A} α(a) ein Anfangsstück von λ^{+}, das höchstens die Mächtigkeit λ hat. Λ hat also eine obere Schranke μ < λ^{+}. Es folgt A ⊂ M_{μ}. Alle Typen über A werden in 𝔐_{μ+1} realisiert.

Weil T κ–kategorisch ist, sind alle Modelle der Mächtigkeit κ λ^{+}–saturiert für alle λ < κ und daher saturiert.

□

Folgerung 16.4 Wenn T κ–kategorisch ist, ist T auch ℵ_{1}–kategorisch.

Die Folgerung ist die Abwärts–Hälfte des Satzes von Morley, 18.4.

8Also höchstens die Mächtigkeit λ hat.

Beweis: Wenn T nicht ℵ_{1}–kategorisch ist, gibt es ein Modell 𝔐, der Mächtigkeit ℵ_{1}, das nicht saturiert ist. Es gibt also einen Typ p über einer abzählbaren Teilmenge von M, der in 𝔐 nicht realisiert wird. Wegen 14.1 und 14.2 können wir annehmen, daß T total transzendent ist. Satz 14.6 liefert uns dann eine elementare Erweiterung 𝔑 von 𝔐, die die Mächtigkeit κ hat und alle abzählbaren Formelmengen ausläßt, die auch in 𝔐 ausgelassen werden. Insbesondere wird p nicht realisiert. 𝔑 ist also nicht saturiert, und T kann nicht κ–kategorisch sein. □

Die Baldwin–Lachlan Theorie

Wir fixieren eine abzählbare vollständige Theorie T ohne endliche Modelle.

17 Streng minimale Theorien

Sei 𝔐 eine Struktur und A eine Teilmenge von M. Eine Menge der Form ϕ(𝔐) für eine L(A)–Formel ϕ(x) heißt A–definierbar.

Definition Sei 𝔐 eine Struktur und A eine Teilmenge von M. Ein Element a heißt algebraisch über A, wenn a Element einer endlichen A–definierbaren Menge ist. acl(A), der algebraische Abschluß von A, ist die Menge aller über A algebraischen Elemente von 𝔐.

In algebraisch abgeschlossenen Körpern ist a ∈ acl(A) genau dann wenn a algebraisch (im Sinne der Körpertheorie) über dem von A erzeugten Körper ist. Das liegt an der Quantorenelimination von T_{AAK}.

Der algebraische Abschluß von A wird nicht größer, wenn man zu einer elementaren Erweiterung von 𝔐 übergeht. Denn eine L(A)–Formel, die in 𝔐 eine endliche Menge definiert^{1}, definiert in jeder elementaren Erweiterung die gleiche Menge. Man sieht leicht, daß |acl(A)| ≤ max{|L|, |A|, ℵ_{0}} (vgl. 6.1).

Wir nennen einen Typ tp(a/A) algebraisch, wenn a algebraisch über A ist. p(x) ist genau dann algebraisch, wenn p eine algebraische Formel ϕ(x) enthält. Wenn man ϕ(x) so wählt, daß ϕ(𝔐) minimal ist, wird p(x) von ϕ(x) isoliert. Die Zahl der Elemente von ϕ(𝔐) nennt man den Grad oder die Multiplizität mult(p) von p.

Lemma 17.1 Sei p ∈ S(A) nicht algebraisch und A ⊂ B. Dann hat p eine nicht–algebraische Erweiterung q ∈ S(B).

1Wir nennen eine solche Formel algebraisch.

Beweis:

q_{0}(x) = p(x) ∪ {¬ψ(x) | ψ(x) algebraische L(B)–Formel}

ist endlich erfüllbar. Denn sonst gibt es ein ϕ(x) ∈ p(x) und algebraische L(B)– Formeln ψ_{1}(x) … ψ_{n}(x) mit

𝔐 ⊧ ∀x (ϕ(x) → ψ_{1}(x) ∨ … ∨ ψ_{n}(x)).

Dann müßte aber auch ϕ(x) endlich sein. Jetzt wählen wir für q einfach einen Typ, der q_{0} enthält. □

Bemerkung p ∈ S(A) ist genau dann algebraisch, wenn p in allen elementaren Erweiterungen von 𝔐 nur von endliche vielen (nämlich mult(p) vielen) Elementen realisiert wird.

Beweis: Nehmen wir an, daß p ∈ S(A) nicht algebraisch ist und daß wir schon Realisierungen b_{1}, …, b_{n} gefunden haben. Wir setzen p zu einem nicht–algebraischen Typ q ∈ S(A ∪ {b_{1}, …, b_{n}}) fort und wählen für b_{n+1} eine Realisierung von q. b_{n+1} ist nicht algebraisch über A ∪ {b_{1}, …, b_{n}}, insbesondere verschieden von b_{1}, …, b_{n}. □

Lemma 17.2 𝔐 und 𝔑 seien elementar äquivalente Strukturen und f : A → B eine elementare Bijektion zwischen zwei Teilmengen. Dann setzt sich f zu einer elementaren Bijektion zwischen acl(A) und acl(B) fort.

Beweis: Sei g : A′ → B′ eine maximale Fortsetzung von f auf zwei Teilmengen von acl(A) und acl(B). Sei a ∈ acl(A). Weil a algebraisch über A′ ist, ist a atomar über A′. Wir können also den Typ g(tp(a/A′)) in 𝔑 – durch b ∈ acl(B) – realisieren und erhalten eine Fortsetzung g ∪ {⟨a, b⟩} von g. Es folgt a ∈ A′. g ist also auf ganz acl(A) definiert. Ebenso sieht man, daß g surjektiv ist. □

Definition Sei X eine Menge und cl : 𝔓(X) → 𝔓(X). cl ist ein Abschlußoperator im Sinne von van der Waerden (oder ein Matroid), wenn für alle A ⊂ X und a, b ∈ X

a) A ⊂ cl(A)

b) cl(A) ist die Vereinigung aller cl(A′), wobei A′ alle endlichen Teilmengen von A durchläuft.

c) cl(cl(A)) = cl(A)

d) Austauscheigenschaft .

a ∈ cl(Ab) \ cl(A) ⇒ b ∈ cl(Aa)

Bemerkung Wenn X das Universum einer Struktur ist, hat acl die Eigenschaften a), b) und c).

Beweis: Die Eigenschaften a) und b) sind klar. Für c) sei c algebraisch über b_{1}, …, b_{n} und die b_{i} algebraisch über A. Wir haben zu zeigen, daß c algebraisch über A ist. c erfülle die algebraische Formel ϕ(x, b_{1}, …, b_{n}), die b_{i} algebraische L(A)– Formeln ϕ_{i}(y). Nehmen wir an, daß ϕ(x, b_{1}, …, b_{n}) von genau k Elementen erfüllt wird. Die L(A)–Formel

∃ y_{1} … y_{n}(∃^{≤k}zϕ(z, y_{1}, …, y_{n}) ∧ ϕ(x, y_{1}, …, y_{n}))

ist dann algebraisch und wird von c erfüllt. □

Definition T heißt streng minimal, wenn in allen Modellen von T alle definierbaren Teilmengen endlich oder coendlich sind.

Beispiele: Die folgenden Theorien sind streng minimal.

• T_{∞}, die Theorie der unendlichen Mengen. In M sind über der endlichen Parametermenge A nur die Teilmengen S von A und ihre Komplemente M \ S definierbar.

• Für einen Körper K die Theorie der unendlichen K–Vektorräume. Über der endlichen Parametermenge A sind genau die endlichen Teilmengen des von A erzeugten Unterraums und ihre Komplemente definierbar.

• Die Theorien T_{AAK_{0}} und T_{AAK_{p}} der algebraisch abgeschlossenen Körper fester Charakteristik. Definierbare Mengen sind boolesche Kombinationen von Nullstellenmengen {a ∈ K | p(a) = 0} von Polynomen p(X) ∈ K[X]. Nullstellenmengen sind entweder endlich oder, wenn p = 0, gleich K.

Bemerkung T ist genau dann streng minimal, wenn es über jeder Parametermenge genau einen nicht–algebraischen Typ gibt.

Beweis: Der Beweis von Lemma 17.1 zeigt auch, daß sich jede nicht–algebraische L(A)–Formel zu einem nicht–algebraischen Typ q ∈ S(A) fortsetzen läßt. Daraus folgt leicht die Behauptung. □

Wenn T streng minimal ist, ist

|S(A)| ≤ |acl(A)| + 1.

Streng minimale Theorien sind also λ–stabil für alle λ und total transzendent. Wenn ϕ(𝔐) koendlich ist und 𝔑 eine echte elementare Erweiterung von 𝔐, ist auch ϕ(𝔑) eine echte Erweiterung von ϕ(𝔐). Streng minimale Theorien können also keinen Vaughtschen Paare haben.

Lemma 17.3 In Modellen einer streng minimalen Theorie definiert der algebraische Abschluß eine Matroidstruktur.

Beweis: Sei a nicht algebraisch über b und b nicht algebraisch über ∅. Wegen der obigen Bemerkung haben alle derartigen Paare ab denselben Typ p(x, y). Sei B eine unendliche Menge von nicht–algebraischen Elementen^{2} und a′ nicht–algebraisch über B. Weil alle b′ ∈ B denselben Typ p(a′, y) über a′ haben, ist kein b′ algebraisch über a′. Also ist auch b nicht algebraisch über a. □

Definition Sei (X, cl) ein Matroid. Eine Teilmenge A von X ist

1. unabhängig, wenn a ∉ cl(A \ {a}) für alle a ∈ A.

2. ein Erzeugendensystem, wenn X = cl(A).

3. Basis, wenn A ein unabhängiges Erzeugendensystem ist.

Bemerkung Bijektionen zwischen unabhängigen Teilmengen von Modellen einer streng minimalen Theorie sind elementar.

Beweis: Wenn b_{1}, …, b_{n} unabhängig sind, ist tp(b_{1}) der (einzige) nicht–algebraische Typ über ∅, tp(b_{2}/b_{1}) ist der nicht–algebraische Typ über b_{1} und so fort. Schließlich ist tp(b_{n}/b_{1} … b_{n−1}) der nicht–algebraische Typ über b_{1} … b_{n−1}. Dadurch ist tp(b_{1}, …, b_{n}) eindeutig bestimmt. □

Lemma 17.4 Ein unabhängige Teilmenge eines Erzeugendensystems läßt sich zu einer Basis erweitern.

Beweis: Sei U eine unabhängige Teilmenge des Erzeugendensystems E. B sei ein maximale unabhängige Teilmenge von E, die U enthält. Wir zeigen, daß B eine Basis ist. Dazu sei e ein beliebiges Element von E, das nicht zu cl(B) gehört. Sei b ∈ B beliebig. Dann ist b ∉ cl(B \ {b}), woraus mit der Austauscheigenschaft folgt, daß b ∉ cl(B \ {b} ∪ {e}). Also ist B ∪ {e} unabhängig, was der Maximalität von B widerspricht. Wir haben also E ⊂ cl(B) und B ist ein Erzeugendensystem. □

Satz 17.5 Streng minimale Theorien sind kategorisch in allen überabzählbaren Mächtigkeiten.

Beweis: Sei κ überabzählbar und 𝔐_{1} und 𝔐_{2} zwei Modelle der Mächtigkeit κ. Wir wählen zwei Basen B_{1} und B_{2} von 𝔐_{1} und 𝔐_{2}. Weil κ überabzählbar ist, haben B_{1} und B_{2} die Mächtigkeit κ. Sei f : B_{1} → B_{2} eine Bijektion. f ist eine elementare Abbildung, die sich zu einem Isomorphismus der algebraischen Abschlüsse M_{1} und M_{2} fortsetzt (17.2). □

2Wir finden ein solches B in einer elementaren Erweiterung des betrachteten Modells.

Definition Sei (X, cl) ein Matroid und S eine Teilmenge. Man kann aus S zwei neue Matroide definieren, die Einschränkung (S, cl^{S}) und die Relativierung (X, cl_{S}), wobei

cl^{S}(A) = cl(A) ∩ S,
cl_{S}(A) = cl(A ∪ S).

Bemerkung Sei A eine Basis von (S, cl^{S}) und B eine Basis von (X, cl_{S}). Dann ist die (disjunkte) Vereinigung A ∪ B eine Basis von (X, cl).

Beweis: Daß A ∪ B ein Erzeugendensystem ist, ist klar. Weil B unabhängig über S ist, ist b ∉ cl_{S}(B \ {b}) = cl(A ∪ B \ {b}) für alle b ∈ B. Sei a ∈ A und A′ = A \ {a}. Wir müssen zeigen, daß a ∉ cl(A′ ∪ B). Wenn nicht, gäbe es eine Teilmenge B′ von B und ein b ∈ B mit a ∈ cl(A′ ∪ B′ ∪ {b}) und a ∉ cl(A′ ∪ B′), denn a ∉ cl(A′). Daraus würde b ∈ cl(A ∪ B′) folgen. □

A nennt man eine Basis von S und B eine Basis über oder relativ zu S.

Lemma 17.6 Alle Basen eines Matroids haben dieselbe Mächtigkeit.

Beweis: Seien A und B zwei Basen von X. Zuerst wählen wir für jedes a ∈ A eine (minimale) endliche Teilmenge B_{a} von B mit a ∈ cl(B_{a}). Weil die Vereinigung der B_{a} ein Erzeugendensystem ist, ist B = ⋃_{a∈A} B_{a}. Symmetrischerweise ist A = ⋃_{b∈B} A_{b}. Daraus folgt, daß A genau dann endlich ist, wenn B endlich ist, und daß |A| = |B|, wenn A und B unendlich sind.

Nehmen wir also an, daß A und B endlich sind. Wir beweisen die Behauptung durch Induktion über |A|. Wenn A leer ist, muß auch B leer sein. Wenn A ≠ ∅ wählen wir ein a ∈ A. Setze S = cl(B_{a}). Weil B_{a} nicht leer sein kann, können wir uns ein b ∈ B_{a} wählen. Setze B′ = B_{a} \ {b}.

Weil B_{a} minimal gewählt war, ist a ∉ cl(B′) und daher b ∈ cl(B′ ∪ {a}). Daraus folgt (wie in der obigen Bemerkung), daß B′ ∪ {a} eine Basis von S ist. Weil B \ B_{a} eine Basis relativ zu S ist, ist (B′ ∪ {a}) ∪ (B \ B_{a}) eine Basis von X. Es folgt, daß A \ {a} und B \ {b} zwei Basen relativ zu {a} sind. Aus der Induktionsvoraussetzung, angewendet auf cl_{{a}}, folgt, daß |A \ {a}| = |B \ {b}|. Also ist |A| = |B|. □

Definition Die Dimension dim(X) eines Matroids (X, cl) ist die Mächtigkeit einer Basis. Für eine Teilmenge S von X ist dim(S) die Dimension von (S, cl^{S}) und dim_{S}(X) die Dimension von (X, cl_{S}).

Aus der letzten Bemerkung folgt, daß

dim(X) = dim(S) + dim_{S}(X).

Die Dimension dim(𝔐) eines Modells 𝔐 einer streng minimalen Theorie ist die Dimension des Matroids (M, acl).

Satz 17.7 Sei T streng minimal. Modelle von T sind durch ihre Dimension eindeutig bestimmt. Die Menge der vorkommenden Dimensionen ist ein Endabschnitt der Kardinalzahlen. 𝔐 ist ω–saturiert genau dann, wenn dim(𝔐) ≥ ℵ_{0}. Alle Modelle sind ω–homogen.

Beweis: Daß 𝔐 durch dim(𝔐) eindeutig bestimmt ist, zeigt der Beweis von 17.5.

Der gleiche Beweis zeigt auch, daß man in jedes Modell 𝔐 jedes Modell von kleinerer Dimension elementar einbetten kann. Wir zeigen, daß jede unendliche algebraisch abgeschlossene Teilmenge S von M Universum einer elementaren Unterstruktur ist. Daraus folgt, daß die vorkommenden Dimensionen die Dimensionen der unendlichen algebraisch abgeschlossenen Teilmengen sind, also ein Endabschnitt der Klasse aller Kardinalzahlen. Wir müssen zeigen, daß jede erfüllbare L(S)–Formel ϕ(x) in S realisiert werden kann (4.2). Wenn ϕ(𝔐) endlich ist, sind alle Realisierungen algebraisch über S und liegen daher in S selbst. Wenn ϕ(𝔐) koendlich ist, schneidet ϕ(𝔐) alle unendlichen Mengen.

Sei A eine endliche Teilmenge von 𝔐 und p der nicht algebraische Typ in S(A). Wenn p in 𝔐 realisiert wird, werden alle Typen über A realisiert. p wird in 𝔐 genau dann realisiert, wenn M ≠ acl(A), das heißt, wenn dim(𝔐) > dim(A). Daraus folgt, daß 𝔐 genau dann ω–saturiert ist, wenn 𝔐 unendliche Dimension hat.

Es bleibt noch zu zeigen, daß alle Modelle ω–homogen sind. Sei f : A → B eine elementare Bijektion zwischen zwei endlichen Teilmengen von M. Sei p der nicht–algebraische Typ über A. Dann ist f(p) der nicht–algebraische Typ über B. p wird genau dann in 𝔐 realisiert, wenn dim(𝔐) > dim(A) und f(p) wird genau dann realisiert, wenn dim(𝔐) > dim(B). Weil dim(A) = dim(B), wird p genau dann realisiert, wenn f(p) realisiert wird. □

18 Der Satz von Baldwin–Lachlan

Sei T eine abzählbare vollständige Theorie ohne endliche Modelle. Wir wollen in diesem Abschnitt zeigen, daß T in allen überabzählbaren Kardinalzahlen kategorisch ist, wenn T total transzendent ist und kein Vaughtsches Paar hat.

Lemma 18.1 Wenn T kein Vaughtsches Paar hat, gibt es zu jeder L–Formel ϕ(x, \overline{y}) eine Schranke F, sodaß in Modellen 𝔐 von T für alle Parameter \overline{a} ∈ M,

ϕ(𝔐, \overline{a})

entweder unendlich ist oder höchstens F Elemente enthält.

Die im Lemma behauptete Eigenschaft von T bedeutet, daß der Quantor ∃^{∞}x, es gibt unendlich viele x, eliminierbar ist. Das heißt, daß es für alle ϕ(x, \overline{y}) ein ψ(\overline{y}) gibt, sodaß in allen Modellen 𝔐 von T und für alle \overline{a} ∈ M

𝔐 ⊧ ∃^{∞}x ϕ(x, \overline{a}) ⟺ 𝔐 ⊧ ψ(\overline{a}).

Oder auch

T ⊢ ∀\overline{y}(∃^{∞}x ϕ(x, \overline{y}) ↔ ψ(\overline{y})).

Wenn F existiert, können wir nämlich ψ(\overline{y}) = ∃^{>F} x ϕ(x, \overline{y}) setzen. Wenn umgekehrt ψ(\overline{y}) eine Formel ist, die aus ∃^{∞}x ϕ(x, \overline{y}) folgt, zeigt ein Kompaktheitsargument, daß es ein F geben muß, sodaß schon

T ⊢ ∃^{>F} x ϕ(x, \overline{y}) → ψ(\overline{y}).

Beweis: Sei P ein neues unäres Prädikat und c_{1}, …, c_{n} neue Konstanten. T^{∗} sei die Theorie aller L ∪ {P, c_{1}, …, c_{n}}–Strukturen

(𝔐, N, a_{1}, …, a_{n}),

wobei 𝔐 ein Modell von T ist, N Universum einer echten elementaren Unterstruktur, a_{1}, …, a_{n} Elemente von N und ϕ(𝔐, \overline{a}) ⊂ N. Nehmen wir an, die Schranke F würde es nicht geben. Dann gibt es für jedes F ein Modell 𝔑 von T und \overline{a} ∈ N, sodaß ϕ(𝔑, \overline{a}) endlich ist, aber mehr als F Elemente hat. Sei 𝔐 eine echte elementare Erweiterung von 𝔑. Dann ist ϕ(𝔐, \overline{a}) = ϕ(𝔑, \overline{a}). Das Paar (𝔐, N, \overline{a}) ist also ein Modell von T^{∗}. Diese Überlegung zeigt, daß die Theorie

T^{∗} ∪ \{∃^{>F} x ϕ(x, \overline{c}) | F = 1, 2, …\}

endlich erfüllbar ist. Ein Modell dieser Theorie liefert ein Vaughtsches Paar von T. □

Definition Sei 𝔐 ein Modell von T und μ(x) eine nicht-algebraische L(M)– Formel. μ(x) heißt minimal in 𝔐, wenn für alle L(M)–Formeln ϕ(x) der Durchschnitt μ(𝔐) ∧ ϕ(𝔐) entweder endlich oder koendlich in μ(𝔐) ist. μ(x) ist streng minimal, wenn μ minimal in allen elementaren Erweiterungen von 𝔐 ist.

Ob μ(x, \overline{a}) streng minimal ist, hängt nur vom Typ des Parametertupels \overline{a} ab und nicht dem aktuellen Modell. Wenn T kein Vaughtsches Paar hat, ist das klar, weil für alle L–Formeln ϕ(x, \overline{z})

¬(∃^{∞}x(μ(x, \overline{a}) ∧ ϕ(x, \overline{z})) ∧ ∃^{∞}x(μ(x, \overline{a}) ∧ ¬ϕ(x, \overline{z})))

eine elementare Eigenschaft von \overline{z} und \overline{a} ist. Sonst überlegen wir uns, daß μ(x, \overline{a}) genau dann streng minimal ist, wenn für alle L–Formeln ϕ(x, \overline{z}) die Formelmenge

Σ_{ϕ}(\overline{z}, \overline{a}) = \{∃^{>F} x(μ(x, \overline{a}) ∧ ϕ(x, \overline{z})) ∧ ∃^{>F} x(μ(x, \overline{a}) ∧ ¬ϕ(x, \overline{z})) | F = 1, 2, …\}

in keiner elementaren Erweiterung realisiert werden kann. Das bedeutet, daß es für alle ϕ(x, \overline{z}) eine Schranke F gibt, sodaß

M ⊧ ∀\overline{z} (∃^{≤F} x(μ(x, \overline{a}) ∧ ϕ(x, \overline{z})) ∨ ∃^{≤F} x(μ(x, \overline{a}) ∧ ¬ϕ(x, \overline{z}))).

Das ist eine elementare Eigenschaft von \overline{a}.

Sei μ(x) eine streng minimale Formel ohne Parameter.

Man zeigt wie auf S. 74, daß es über jeder Parametermenge genau einen nicht–algebraischen Typ p mit μ(x) ∈ p gibt, und wie in 17.3, daß μ(𝔐) mit dem Abschlußoperator

cl(A) = acl(A) ∩ μ(𝔐)

ein Matroid ist^{3}. Daraus folgt, daß der Typ tp(b_{1}, …, b_{n}) einer unabhängigen Folge von Elementen von μ(𝔐) eindeutig bestimmt ist. (Vergleiche die Bemerkung auf Seite 75.)

{Lemma 18.2 \atop 1.} Wenn T total transzendent ist, gibt es in jedem Modell 𝔐 eine minimale L(M)–Formel.

2. Wenn μ(x) minimal in M ist und wenn M ω–saturiert ist, ist μ(x) streng minimal.

3. Wenn T den Quantor ∃^{∞} eliminiert, ist jede in einem Modell minimale Formel auch streng minimal.

Beweis:

1) Wenn es in 𝔐 keine minimale Formel gibt, läßt sich jede nicht–algebraische L(M)–Formel in zwei nicht–algebraische Formeln auspalten. Es gibt also einen binären Baum aus nicht–algebraischen Formeln und T ist nicht total transzendent.

2) Wenn μ(x, \overline{a}) minimal in 𝔐 ist, sind die Formelmengen Σ_{ϕ}(\overline{z}, \overline{a}) (S. 79) in 𝔐 nicht erfüllbar. Wenn 𝔐 ω–saturiert sind, müssen die Σ_{ϕ}(\overline{z}, \overline{a}) inkonsistent sein und μ(x, \overline{a}) ist streng minimal.

3) Wenn sich der Quantor ∃^{∞} eliminieren läßt, ist jede der Formelmengen Σ_{ϕ}(\overline{z}, \overline{a}) äquivalent zu einer endlichen Teilmenge. □

3Es läßt sich mit einem etwas anderen Beweis zeigen, daß es genügt, wenn μ minimal in 𝔐 ist.

Satz 18.3 Wenn T total transzendent ist und keine Vaughtschen Paare hat, ist T in allen überabzählbaren Kardinalzahlen kategorisch.

Beweis: Wenn T total transzendent ist gibt es ein Primmodell 𝔐_{0}. (Das folgt aus 12.3 und 12.4 oder aus 14.3.) Sei μ(x, \overline{a}_{0}) minimal in 𝔐_{0}. Weil T keine Vaughtschen Paare hat, ist der Quantor ∃^{∞} eliminierbar ist und μ(x, \overline{a}_{0}) ist streng minimal. Weil 𝔐_{0} prim ist, ist \overline{a}_{0} atomar (vgl. 12.1).

Sei q(\overline{y}) der Typ von \overline{a}_{0}. Die L(\overline{c})–Theorie

T (q) = Th(𝔐_{0}, \overline{a}_{0}) = T ∪ \{ϕ(\overline{c}) | ϕ(\overline{y}) ∈ q(y)\}

ist vollständig. Weil q isoliert ist, läßt sich jedes Modell 𝔐 von T zu einem Modell (𝔐, \overline{a}) von T (q) erweitern. Es genügt also zu zeigen, daß T (q) in allen überabzählbaren Kardinalzahlen kategorisch ist. Natürlich ist auch T (q) total transzendent und hat kein Vaughtsches Paar. Die L(\overline{c})–Formel μ(x, \overline{c}) ist immer noch streng minimal, enthält aber jetzt keine neuen Parameter mehr. Darum haben wir T (q) eingeführt: Wir können annehmen, daß es für T eine streng minimale Formel μ ohne Parameter gibt^{4}.

Sei 𝔐 ein Modell von T. Und 𝔐′ ≺ 𝔐 eine Primerweiterung von μ(𝔐) (vgl. 14.3). Weil T kein Vaughtsches Paar hat, muß 𝔐′ = 𝔐 sein. Es folgt, daß 𝔐 minimale Primerweiterung von μ(𝔐) ist: 𝔐 hat keine echte elementare Unterstruktur, die μ(𝔐) enthält. Der Satz von Löwenheim–Skolem liefert |𝔐| = |μ(𝔐)|. Wenn 𝔐 überabzählbarist, folgt dim(μ(𝔐)) = |𝔐|.

Seien nun 𝔐_{1} und 𝔐_{2} zwei Modelle der gleichen überabzählbaren Mächtigkeit. Wir wählen zwei Basen B_{1} und B_{2} von μ(𝔐_{1}) und μ(𝔐_{2}) und eine Bijektion f : B_{1} → B_{2}. f ist eine elementare Abbildung, die sich zu einer elementaren Bijektion der algebraischen Abschlüsse fortsetzt. Wir erhalten also eine elementare Bijektion

g : μ(𝔐_{1}) → μ(𝔐_{2}).

Weil 𝔐_{1} Primerweiterung von μ(𝔐_{1}) ist, läßt sich g zu einer elementaren Einbettung h : 𝔐_{1} → 𝔐_{2} fortsetzen. Weil 𝔐_{2} eine minimale Erweiterung von μ(𝔐_{2}) ist, ist h surjektiv und also ein Isomorphismus. □

Folgerung 18.4 (Morley) Sei T eine abzählbare Theorie. Wenn T in einer überabzählbaren Mächtigkeit kategorisch ist, ist T in allen überabzählbaren Mächtigkeiten kategorisch.

Beweis: (Natürlich können wir annehmen, daß T vollständig ist und keine endlichen Modelle hat.) Wenn T in einer überabzählbaren Mächtigkeit kategorisch ist, ist T total transzendent (14.1 und 14.2) und hat keine Vaughtschen Paare (15.4). □

4Ohne diese Annahme wäre das Schriftbild etwas komplizierter.

Anhang A

Mengenlehre

19 Kardinalzahlen

Zwei Mengen, zwischen denen es eine Bijektion gibt, heißen gleichmächtig. Man kann jeder Menge x eine Kardinalzahl |x| (die Mächtigkeit von x) so zuordnen, daß je zwei Mengen genau dann die gleiche Mächtigkeit haben, wenn sie gleichmächtig sind^{1}.

Man bezeichnet mit 0 die Mächtigkeit der leeren Menge, mit 1 die Mächtigkeit einer ein–elementigen Menge etc.

Definition Für zwei Kardinalzahlen κ und λ definieren wir

κ ≤ λ,

wenn λ die Mächtigkeit einer Menge x ist und κ die Mächtigkeit einer Teilmenge von x.

Man sieht leicht, daß ≤ reflexiv und transitiv ist. Der Satz von Cantor– Bernstein besagt, daß zwei Mengen, die man ineinander injektiv abbilden kann, gleichmächtig sind. Daraus folgt, daß ≤ antisymmetrisch ist, und damit eine partielle Ordnung auf der Klasse der Kardinalzahlen.

Für je zwei Mengen x, y existiert nach Zorns Lemma eine maximale Bijektion f zwischen einer Teilmenge x_{0} von x und einer Teilmenge y_{0} von y. Wenn beide, x_{0} und y_{0}, echte Teilmengen wären, könnte man f weiter fortsetzen. Also ist f eine Bijektion zwischen x_{0} und y oder zwischen x oder y_{0}. Es folgt, daß ≤ eine lineare Ordnung ist.

Definition Eine Wohlordnung von X ist eine lineare Ordnung, für die jede nicht–leere Teilmenge von X ein kleinstes Element enthält. Wenn X keine Menge sondern nur eine Klasse ist, fordert man zusätzlich, daß für alle x ∈ X die Menge {y | y < x} der Vorgänger eine Menge ist.

1 Man könnte |x| als die Klasse aller zu x gleichmächtigen Mengen definieren. Dann wären allerdings Kardinalzahlen keine Mengen.

Lemma 19.1 Die Klasse aller Kardinalzahlen wird durch ≤ wohlgeordnet.

Beweis: Nach dem Wohlordnungssatz (der aus dem Auswahlaxiom folgt) hat jede Menge eine Wohlordnung. Wie oben sieht man mit Hilfe von Zorns Lemma, daß für je zwei Wohlordnungen die eine isomorph zu einem Anfangsstück^{2} der anderen ist, oder umgekehrt. Wenn κ die Mächtigkeit der Wohlordnung x ist, ist daher jede kleinere Kardinalzahl die Mächtigkeit eines Anfangsstücks von x. Daraus folgt die Behauptung, weil die Anfangsstücke einer Wohlordnung selbst durch Inklusion wohlgeordnet sind. □ ℵ_{0} ist die Mächtigkeit der (wohlgeordneten) Menge der natürlichen Zahlen. Mengen der Mächtigkeit ℵ_{0} heißen abzählbar. Alle echten Anfangsstücke sind endlich, ℵ_{0} ist daher die kleinste unendliche Kardinalzahl.

Jede Familie (κ_{i})_{i∈I} von Kardinalzahlen hat eine obere Schranke(zum Beispiel die Mächtigkeit von ⋃_{i∈I} x_{i}, wenn κ_{i} = |x_{i}|). Es gibt also auch eine kleinste Schranke sup_{i∈I} κ_{i}.

Summe, Produkt und Potenz von Kardinalzahlen definiert man durch disjunkte Vereinigung, cartesisches Produkt und Mengenpotenz. Also

(1)  |x| + |y| = |x ∪ y|
(2)  |x| · |y| = |x × y|
(3)  |x|^{|y|} = |^{y}x|

Dabei nehmen wir in (1) an, daß x und y disjunkt sind. In (3) ist ^{y}x die Menge aller Funktion von y nach x.

Man zeigt leicht, daß die gleichen Regeln wie für das Rechnen mit natürlichen Zahlen gelten. Zum Beispiel ist (κ^{λ})^{μ} = κ^{λ·μ}. Der folgende Satz wurde von Cantor bewiesen.

{Satz 19.2 \atop 1.} Wenn κ unendlich ist, ist κ · κ = κ.

2. 2^{κ} > κ

Aus 2. folgt, daß es keine größte Kardinalzahl gibt. Weil jede Menge von Kardinalzahlen ein Supremum hat, ist die Klasse der Kardinalzahlen kein Menge.

Folgerung 19.3 1. Wenn λ unendlich ist, ist κ + λ = max(κ, λ).

2. Wenn κ > 0 und λ unendlich ist, ist κ · λ = max(κ, λ).

3. Wenn κ unendlich ist, ist κ^{κ} = 2^{κ}.

Beweis: Sei μ = max(κ, λ). Dann ist μ ≤ κ + λ ≤ μ + μ ≤ 2 · μ ≤ μ · μ = μ und wenn κ > 0, ist μ ≤ κ · λ ≤ μ · μ = μ.

2 Ein Anfangsstück einer partiellen Ordnung X enthält mit jedem Element auch alle kleineren Elemente von X.

Schließlich ist

2^{κ} ≤ κ^{κ} ≤ (2^{κ})^{κ} = 2^{κ·κ} = 2^{κ}.
□

Folgerung 19.4 Die Menge aller endlichen Folgen von Elementen der nicht– leeren Menge x hat die Mächtigkeit max(|x|, ℵ_{0}).

Beweis: Sei κ die Zahle der endlichen Folgen aus x. Es ist klar, daß |x| ≤ κ und ℵ_{0} ≤ κ. Andererseits ist

κ = ∑_{n∈ℕ} |x|^{n} ≤ (sup_{n∈ℕ} |x|^{n}) · ℵ_{0} = max(|x|, ℵ_{0}),

weil

sup_{n∈ℕ} |x|^{n} = \{ \begin{matrix}1 & wenn |x| = 1 \\ ℵ_{0} & wenn 2 ≤ |x| ≤ ℵ_{0} \\ |x| & wenn ℵ_{0} ≤ |x| \end{matrix} .

□

Für jede Kardinalzahl κ nennt man die kleinste Kardinalzahl κ^{+}, die größer als κ, die Nachfolgerkardinalzahl von κ. Aus 19.2.2 folgt κ^{+} ≤ 2^{κ}. Die allgemeine Kontinuumshypothese (GCH) besagt, daß für alle unendlichen κ

κ^{+} = 2^{κ}.

GCH ist unabhängig von den Axiomen der Mengenlehre^{3}.

3Wenn man die Konsistenz dieser Axiome annimmt.

20 Ordinalzahlen

Die Klasse On der Ordinalzahlen wird bis auf Isomorphie durch Eigenschaften charakterisiert, die auch die Klasse der Kardinalzahlen hat:

a) On ist wohlgeordnet

b) On ist keine Menge

Die Wohlgeordnetheit hat das folgende Induktionsprinzip zur Folge:

Sei E eine Eigenschaft von Ordinalzahlen. Nehmen wir an, daß jedes α, für das alle kleineren Ordinalzahlen die Eigenschaft E haben, selbst die Eigenschaft E hat. Dann haben alle Ordinalzahlen die Eigenschaft E.

Sei (X, <) ein Wohlordnung und f ein maximaler Isomorphismus zwischen einem Anfangsstück von X und einem Anfangsstück von On. Man sieht leicht, daß f auf ganz X erklärt sein muß. Wenn X eine echte Klasse ist, ist f ein Isomorphismus zwischen X und On. Wenn X eine Menge ist, ist f ein Isomorphismus zwischen X und einem echten Anfangsstück, das immer die Form

{β | β < α}

hat. Man sieht leicht^{4}, daß f, und damit α, eindeutig durch X bestimmt ist. Man nennt α den Ordnungstyp von (X, <)

α = otp(X, <).

Weil viele Bezeichnungen erheblich vereinfacht werden, identifizieren wir jede Ordinalzahl mit der Menge ihrer Vorgänger^{5}

α = {β | β < α}.

α ist also sein eigener Ordnungstyp. Jede Kardinalzahl ist nach dem Wohlordnungssatz Mächtigkeit einer Ordinalzahl. In der axiomatischen Mengenlehre wird eine Kardinalzahl mit der kleinsten Ordinalzahl identifiziert, die diese Mächtigkeit hat. Die Klasse der Kardinalzahlen wird auf diese Weise eine Teilklasse von On: κ ist genau dann eine Kardinalzahl, wenn alle α < κ eine kleinere Mächtigkeit als κ haben.

Satz 20.1 Sei G eine Zuordnungsvorschrift, die jeder auf einer Ordinalzahl definierten Funktion f eine Menge G(f) zuordnet. Dann gibt es genau eine auf der Klasse On definierte Funktion F, die für alle α die Rekursionsgleichung

F (α) = G(F ↾ α)

erfüllt.

4 Wenn g : X → On ein zweiter Isomorphismus auf ein Anfangsstück ist, betrachte das kleinste x mit f(x) ≠ g(x).

5 In der axiomatischen Mengenlehre werden Ordinalzahlen tatsächlich so eingeführt.

Beweis: Man beweist leicht durch Induktion, daß es für alle β eine eindeutig bestimmte Funktion F_{β} gibt, die auf β definiert ist und für alle α < β die Rekursionsgleichung erfüllt. Wir setzen F = ⋃_{β∈On} F_{β}. □ Beispiel: Die Alephfunktion indiziert die unendlichen Kardinalzahlen durch Ordinalzahlen. Man setzt

ℵ_{α} = Die kleinste unendliche Kardinalzahl, die größer als alle ℵ_{β} (β < α) ist.

Die kleinste Ordinalzahl ist 0 = ∅, die nächstgrößere ist 1 = {0}, dann 2 = {0, 1} und so weiter. Wir erhalten so die natürlichen Zahlen. Der Ordnungstyp der natürlichen Zahlen ist ω = {0, 1, …}, die nächste Ordinalzahl ist ω + 1 = {0, 1, …. , ω}, et cetera. Die natürlichen Zahlen und ω = ℵ_{0} sind Kardinalzahlen.

Allgemein nennen wir eine Ordinalzahl β, die einen unmittelbaren Vorgänger α hat, eine Nachfolgerzahl und schreiben β = α + 1. Für natürliche Zahlen n ist

α + n = α + \underbrace{1 + … + 1}_{n− mal} .

Ordinalzahlen > 0, die keine Nachfolgerzahlen sind, heißen Limeszahlen. Wenn die Menge {α_{i} | i ∈ I} nicht–leer ist und kein größtes Element hat, ist sup_{i∈I} α_{i} eine Limeszahl. Jede Ordinalzahl schreibt sich eindeutig in der Form

λ + n,

wobei λ = 0 oder eine Limeszahl ist.

Eine endliche Folge der Länge n mit Elementen aus A ist eine Funktion s : n → A.

<ωA = ⋃_{n<ω} ^{n}A

bezeichnet die Menge alle endlichen Folgen von Elementen aus A.

Anhang B

Körpertheorie

21 Ringe und Körper

21.1 Homomorphiesatz

Sei R ein kommutativer Ring^{1}. Ein Ideal I ◁ R ist eine additive Untergruppe von R, die unter Multiplikation mit beliebigen Elementen von R abgeschlossen ist. R ist genau dann ein Körper, wenn das Nullideal das einzige echte Ideal^{2} ist. Die Nebenklassen a+I bilden mit den Operationen (a+I)+(b+I)=(a+b)+I und (a + I)(b + I) = ab + I den Faktorring R/I. Wenn f : R → S ein Homomorphismus ist, ist der Kern

I = kerf = {r ∈ R | f(r) = 0}

ein Ideal. Man faktorisiert f eindeutig als

R → R/kerf → S.

Der erste Pfeil ist der natürliche Homomorphismus, der zweite eine isomorphe Einbettung (Homomorphiesatz).

Sei R ein kommutativer Ring und a Element eines Oberrings. Dann können wir die von a erzeugte Ringerweiterung schreiben als

R[a] = {p(a) | p(X) ∈ R[X]}

oder, wenn I ◁ R[X] der Kern des Einsetzungshomomorphismus p(X) ↦ p(a) ist, als

R[a] = R[X]/I.

Die hier auftretenden I sind genau die Ideale von R[X], die R in 0 schneiden.

1Wir betrachten nur Ringe mit Einselementy. Homomorphismen sollen das Einselement erhalten, Unterringe das gleiche Einselement haben.

2 d.h. R ≠ I

21.2 Primideale

Ein Integritätsbereich ist ein nicht–trivialer kommutativer Ring, der keine Nullteiler hat. Das heißt, daß R ≠ 0 und

a, b ≠ 0 ⇒ ab ≠ 0.

Sei I ein Ideal in R. Der Faktorring R/I ist genau dann ein Integritätsbereich, wenn P ein Primideal ist, das heißt, daß R ≠ P und

a, b ∈ R \ I ⇒ ab ∈ R \ I.

Jedes echte Ideal läßt sich mit Zorns Lemma zu einem maximalen Ideal M (gemeint ist ein maximales echtes Ideal) erweitern. M ist genau dann maximal, wenn R/M ein Körper ist. Der Ring der ganzen Zahlen ℤ und Polynomringe K[X] über Körpern K sind Hauptidealringe. Das sind Integritätsbereiche, in denen jedes Ideal I von einem Element a erzeugt wird: I = Ra. In Hauptidealringen ist ein I = Ra ≠ 0 genau dann prim, wenn I maximal ist, und genau dann, wenn a irreduzibel^{3} ist.

21.3 Quotientenkörper

Unterringe von Körpern sind immer Integritätsbereiche. Umgekehrt läßt sich jeder Integritätsbereich R in einen kleinsten Körper Q einbetten, den Quotientenkörper von R. Es ist

Q = \{\frac{a}{b} | a ∈ R, b ∈ R, b ≠ 0\}

Lemma 21.1 Sei K ein Oberkörper von R. Dann ist der von R in K erzeugte Körper (über R) isomorph zu Q. □

Der Quotientenkörper von ℤ ist der Körper ℚ der rationalen Zahlen. Der Quotientenkörper eines Polynomrings K[X] über einem Körper K ist K(X), der rationale Funktionenkörper über K.

21.4 Charakteristik

Jeder Körper K enthält einen kleinsten Unterring:

R = {z · 1 | z ∈ ℤ}

R ist isomorph zu einem Faktorring von ℤ. Es gibt zwei Fälle:

1. R = ℤ. Dann hat K die Charakteristik 0.

3 Elemente mit multiplikativen Inversen heißen Einheiten. a ≠ 0 heißt irreduzibel, wenn aus a = bc folgt, daß entweder b oder c eine Einheit ist.

2. Für eine Primzahl p ist R = ℤ/pℤ = 𝔽_{p}, der Körper mit p Elementen. p ist die Charakteristik von K^{4}.

Im Fall der Charakteristik p ist 𝔽_{p} der kleinste Unterkörper von K, der Primkörper. Wenn die Charakteristik 0 ist, ist der Primkörper ℚ.

4 Man spricht hier auch von positiver oder endlicher Charakteristik

22 Algebraisch abgeschlossene Körper

Sei K ⊂ L eine Körpererweiterung und a ein Element von L. K(a), der von a über K erzeugten Unterkörper von L, ist der Quotientenkörper von K[a]. Es ist

K[a] = K[X]/P

für ein Primideal P ◁ K[X]. Für P gibt es zwei Möglichkeiten:

1. Wenn P = 0, heißt a transzendent über K. K[a] ist dann isomorph zum Polynomring K[X] und K(a) isomorph zum rationalen Funktionenkörper.

2. Sonst wird P von einem irreduziblen Polynom p(x), dem Minimalpolynom erzeugt. a heißt algebraisch über K. Weil P maximal ist, ist jetzt K(a) = K[X].

Eine KörpererweiterungK ⊂ L heißt algebraisch, wenn alle Elemente von L algebraisch über K sind.

{Lemma 22.1 \atop 1.} Die Erweiterung K ⊂ K(a) ist genau dann algebraisch, wenn a algebraisch über K ist.

2. Wenn H ⊂ K und K ⊂ L algebraische Körpererweiterungen sind, ist L algebraische Erweiterung von H

□

Definition Ein Körper K heißt algebraisch abgeschlossen, wenn jedes nicht– konstante Polynom mit Koeffizienten aus K eine Nullstelle in K hat.

Lemma 22.2 K sei ein Körper. Es sind äquivalent:

a) K ist algebraisch abgeschlossen.

b) K hat keine echte algebraische Körpererweiterung.

c) Jedes Polynom aus K[X] zerfällt in ein Produkt von linearen Polynomen.

□

Definition Eine algebraische Erweiterung L von K, die algebraisch abgeschlossen ist, heißt algebraischer Abschluß von K.

Satz 22.3 Jeder Körper K hat einen bis auf Isomorphie über K eindeutig bestimmten algebraischen Abschluß. □

Wir bezeichnen mit

acl(K)

den algebraischen Abschluß von K.

Sei M eine Erweiterung von K. Nach 22.1.1) ist die Menge L aller Elemente von M, die algebraisch über K sind ein algebraische Körpererweiterung von K. Man nennt L den relativen algebraischen Abschluß von K in M. Wenn M algebraisch abgeschlossen ist, ist nach 22.1.2) auch L algebraisch abgeschlossen und daher ein algebraischer Abschluß von K.

Lemma 22.4 Algebraisch abgeschlossene Körper sind unendlich.

Beweis: Wenn K endlich ist, ist

∏_{a∈K}(X − a) + 1

ein Polynom ohne Nullstelle in K. □

23 Reell abgeschlossene Körper

Sei R ein Integritätsbereich. Eine lineare < Ordnung auf R ist verträglich mit der Ringstruktur, wenn für alle x, y, z ∈ R

x < y → x + z < y + z
x < y ∧ 0 < z → xz < yz

Ein Körper (K, <) zusammen mit einer verträglichen Anordnung ist ein angeordneter Körper.

Lemma 23.1 Sei R ein Integritätsbereich und < eine verträgliche Anordnung von R. Dann setzt sich < eindeutig zu einer Anordnung des Quotientenkörpers fort.

Beweis: Setze

\frac{a}{b} > 0 ⇔ ab > 0.

□

Man zeigt leicht, daß in einem angeordneten Körper Quadratsummen niemals negativ sein können. Insbesondere sind alle 1, 2, … positiv. Die Charakteristik angeordneter Körper ist also 0.

Ein Körper K, in dem −1 keine Quadratsumme ist, heißt formal reell. Körper mit einer Anordnung sind formal reell.

Lemma 23.2 Formal reelle Körper haben eine Anordnung.

Beweis: Wir stellen zuerst fest, daß Σ□, die Menge aller Quadratsummen in K, ein Semipositivbereich ist. Ein Semipositivbereich ist eine Menge P mit

(1)  Σ□ ⊂ P
(2)  P + P ⊂ P
(3)  P · P ⊂ P
(4)  −1 ∉ P

Man überlegt leicht, daß aus der ersten und dritten Bedingung folgt, daß

x ∈ P \ 0 ⇒ \frac{1}{x} ∈ P.

Die Bedingung (4) ist deshalb gleichbedeutend mit P ∩ (−P) = 0. Man sieht auch leicht, daß für alle b die Menge P + bP wieder alle Eigenschaften eines Semipositivbereich hat, bis vielleicht auf (4). Und daß (4) genau dann gilt, wenn b = 0 oder −b ∉ P.

Jetzt wählen wir für P einen maximalen Semipositivbereich. Dann gilt P ∪ (−P) = K. Wir setzen

x ≤ y ⇔ y − x ∈ P

und erhalten eine verträgliche Anordnung von K. □

Folgerung 23.3 (aus dem Beweis) Sei K formal reell^{5} und a ein Element von K. Es gibt genau dann ein Anordnung von K, bezüglich der a negativ wird, wenn a keine Summe von Quadraten ist.

Beweis: Wenn a ∉ Σ□, ist Σ□ − a · Σ□ ein Semipositivbereich. □

Definition Ein angeordneter Körper (R, <) heißt reell abgeschlossen, wenn

a) jedes positive Element Quadrat ist,

b) jedes Polynom von ungeradem Grad eine Nullstelle hat.

(R, <) heißt reeller Abschluß des Unterkörpers (K, <), wenn R algebraisch über K ist.

Der Körper der reellen Zahlen ist reell abgeschlossen. Ebenso der Körper der reellen algebraischen Zahlen, der reeller Abschluß von ℚ ist. Allgemein ist jeder Körper der relativ abgeschlossen in einem reell abgeschlossenen Körper ist, selbst reell abgeschlossen.

Satz 23.4 Jeder angeordnete Körper (K, <) hat einen bis auf Isomorphie über K eindeutig bestimmten reellen Abschluß. □

Beweis: (Skizze) Existenz: Sei K_{≥0} der Positivbereich von (K, <) und L ein Oberkörper von K. Die Anordnung von K läßt sich genau dann auf R fortsetzen, wenn

P = {x_{1}y_{1}^{2} + ⋯ + x_{n}y_{n}^{2} | x_{i} ∈ K_{≥0}, y_{i} ∈ L}

ein Semipositivbereich von L ist, das heißt, wenn −1 ∉ P. Daraus folgt, daß man Zorns Lemma anwenden kann, um eine maximale algebraische Erweiterung R von K zu finden, die eine Anordnung < besitzt, die die Anordnung K fortsetzt. Wir zeigen, daß R reell abgeschlossen ist. Sei r ein positives Element von R, das kein Quadrat ist. Dann läßt sich die Anordnung nicht auf L = R(\sqrt{r}) fortsetzen. Das bedeutet, daß

−1 = ∑ r_{i}(s_{i}\sqrt{r} + t_{i})^{2}

für r_{i} ∈ R_{≥0} und s_{i}, t_{i} ∈ R. Daraus folgt −1 = ∑ r_{i}(s_{i}^{2}r + t_{i}^{2}), was unmöglich ist, weil die rechte Seite positiv ist. Also ist in R jedes positive Element Quadrat. (Und R hat nur eine Anordnung.) Sei f ∈ R[X] ein Polynom von minimalem ungeraden Grad n, das in R keine Nullstelle hat. f ist muß irreduzibel sein. Sei α ein Nullstelle und L = R(α). Weil L keine Anordnung hat, ist −1 in L eine Summe von Quadraten. Also gibt es Polynome g_{i} ∈ R[X] von kleinerem Grad als n, sodaß h = ∑ 1 + g_{i}^{2} durch f teilbar ist. Die führenden Koeffizienten der g_{i}^{2} sind Quadrate und können sich nicht wegheben. Also ist der Grad von h gerade und kleiner als 2n. Das Polynom hf^{−1} hat daher ungeraden Grad < n und keine Nullstelle in R, weil h keine Nullstelle hat. Widerspruch.

5Es genügt vorauszusetzen, daß K nicht die Charakteristik 2 hat

Eindeutigkeit: Seien R und S zwei reelle Abschlüsse von (K, <). Es genügt, zu zeigen, daß R und S als Körper über K isomorph sind. Sei L ein Unterkörper von R, der über K endlich erzeugt ist. Dann gibt es nur endlich viele Möglichkeiten L über K isomorph in S einzubetten. Eine Kompaktheitsüberlegung zeigt, daß es deshalb genügt zu zeigen, daß jedes solche L über K isomorph in S einbettbar ist (und daß umgekehrt jeder endlich erzeugte Zwischenkörper von S/K über K isomorph in R einbettbar ist). In Charakteristik 0 sind endlich erzeugte algebraische Erweiterungen von einem einzelnen Element erzeugt. Es folgt, daß es genügt zu zeigen, daß in R und S die gleichen irreduziblen f ∈ K[X] Nullstellen haben. Das folgt aber sofort aus dem nächsten Hilfssatz, den wir am Ende des Abschnitts beweisen.

Hilfssatz (M. Knebusch) Sei f irreduzibel^{6} in K[X] und (R, <) eine reell abgeschlossene Erweiterung von (K, <). Dann ist die Zahl der Nullstellen von f in R die Signatur der Spurform der K–Algebra K[X]/(f).

□

Der Hauptsatz der Algebra gilt für beliebige reell abgeschlossene Körper^{7}:

Satz 23.5 Sei R reell abgeschlossen. Dann ist C = R(\sqrt{−1}) algebraisch abgeschlossen.

Beweis: Zuerst überlegen wir uns, daß in C alle Elemente Quadrate sind: Die (eine) Quadratwurzel von a + b\sqrt{−1} berechnet sich als

\sqrt{\frac{\sqrt{a^{2} + b^{2}} + a}{2}} + \sqrt{\frac{\sqrt{a^{2} + b^{2}} − a}{2}} \sqrt{−1}.

Unter der Wurzelzeichen stehen nur nicht–negative Elemente von R. Die inneren Wurzel wählt man nicht–negativ, die Vorzeichen der äußeren Wurzeln geeignet.

Sei F eine endliche Erweiterung von C. Wir wollen zeigen, daß F = C. Dazu können wir annehmen, daß F galoissch über R ist. Sei G eine 2–Sylowgruppe in Aut(F/R) und L der Fixkörper von G. Dann ist der Grad der Erweiterung L/R ungerade. Das Minimalpolynom eines erzeugenden Elements dieser Erweiterung hat denselben Grad und ist irreduzibel. Weil aber über R alle irreduziblen Polynome ungeraden Grades linear sind, muß L = R sein. Es folgt, daß G = Aut(F/R) und damit auch H = Aut(F/C) eine 2–Gruppe ist. 2 Gruppen sind auflösbar (sogar nilpotent). Darum hätte H, wenn nicht trivial, eine Untergruppe vom Index 2 und C eine Körpererweiterung von Grad 2; was aber nicht geht, weil alle Elemente Quadratwurzeln sind. Also ist H = 1 und F = C. □

6Es genügt, wenn f nicht konstant ist und keine doppelten Nullstellen in acl(K) hat.

7 Weil in reell abgeschlossenen Körpern (K, <) die nicht–negativen Elemente gerade die Quadrate sind, wird die Anordnung < eindeutig durch die Körperstruktur bestimmt. Es hat also Sinn zu sagen, daß K reell abgeschlossen ist.

Folgerung 23.6 In einem reell abgeschlossenen Körper R gibt es nur zwei Arten von (normierten) irreduziblen Polynomen:

• Lineare Polynome

X − a,

(a ∈ R)

• Quadratische Polynome

(X − b)^{2} + c,

(b, c ∈ R, c > 0)

Beweis: Weil alle nicht-konstanten f ∈ R[X] Nullstellen in R(\sqrt{−1}) haben, sind alle irreduziblen Polynome linear oder quadratisch. Quadratische Polynome sind genau dann irreduzibel, wenn sie keine Nullstelle haben. Jedes normierte quadratische Polynom hat die Form (X − b)^{2} + c und genau dann eine Nullstelle x in R, wenn c ≤ 0 (nämlich x = b ± \sqrt{−c}). □

Schließlich beweisen wir noch Knebuschs Lemma (S. 93). Sei K ein angeordneter Körper mit reellem Abschluß R und f ∈ K[X] ein irreduzibles Polynom. Wir betrachten die endlich–dimensionale K–Algebra A = K[X]/(f). Die Spur Tr_{K}(a) eines Elements von A ist die Spur der Linksmultiplikation mit a, als Vektorraumendomorphismus aufgefaßt. Die Spurform ist

(a, b)_{K} = Tr_{K}(ab).

Sei a_{1}, …, a_{n} eine Basis von A, in der ( , )_{K} Diagonalgestalt hat: (a_{i}, a_{j})_{K} = λ_{i}δ_{ij}. Die Signatur der Spurform ist die Zahl der positiven λ_{i} minus die Zahl der negativen λ_{i}. Der Satz von Sylvester (Lineare Algebra) besagt, daß die Signatur unabhängig ist von der Wahl der diagonalisierenden Basis.

Wenn man A mit R tensoriert, erhält man die R–Algebra

A ⊗ R ≅ R[X]/(f).

Die Spurform dieser Algebra hat die gleiche diagonalisierende Basis (tensoriert mit R), die gleichen λ_{i} und die gleiche Signatur wie die Spurform von A. Wir zerlegen nun f in R[X] in irreduzible Polynome g_{1}, …, g_{m}. Weil f keine doppelten Nullstellen hat, sind die g_{i} paarweise verschieden. Also ist nach dem chinesischen Restsatz

R[X]/(f) ≅ R[X]/(g_{1}) × ⋯ × R[X]/(g_{m}).

Die Spurform von R[X]/(f) ist also die direkte Summe der Spurformen der R[X]/(g_{i}) und die Signatur die Summe der zugehörigen Signaturen. Knebuschs Lemma folgt nun sofort, wenn wir zeigen können, daß für lineares g die Signatur der Spurform von R[X]/(g) gleich 1 ist, und gleich Null, wenn g irreduzibel quadratisch ist.

Wenn g linear ist, ist R[X]/(g) = R. Die Spurform (x, y)_{R} = xy hat Signatur 1. Wenn g irreduzibel quadratisch ist, ist R[X]/(g) = R(\sqrt{−1}). Es ist Tr_{R}(x + y\sqrt{−1}) = 2x. Die Spurform wird also diagonalisiert von der Basis 1, \sqrt{−1}. Für diese Basis ist λ_{1} = 2 und λ_{2} = −2 und die Signatur ist Null.

Literaturverzeichnis

[1] Wilfried Hodges. Model Theory. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 1993.

[2] Wilfried Hodges. A Shorter Model Theory. Cambridge University Press, 1997.

[3] Serge Lang. Algebra. Addison–Wesley Publishing Company, second edition, 1984.

[4] Bruno Poizat. Cours de Théorie des Modèles. Nur Al-Mantiq Wal-Ma’rifah, Villeurbanne, 1985.

Index

0, 85 1, 85 2, 85 ℵ_{0}–saturiert, 49 ∀, 10 (𝔄, R), 7 (𝔄, a_{1}, …, a_{n}), 7 𝔄 ≅ 𝔅, 4 𝔄 ⊧ ϕ[b⃗], 10 𝔄 ↾ K, 6 𝔄 ⊂ 𝔅, 5 𝔄_{B}, 7 |𝔄|, 4 𝔄 ≡ 𝔅, 18 𝔄 ≺ 𝔅, 19 𝔄 ≺_{1} 𝔅, 36 acl(K), 90 acl(A), 72 𝔄 ⇒_{Δ} 𝔅, 30 A–definierbare Menge, 72 𝔄 ⇒_{∃} 𝔅, 30 ∀∃–Formel, 32 ℵ_{0}, 82 ℵ_{α}, 85 α + 1, 85 α + n, 85 [A]^{n}, 59 𝔅 ↾ A, 5 b⃗\frac{a}{x}, 11 cl^{S}, 76 cl_{S}, 76 Diag(𝔄), 14 Ded(T), 17 dim(𝔐), 77 dim_{S}(X), 76 dim(X), 76 ∃, 10 ↔, 10 ∃∀–Formel, 32 ∃^{∞}, 78 ⟨ϕ(\overline{x})⟩, 47 ⟨ϕ(\overline{x})⟩_{A}, 56 ϕ(π), 12 ϕ(t_{1}, …, t_{n}), 12 ϕ(x_{1}, …, x_{n}), 11 f : 𝔄 →_{Δ} 𝔅, 30 ϕ(𝔐), 64 𝔽_{p}, 88 f(p), 50

=^{.}, 10

h : 𝔄 ⟶^{≺} 𝔅, 19

h : 𝔄 →^{∼} 𝔅, 4

h : 𝔄 → 𝔅, 4

→, 10 I ◁ R, 86 κ–kategorische Theorie, 27, 28 κ ≤ λ, 81 K(a), 89 κ^{+}, 83 κ–saturiert, 70 κ–stabil, 69 K–saturiert, 53 K(X), 87 K[X], 87 ⟨∅⟩^{𝔅}, 5 L_{AG}, 3 L_{AR}, 3 L(B), 7 L(C), 7 L_{G}, 3 L_{Me}, 3 L_{M(R)}, 41 L_{N}, 3 L_{∅}, 3 L_{O}, 3 L_{R}, 3 L_{Sk}, 61 Mod(T), 17 mult(p), 72 ¬, 10 ⋁_{i<m}, 13 ∨, 10 otp(X, <), 84 ω, 85 <ωA, 85 ω–homogen, 66

algebraisch, 52 ω–stabil, 62 On, 84 ℚ, 87 R[a], 86 R/I, 86 ⟨S⟩^{𝔅}, 5 sup_{i∈I} α_{i}, 85 sup_{i∈I} κ_{i}, 82 S_{1}^{𝔄}(B), 25 S_{n}^{𝔄}(B), 25 S(B), 25 S_{n}(B), 25 S_{n}(T), 47 Th(K), 17 ⊥, 13 ⊤, 13 tp(a/B), 25 tp^{𝔄}(a/B), 25 t(t_{1}, …, t_{n}), 9 t(x_{1}, …, x_{n}), 8 t^{𝔄}[b⃗], 8 t^{𝔄}[a_{1}, …, a_{n}], 8 T_{∀}, 31 T_{AAK}, 41 T_{∀∃}, 33 T_{AG}, 16 T_{AAK_{0}}, 42 T_{AAK_{p}}, 42 T_{DLO}, 40 T -e.a, 37 T ⊢ ϕ, 17 T^{KH}, 38 T_{K}, 16 T_{M(R)}, 41 tp(\overline{a}), 56 tp_{qf}(\overline{a}), 53 T_{R}, 16 T_{RAK}, 43 T ≡ S, 17 T ⊢ S, 17 T_{Sk}(L), 61 T_{∞}, 40 ⋃_{i∈I} 𝔄_{i}, 6 ⋀_{i<m}, 13 ∧, 10 v_{0}, v_{1}, …, 8 |x|, 81 yx, 82 ℤ, 87

17. Hilbertsches Problem, 44

Abbildung

elementare, 19, 50 abelsche Gruppe, 16 Abschlußoperator, 73 abzählbare

Menge, 82 Theorie, 46

äquivalente Formeln, 13 Theorien, 17

Äquivalenz, 10 algebraisch

ω–homogen, 52

abgeschlossener Körper, 41, 89 algebraische

Formel, 72

Körpererweiterung, 89 algebraischer

Abschluß, 72, 89

Typ, 72 algebraisches

Element, 72

Körperelement, 89 Allformel, 14 allgemeingültige Aussage, 17 Allquantor, 10 Amalgamationseigenschaft, 54 Anfangsstück, 82 angeordneter Körper, 91 atomare

Erweiterung, 62 Formel, 48, 56 atomarer Typ, 48, 56 atomares

Diagramm, 14 Modell, 56 Tupel, 56, 63

Auslassen einer Formelmenge, 24

lokales, 46 Aussage, 12 Austauscheigenschaft, 73 basic Formel, 12 Basis, 75, 76 Basissatz, 43 Baum, 58 Belegung, 8 binärer Baum, 58 Bindungsstärke, 10

Charakteristik, 87

deduktiver Abschluß, 17 definitorische

Äquivalenz, 52 Erweiterung, 52

Diagramm atomares, 14 elementares, 19

Dichtheit, 57 Dimension, 76 Disjunktion, 10 disjunktive Normalform, 13

echtes Ideal, 86 Einbettung, 4

elementare, 19 Eindeutige Lesbarkeit, 8, 11 einfache Existenzformel, 34 Einheit, 87 Einschränkung eines Matroids, 76 Einsetzungshomomorphismus, 86 elementare

Unterstruktur, 19 Abbildung, 19, 50 Einbettung, 19 Erweiterung, 19 gerichtete Familie, 20 Klasse, 17

elementares Diagramm, 19 endlich erfüllbare

Formelmenge, 24

Theorie, 22 Erfüllen, 11 Erfüllungsmenge, 64 Erhaltungssätze, 29 Erweiterung

atomare, 62 minimale, 80 prime, 62

Erzeugendensystem, 75 Erzeugnis, 5 erzeugter Haupttyp, 47 existentiell abgeschlossene Modelle, 37 Unterstruktur, 36

Existenzformel, 14 einfache, 34 primitive, 34 existenzielle Formel, 14 Existenzquantor, 10 Expansion, 6

Faktorring, 86

Familie

gerichtete, 6 Folgerung, 17 formal reeller Körper, 91 Formel

∀∃, 32 ∃∀, 32 algebraische, 72 All–, 14 atomare, 48, 56 basic, 12 Existenz–, 14 existenzielle, 14 konsistente, 46 minimale, 78 Prim-, 10 quantorenfreie, 12 streng minimale, 78 universelle, 14 vollständige, 48, 56

freies Vorkommen, 11 Funktionszeichen, 3

GCH, 83 gerichtete

Familie, 6

elementare, 20 partielle Ordnung, 6

Gleichheitszeichen, 10 gleichmächtige Mengen, 81 Grad eines Typs, 72 Graph, 55 Grundmenge, 4 Gültigkeit, 12

Hauptidealring, 87

Hauptsatz der Algebra, 93 Haupttyp, 47 Henkin–Konstante, 22 Henkin–Theorie, 22 Hilberts 17. Problem, 44 Hilbertscher

Basissatz, 43 Nullstellensatz, 43

Homomorphiesatz, 86 Homomorphismus, 4

Ideal, 86 echtes, 86 maximales, 87 Null–, 86 primes, 87

Implikation, 10 Indiscernibles, 59 Induktion, 84 induktive Theorie, 32 Integritätsbereich, 87 irreduzibles Ringelement, 87 Isolieren, 47 isolierter Typ, 48 isomorphe Strukturen, 4 Isomorphismus, 4

Junktoren, 10

Kaiserhülle, 38 Kardinalität, 4 Kardinalzahl, 81, 84 Kardinalzahlarithmetik, 82 Kategorizität, 27 Kette, 6

elementare, 20 stetige, 25

Kettenlemma, 20 Klammern, 10 Knebusch, M., 93 Körper, 16

algebraisch abgeschlossener, 41, 89 angeordneter, 91 formal reeller, 91 reell abgeschlossener, 92, 93

Körpererweiterung

algebraische, 89 kommutativer Ring, 16 Kompaktheitssatz, 22 Konjunktion, 10 konjunktive Normalform, 13 konsistente Formel, 46 Formelmenge, 46 Theorie, 16

Konstante, 3

konstanter Term, 9 konstruktible Menge, 63 Kontinuumshypothese, 83

Limeszahl, 85

logische Zeichen, 10

Mächtigkeit, 4, 81

Matroid, 73

maximales Ideal, 87

minimale Erweiterung, 80 Formel, 78 Minimalpolynom, 89 Modell, 12, 16

ℵ_{0}–saturiertes, 49 κ–saturiertes, 70 atomares, 56 aus Konstanten, 23 existentiell abgeschlossenes, 37 primes, siehe Primmodell saturiertes, 69 Modellbegleiter, 36 Modellklasse, 17 modellvollständige Theorie, 36 Modul, 41 Morleyisierung, 52 Multiplizität, 72

Nachfolgerkardinalzahl, 83 Nachfolgerzahl, 85 Negationsnormalform, 14 Negationszeichen, 10 Normalform

disjunktive, 13 konjunktive, 13 pränexe, 13

Nullideal, 86

Nullstellensatz, 43

Oberstruktur, 6 Omitting Types, 46 Ordinalzahl, 84 Ordnung, 40 Ordnungstyp, 84

partielle Ordnung

gerichtete, 6 Prädikat, 3 pränexe Normalform, 13 Primerweiterung, 62 Primformel, 10 Primideal, 87 primitive Existenzformel, 34 Primkörper, 88 Primmodell, 56 Primstruktur, 43

Quantorenelimination, 34 quantorenfreie Formel, 12 Quotientenkörper, 87

Randomgraph, 55 rationaler Funktionenkörper, 87 Realisieren einer Formelmenge, 24

lokales, 46 reell abgeschlossener Körper, 92, 93 reeller Abschluß, 92 Rekursionssatz, 84 relationale Sprache, 52 Relationszeichen, 3 relativer algebraischer Abschluß, 90 Relativierung eines Matroids, 76 Restriktion, 6 Ring, 86 Robinsons Test, 36

Saturiertheit, 49, 69, 70 Satz

von Cantor, 51, 82 von Cantor–Bernstein, 81 von Lachlan, 64 von Löwenheim–Skolem, 27 von Morley, 80

abwärts, 70 von Ramsey, 59 von Ryll–Nardzewski, 49 von Vaught, 51 Zwei-Kardinalzahlsatz von Vaught,

67 schmale Theorie, 51 Skelett, 53 Skolemfunktion, 61 Skolemtheorie, 61 Sprache, 3 stabil

κ–stabil, 69

ω–stabil, 62 stetige Kette, 25 streng minimale

Formel, 78 Theorie, 74

Struktur, 3 Substitution, 9 Substitutionslemma, 9, 12

Tarskis Kettenlemma, 20 Test, 19

Teilsprache, 6 Term, 8

konstanter, 9 Theorie, 16

κ–stabile, 69 ω–stabile, 62 abzählbare, 46 äquivalente, 17 deduktiv abgeschlossene, 17 der abelschen Gruppen, 16 der Körper, 16 der kommutativen Ringe, 16 einer Klasse von Strukturen, 17 endlich erfüllbare, 22 induktive, 32 κ–kategorische, 27, 28 konsistente, 16 mit Vaughtschem Paar, 68 modellvollständige, 36 schmale, 51 streng minimale, 74 total transzendente, 62 universelle, 31 vollständige, 17 widerspruchsfreie, 16

total transzendente Theorie, 62 transzendentes Körperelement, 89 trennende Aussage, 29 Trennungslemma, 29 Tupel

atomares, 56, 63 Typ, 25, 47

algebraischer, 72 atomarer, 48, 56 eines Elements, 25 erzeugter, 47 Haupt–, 47 isolierter, 48

quantorenfreier, 53

unabhängige Aussage, 18 Menge, 75

universelle Formel, 14 Theorie, 31

Universum, 4 Unterstruktur, 5

elementare, 19

existentiell abgeschlossene, 36

Variable, 8 Vaughts Test, 27 Vaughtscher Zwei-Kardinalzahlsatz, 67 Vaughtsches Paar, 66, 68 Vektorraum, 41 vollständige

Formel, 48, 56 Theorie, 17

widerspruchsfreie Theorie, 16 Wohlordnung, 81 Wohlordnungssatz, 82

Zutreffen, 11

Änderungen

Version 6.0 (28.2.1998)

Erste vollständige Version.

Version 6.1 (7.2.2000)

Anhand einer Liste von Immanuel Hermann wurden viele Druckfehler verbessert.

Version 6.2 (8.5.2002)

Es gibt zusätzliches Material über Modellbegleiter und reelle Körper. Olaf Schürer und Sebastian Holzmann haben viele Fehler gefunden und Anregungen gegeben.

Version 6.2c (26.10.2004)

Druckfehler von L. Stieber. Druckfehler. Definition Modellbegleiter verbessert. Beweis von 11.7 verbessert. Fehler in der Formulierung von 23.3 verbessert. Beweis der Bemerkung auf S. 74. Fußnote in 21.1.

Version 6.2e (8.9.2007)

Druckfehler in den Beweisen von 7.5, von 8.5 und der Bemerkung nach 8.5. Druckfehler in der Definition der leeren Disjunktion und Konjunktion.