Hrushovskis primordiales Amalgam

M.Z.^{∗}

27. September 2009

Zusammenfassung Hrushovskis originale Fusion [1]. Seminarvortrag, Freiburg 4.Mai 2005

We prove that the resulting theory is model-complete (26.11.2005).

1 Das Hauptlemma

Wir betrachten Strukturen mit einem dreistelligen Prädikat R und definieren für endliches A

δ(A) = |A| − |R(A)|.

und allgemeiner

δ(A/M) = |A \ M| − |R(A ∪ M) \ R(M)|.

Wenn δ(A/M) endlich ist, ist δ(A/M) = δ(A∪B)−δ(B) genügend große endliche B zwischen A ∩ M und M.

B ⊂ M ist abgeschlossen in M, wenn δ(A/B) ≥ 0 für alle A ⊂ M. Wir schreiben dafür B ≤ M. Wir sagen auch M/B ist stark. cl(X), der Abschluß von X in M ist die kleinste starke Teilmenge von M, die X enthält. C^{0} ist die Klasse aller M mit ∅ ≤ M. Wenn M zu C^{0} gehört und X ⊂ M endlich ist, ist auch cl(X) endlich.

Für endliche Teilmengen B von M ∈ C^{0} definieren wir

d(B) = min{δ(A)|B ⊂ A ⊂ M} = δ cl(B).

d ist Dimensionsfunktion eines Matroids.

Eine echte starke Erweiterung M ≤ N ist minimal, wenn sie sich nicht in zwei echte starke Erweiterungen M ≤ M′ und M′ ≤ N zerlegt.

Lemma 1.1. Sei N/M minimal und δ(N/M) > 0. Dann ist δ(N/M) = 1 und N = M ∪ {n}, für ein n, das mit keinen Elementen von M in Relation steht.

Definition 1.2. Ein Paar (A, B) heißt gut, wenn

a) B ∪ A ∈ C^{0}

b) A ∩ B = ∅

c) (B ∪ A)/B minimal d) δ(A/B) = 0

∗primordial.tex,v 1.14, September 26, 2009

(A, B) heißt sehr gut, wenn für keine echte Teilmenge B′ von B das Paar (A, B′) gut ist.

Wenn (A, B) sehr gut ist, steht jedes b ∈ B in Relation mit einem Element von A (und Elementen von B ∪ A). Wenn (A, B) gut ist, gibt es ein eindeutig bestimmtes B′ ⊂ B, für das (A, B′) sehr gut ist: B′ ist die Menge aller b ∈ B, die in Relation mit einem Element von A (und Elementen von B ∪ A) sind. Wir nennen B′ die Basis von A/B. Man hat die Abschätzung |B′| ≤ 2 · |A|.

Ein Code α ist ein Isomorphietyp eines sehr guten Paares (A_{α}, B_{α}). Eine Pseudomorleyfolge von α über B ist eine Menge von paarweise disjunkten A_{i} so, daß (A_{i}, B) ≅ (A_{α}, B_{α}).

Wir fixieren für jedes sehr gute α eine Zahl μ(α) ≥ δ(B_{α}).

Definition 1.3. C^{μ} ist die Klasse aller M aus C^{0}, so daß jedes α über jedem B ⊂ M in M höchstens Pseudomorleyfolgen der Länge μ(α) hat.

Lemma 1.4. Sei M ∈ C^{μ} und a nicht mit M verbunden. Dann ist M ∪ {a} in C^{μ}.

Lemma 1.5 (Hauptlemma). Sei M ∈ C^{μ} und (A, M) ein gutes Paar mit Basis B. Dann ist M′ = M ∪ A in C^{μ}, es sei denn, einer der beiden folgenden Fälle tritt ein:

1. Der Typ α von (A, B) hat in M über B eine Pseudomorleyfolge der Länge μ(α).

2. Es gibt ein B′ ⊂ M′, das nicht in M liegt, und einen Code α′, der über B′ in M′ eine Pseudomorleyfolge (A′_{i}) der Länge μ(α′) + 1 hat. Es folgt

(a) Kein A′_{i} liegt in M \ B.

(b) Ein A′_{i} liegt in A.

(c) B′ ⊂ B ∪ A.

Beweis. Es ist klar, daß M′ nicht in C^{μ} ist, wenn einer der beiden Fälle eintritt. Nehmen wir also an, daß M′ nicht in C^{μ} ist. Dann gibt es ein α′ mit einer zu langen Morleyfolge A′_{i} über einem B′ in M′. Wir unterscheiden zwei Fälle:

1.Fall: B′ ⊂ M. Weil M ∈ C^{μ}, liegt eines der A′_{i} nicht in M. Wäre A′_{i} nicht ganz in A, würde aus der Minimalität von A′_{i}/B′ folgen, daß δ(A′_{i}/M) < 0, was M ≤ M′ widerspricht. Also ist A′_{i} ⊂ A. Nun ist aber δ(A′_{i}/M) = 0, was wegen der Minimalität von A/M impliziert, daß A′_{i} = A. Es folgt B′ = B und α′ = α. Also hat α über B in M ein Pseudomorleyfolge der Länge μ(α).

2.Fall: B′ liegt nicht ganz in M.

Ein A′_{i}, das ganz in M \ B läge, könnte nicht mit den Punkten B′ \ M verbunden sein. Also gilt (2a).

Nehmen wir an, daß die ersten A′_{1}, …, A′_{k} ganz in M liegen und die nächsten A′_{k+1}, …, A′_{k+l} weder ganz in M noch ganz in A. Weil alle A′_{i} mit den Punkten aus B′ \ M verbunden sind, folgt zunächst, daß^{1}

δ(B′/M) ≤ δ(B′/M ∩ B′) − k ≤ δ(B′) − k.

1Beachte δ(B′/M ∩ B′) ≤ δ(B′), weil δ(M ∩ B′) ≥ 0.

Dann folgt aus der Minimalität der A′_{i}/B′, daß

δ(A′_{i}/M ∪ B′ ∪ A′_{k+1} ∪ ⋯ A′_{i−1}) < 0

für alle i = k + 1, …, k + l. Es ergibt sich

δ( ⋃_{i=k+1}^{k+l} A′_{i}/M ∪ B′) ≤ −l.

Also ist

0 ≤ δ( ⋃_{i=k+1}^{k+l} A′_{i} ∪ B′/M) ≤ δ(B′/M) − l ≤ δ(B′) − (k + l).

Es liegen also höchstens δ(B′) viele der A′_{i} nicht in A. Daraus folgt (2b). Weil die Elemente von A nicht mit den Punkten von B′ \ (B ∪ A) verbunden sind, folgt (2c).

2 Die Theorie T^{μ}

Folgerung 2.1. C^{μ} hat bezüglich starker Einbettungen die Amalgamationseigenschaft.

Beweis. Sei N ≤ M ∈ C^{μ}, N ≤ N′ ∈ C^{μ}. Wir suchen ein M ≤ M′ ∈ C^{μ} und eine starke Einbettung N′ → M′ über N. Wir können annehmen, daß N′/N minimal ist (!). Der Fall δ(N′/N) > 0 ist klar nach Lemma 1.1: Es ist N′ = N ∪ {a}, für ein a, daß nicht mit N verbunden ist. Wir setzen M′ = M ∪ {a}, wobei a nicht M verbunden ist. Wir haben also nur noch den Fall zu betrachten, daß N′ = N ∪ A, wobei (A, N) gut ist.

Fall 1: Die (freie) Vereinigung M′ = M ∪ A gehört zu C^{μ}. Dann sind wir fertig, weil M ≤ M′ und N′ ≤ M′.

Fall 2: Sonst tritt einer der beiden Fälle von Lemma 1.5 ein.

Weil die Basis B von A/M in N liegt, kann der zweite Fall kann nicht eintreten: Die A′_{i} liegen nicht voll in M \ N = M′ \ N′ und daher, weil B′ ⊂ N′ ≤ M′, und A′_{i}/B′ minimal, liegen sie voll in N′. Es würde N′ ∉ C^{μ} folgen.

Also hat der Typ α von (A, B) in M eine Pseudomorleyfolge (A_{i}) der Länge μ(α). Die A_{i} können nicht alle in N liegen, weil N′ ∈ C^{μ}. Also gibt es ein A_{i}, das voll in M \ N liegt. Es folgt N ∪ A_{i} ≤ M. Der Isomorphismus zwischen B ∪ A und B ∪ A_{i} setzt sich trivial zu einem Isomorphismus N′ → N ∪ A_{i} über N fort.

Definition 2.2. Ein M ∈ C^{μ} ist reich, wenn es für alle endlichen B ≤ M und B ≤ C ∈ C^{μ} eine starke Einbettung C → M über B gibt.

Aus der letzten Folgerung ergibt sich sofort die Existenz einer eindeutig bestimmten abzählbaren reichen Struktur K^{μ}.

Wir bezeichnen mit F_{n} die Struktur mit n Elementen und δ(F_{n}) = n, das heißt ohne Relationen. F_{n} ≤ M bedeutet, daß die Elemente von F_{n} in M d– unabhängig sind. Es ist klar, daß F_{n} zu C^{μ} gehört.

Definition 2.3. M ist ein Modell der Theorie T^{μ}, wenn

a) M ∈ C^{μ}

b) Wenn (A, M) gut ist, ist M ∪ A ∉ C^{μ}.

c) Für jedes n ist F_{n} stark einbettbar in eine elementare Erweiterung von M.^{2}

Folgerung 2.4. T^{μ} ist tatsächlich eine elementare Theorie.

Beweis. Es ist leicht zu sehen, daß für jedes α die Eigenschaft Für kein B ⊂ M enthält M ein Pseudomorleyfolge von α über B der Länge μ(α) + 1 sich durch eine elementare Aussage ausdrücken läßt.

Für alle α müssen wir (durch eine Aussage) ausdrücken: Wenn (A/M) gut ist, mit einer Basis B ⊂ M für die (A, B) vom Typ α ist, ist M′ = M ∪A ∉ C^{μ}. Das geht, wenn wir nur für endlich viele α′ die Länge von Pseudomorleyfolgen in M′ beschränken müssen. Das folgt aber aus Lemma 1.5: Für die dort vorkommenden α′ gilt |A_{α′}| ≤ |A| und |B_{α′}| ≤ |B ∪ A|.

Satz 2.5. M ist genau dann reich, wenn M ein ω–saturiertes Modell von T^{μ} ist.

Beweis. Sei K reich. Es ist klar, daß K die Axiome a) und c) erfüllt. Sei (A, K) ein gutes Paar und sei K ∪ A ∈ C^{μ}. Wähle ein endliches C_{0} ≤ K, das die Basis B von A/K enthält und eine Kopie A_{0} von A über C_{0} mit C_{1} = C_{0} ∪ A_{0} ≤ K. Man fährt so fort und erhält in K eine unendliche Pseudomorleyfolge von α über B. Widerspruch. Also gilt b). Daß K ω–saturiert ist, zeigen wir später.

Sei jetzt M ⊧ T^{μ} ω–saturiert, B ≤ M und B ≤ C ∈ C^{μ}. Wir können annehmen, daß C/B minimal ist. Wir unterscheiden zwei Fälle:

1.δ(C/B) > 0. Dann ist C = B ∪ {a} für ein a, das mit B nicht verbunden ist. Aus Axiom c) und der ω–Saturiertheit folgt, daß d(M) = ∞. Also gibt es ein a′ ∈ M mit d(a′/B) = 1. Daraus folgt, daß a′ nicht mit B verbunden ist und B ∪ {a′} ≤ M. Das liefert die gesuchte starke Einbettung von C in M.

2. C = B ∪ A für ein gutes Paar (A, B). Weil M ∪ A nicht zu C^{μ} gehört, C und M aber stark in C^{μ} amalgamierbar sind, ist B∪A über B stark in M einbettbar. (Siehe Beweis von 2.1.)

Weil M und K partiell isomorph sind, folgt, daß auch K ω–saturiert ist.

Folgerung 2.6. T^{μ} ist die vollständige Theorie von K^{μ}.

Beweis. Jedes saturierte Modell von T^{μ} ist partiell isomorph zu K^{μ}

2Ich weiß nicht, ob dieses Axiom wirklich notwendig ist. Wenn μ(α) > 0, falls B_{α} ≠ ∅, folgt dieses Axiom aus den anderen beiden Axiomen.

26.11.2005: Das Axiom ist in der Tat überflüssig. Siehe 4.2

3 T^{μ} ist streng minimal

Lemma 3.1. M und M′ seien zwei Modell von T^{μ}. Zwei Tupel a ∈ M und a′ ∈ M′ haben genau dann denselben Typ, wenn a ↦ a′ sich zu einem Isomorphismus cl(a) → cl(a′) fortsetzen läßt.

Beweis. Nehmen wir an, daß a und a′ denselben Typ haben. Man sieht leicht, daß d(a) = d(a′). Es gibt ein a′ ∈ A′ ⊂ M′, das zu cl(A) isomorph ist. Dann ist A′ – in A′ – der Abschluß von a′ und d(a′) = δ(A′). Daraus folgt A′ = cl(a′). Damit ist eine Richtung der behaupteten Äquivalenz bewiesen.^{3}

Für die Umkehrung wählen wir elementare ω–saturierte elementare Erweiterungen M ≺ N und M′ ≺ N′. Der erste Teil des Beweises zeigt, daß a und a′ in N bzw. N′ denselben Abschluß haben. Ein Isomorphismus zwischen cl(a) und cl(a′) erhält L_{∞,ω}–Formeln (in N und N′), weil N und N′ reich sind.

Lemma 3.2. Sei M ∈ C^{μ}, B eine starke Teilmenge von M, (A, B) eine gutes Paar. Dann gibt es nur endlich viele Kopien von A über B in M.

Beweis. Seien A_{1} und A_{2} zwei verschieden Kopien von A über B. Es genügt zu zeigen, daß A_{1} und A_{2} disjunkt sind. Weil B ≤ M und δ(A_{1}/B) = 0, ist B ∪ A_{1} ≤ M. Also ist B ≤ (B ∪ A_{1}) ∩ (B ∪ A_{2}) ≤ B ∪ A_{2}. Weil (B ∪ A_{2})/B minimal ist, folgt die Behauptung.

Folgerung 3.3. Sei M ∈ C^{μ}, B eine starke Teilmenge von B, A/B eine Erweiterung mit δ(A/B) = 0. Dann gibt es nur endlich viele Kopien von A über B in M.

Beweis. Wir können annehmen, daß B ≤ A. Zerlege A/B in eine Folge von minimalen Erweiterungen.

Satz 3.4. T^{μ} ist streng minimal mit Dimensionsfunktion d.

Beweis. Wir arbeiten in einem Modell von T^{μ}. Sei X eine Teilmenge und a ein Element. Es gibt zwei Fälle:

• d(a/X) = 0. Dann ist nach dem obigen a algebraisch über X.

• d(a/X) = 1. Dann ist a mit X nicht verbunden und cl(X) ∪ {a} ist eine starke Teilmenge. Der Typ von a über X ist also festgelegt.

Es gibt also nur einen nicht–algebraischen 1–Typ über X. Das bedeutet, daß T^{μ} streng minimal ist.

4 Schlußbemerkung

Lemma 4.1. Der d–Abschluß einer endlichen Teilmenge von M ∈ C^{μ} ist höchstens abzählbar.

Beweis. cl_{d}(X) ist die Vereinigung aller A′ ⊂ M mit cl(X) ⊂ A′ und δ(A′/ cl(X)) = 0.

3Wir haben nur verwendet, daß a und a′ dieselben Existenzformeln erfüllen. Aus 4.3 folgt, daß es genügt, wenn a′ alle Existenzformeln erfüllt, die a erfüllt.

Folgerung 4.2. Das Axiom c) kann ersetzt werden durch die Forderung, daß es unendlich viele Element gibt.

Beweis. Sei M ein ω_{1}–saturiertes unendliches Modell der Axiome a), b). Wähle e_{i} mit e_{i} ∉ cl_{d}(e_{0}, …, e_{i−1}). Die e_{i} sind d–unabhängig. Also hat {e_{0}, … } keine Relationen und ist stark in M.

Folgerung 4.3. T^{μ} ist modellvollständig.

Beweis. T^{μ} ist ∀∃–axiomatisierbar und streng minimal.

5 Änderungen

1.4 : Druckfehler im Beweis von 2.1. 1.6 : Kleine Druckfehler (Junker). 1.7 : Abschnitte 3, 4. 1.8 : Beweis von 4.2 1.9 : Beweis von 3.2 (Omar Kaziz) 1.12 : Formulierung von 3.1, Beweis von 3.4 (Omar Kaziz) 1.13: Beweis von 3.2 (Tent) 1.14: Letzte Ungleichung in Abschnitt 1.

Literatur

[1] Ehud Hrushovski. A new strongly minimal set. Ann. Pure Appl. Logic, 62:147–166, 1993.