Logik II: Modelltheorie

Martin Bays

Universität Münster, Wintersemester 2019-2020^{∗} version d4657169 de^{†}

1 Überblick

• Ein Hauptziel von Modelltheorie ist, die definierbare Menge einer Struktur M, d.h. die Teilmenge der Potenze M^{n}, die mit Formeln definiert sind, zu verstehen.

• Gödel vs Tarski: Die definierbare Menge einiger Strukturen sind unkontrollierbar wild, und mehr kompliziert werden, als wir mehr Quantoren erlauben. Zum Beispiel, in (N; +, ·) können wir bereits mit nur einem unbeschränkten Quantor jede rekursiv aufzählbare Menge definieren. Jedoch, es ist ein verwunderlicher Fakt, dass viele Strukturen, die wichtig zu Mathematik sind, diese Gödelische Phänomene vermeiden, und “zahm” sind. Ihre definierbare Mengen sind kontrolliert (insbesondere, alle definiert bei Formeln mit wenige Quantoren), ihre Theorien sind oft entscheidbar, und manchmal die Modelle ihre Theorien sind bis auf Isomorphie klassifizierbar. Beispielen einschließen:

– (ℂ; +, ·), (𝔽_{p}^{alg}; +, ·), (ℝ; +, ·), (ℚ_{p}; +, ·);

– (ℚ; <);

– Vectorräume;

– (ℤ; +), (ℤ; ∗), (ℤ; +, <) (aber nicht (ℤ; ·, <)! CHECKME);

– (ℝ; +, ·, x ↦ e^{x});

– (ℂ; +, ·, x ↦ x^{ζ}) (für die meisten ζ ∈ ℂ);

– Kompacte Liesche Gruppen ¡—e.g.—¿ (SO_{3}(ℝ); ·);

– (𝔽_{p}; +, ·) für ein “unendlich” (pseudoendlich) Primzahl p;

– Kompacte komplexe Mannigfaltkeiten (komplexe tori, Calabi-Yau Mannigfaltkeiten, usw.;

– Differenziele und differenze Gleichungen (auf einem gewissen Sinn);

– Freie Gruppen (F_{n}; ∗).

∗Dies Skript ist unter der Creative Commons Attribution-Sharealike Lizenz CC-BY-SA 4.0 https://creativecommons.org/licenses/by-sa/4.0/ bei Martin Bays 2019 lizenziert.

†These notes are also available in English.

Wir betrachten in diesem Kurs nür einen Bruchteil dieses Reichtum, aber wir entwickeln Werkzeuge mit breiter Anwendigkeit.

• Wir studieren oft eine Struktur, durch die Betrachtung anderer Modelle seiner Theorie. Wir werden drei Resultate dieser Art sehen. Sei M eine unendliche L-Struktur.

– “Monstermodelle existieren”: M hat eine elementare Erweiterung bis ein hoch saturiertes und homogenes Modell seine Theorie. Wir können dann M studieren, durch in dieser “glatter” Erweiterung arbeiten. Dies ist eine Inkarnation von Robinsons /nicht-standard Analysis/.

– (L abzählbar) Ryll-Nardzewski: M hat ein eindeutiges abzählbares Modell seine Theorie genau dann, wenn es für jedes n ∈ N gibt nur endliche viele L-definierbare Teilmenge von M^{n}.

– (L abzählbar) Baldwin-Lachlan: für eine unabzählbare Kardinalzahl κ, M hat ein eindeutiges Modell seine Theorie von Kardinalität κ genau dann, wenn M prim und minimal ist über eine streng minimale Menge, die auf dem Primmodell definiert ist. (Wir definieren später diese Begriffe. Eine streng minimale Menge ist eine besonders einfach Struktur, und wenn M prim und minimal über sie ist, sind die definierbare Menge von M “konstruktiert” (in einem gewissen Sinn) durch seine definierbare Menge.)

2 Grundbegriffe

Wir arbeiten in ZFC durch diesen Kurs.

2.1 Syntax und Struktur

• Ein (erst Stufe) (ein Sorte) Sprache ist eine Menge L von Relationszeichen, Funktionszeichen, und Konstanten.

• Eine L-Struktur M = (M; (R^{M})_{R}, (f^{M})_{f}, (c^{M})_{c}) ist eine nicht-leer Menge M mit Interpretationen der Zeichen von L:

– R^{M} ⊆ M^{n} für R ∈ L ein n-är Relationszeichen;

– f^{M} : M^{n} → M für f ∈ L ein n-är Funktionszeichen;

– c^{M} ∈ M für c ∈ L eine Konstante.

Oft bezeichnen wir auch die Grundmenge M als M.

• Ein L-Term ist eine Variable, eine Konstante, oder f(t_{1}, …, t_{n}) wobei t_{i} L-Terme und f ein n-är Funktionszeichen sind.

• Eine atomare L-Formel ist t_{1} ≐ t_{2} oder Rt_{1} … t_{n} wobei t_{i} L-Terme und R ein n-är Relationszeichen sind.

• Eine L-Formel ist eine atomare L-Formel oder ¬ϕ oder (ϕ ∧ ϕ′) oder ∃x.ϕ wobei ϕ, ϕ′ L-Formeln und x eine Variable sind.

• Ein L-Aussage ist eine L-Formel, die keine freie Variablen hat.

• Für M eine L-Struktur und σ ein L-Aussage, ist M ⊨ σ rekursiv definiert.

• Abkürzungen:

(ϕ ∨ ψ) ↦ ¬(¬ϕ ∧ ¬ψ)
(ϕ → ψ) ↦ (¬ϕ ∨ ψ)
(ϕ ↔ ψ) ↦ ((ϕ → ψ) ∧ (ψ → ϕ))
∀x.ϕ ↦ ¬∃x.¬ϕ
x ≐ y̸ ↦ ¬x ≐ y

• Wenn L′ ⊇ L und M eine L′-Struktur ist, ist M|_{L} die entsprechende L-Struktur. Dann ist M|_{L} das Redukt von M bis L, und M eine Expansion von M|_{L} bis L′.

• Wenn M eine L-Struktur ist und A ⊆ M, ist die Expansion durch Konstanten für A die Expansion M_{A} von M bis L(A) := L ˙∪A definiert durch a^{M_{A}} := a.

• Wenn ϕ = ϕ(\overline{x}, \overline{y}) (d.h. dass die freie Variablen von ϕ unter \{x_{1}, …, x_{n}, y_{1}, …, y_{m}\} sind) und a_{i} ∈ A, schreiben wir ϕ(\overline{a}, \overline{y}) für die L(A)-Formel, in der jedes x_{i} durch a_{i} ersetzt wird (i = 1, …, n). Wir schreiben M ⊨ ϕ(\overline{a}) für M_{A} ⊨ ϕ(\overline{a}).

• Ein partieller Isomorphismus von L-Strukturen ist eine partielle Funktion θ : M −−→ N, sodass für jede atomare L-Formel ϕ(x_{1}, …, x_{n}) und alle a_{1}, …, a_{n} ∈ dom(θ),

M ⊨ ϕ(\overline{a}) ⇔ N ⊨ ϕ(θ(\overline{a})).

Wenn dies für jede L-Formel ϕ gilt, heißt θ eine partielle elementare Abbildung.

• Ein totaler partieller Isomorphismus θ heißt Einbettung θ : M ⟶ N.

• Ein totaler partieller elementare Abbildung θ heißt elementare Einbet-

tung θ : M ⟶^{⪯} N.

• Eine surjective Einbettung heißt Isomorphismus θ : M ⟶^{≅} N.

• Eine Unterstruktur (bzw. elementare Unterstruktur einer L-Struktur N ist eine L-Struktur M auf eine Teilmenge von N, sodass die Inklusion eine Einbettung (bzw. elementare Einbettung) ist.

• Wir schreiben M ≤ N oder M ⊆ N für eine Unterstruktur, und M ⪯ N für eine elementare Unterstruktur.

2.2 Theorien

• Eine L-Theorie ist eine Menge von L-Aussagen.

• Die Theorie einer L-Struktur M ist Th(M) := {σ : M ⊨ σ, σ ein L-Aussage ist}.

• Eine L-Struktur M ist ein Modell einer L-Theorie T,

M ⊨ T,

wenn M ⊨ σ für alle σ ∈ T.

• T heißt konsistent, wenn sie ein Modell hat.

Bemerkung 2.1. T ist konsistent gdw T ⊭ ¬∃x.x ≐ x.

• T ⊨ σ bedeutet: M ⊨ σ für jedes M ⊨ T. Wir schreiben auch T ⊢ σ.

• Eine konsistente L-Theorie T heißt vollständig, wenn für alle L-Aussagen

σ

T ⊨ σ oder T ⊨ ¬σ.

• L-Strukturen M, N heißen elementar äquivalent, M ≡ N, wenn Th(M) = Th(N). Bemerkung 2.2. T ist genau dann vollständig, wenn M ≡ N für jede M, N ⊨ T. Bemerkung 2.3. Wenn A eine gemeinsame Teilmenge von L-Strukturen M und N ist, ist id_{A} : M −−→ N partiel elementar gdw M_{A} ≡ N_{A}. Insbesondere, M ⪯ N gdw M_{M} ≡ N_{M}.

3 Ultraprodukte

Sei I eine Menge.

∅ ≠ B ⊆ P(I) heißt Filterbasis, wenn

• X, Y ∈ B ⇒ ∃Z ∈ B.X ∩ Y ⊇ Z;

• ∅ ∉ B. Eine maximale Filterbasis U heißt Ultrafilter. Dazu äquivalent, U ist eine

Filterbasis, und für alle X ⊆ I, gilt

X ∈ U oder I \ X ∈ U.

Als direkte Folgerung aus dem Zornschen Lemma, haben wir Fakt 3.1. Jede Filterbasis B ⊆ P(I) auf einen Ultrafilter B ⊆ U ⊆ P(I) sich erweitert. Bemerkung 3.2. Fakt ?? ist kein Satz von ZF. Es ist echt schwächer als das Auswahlaxiom modulo ZF.

Bemerkung 3.3. Ultrafilteren sind aufwärts geschlossen: wenn X ⊆ Y, gilt X ∈ U ⇒ Y ∈ U. Eine Filterbasis, die aufwärts geschlossen ist, heißt Filter.

Wenn U ⊆ P(I) ein Ultrafilter ist und (A_{i} : i ∈ I) Mengen sind, ist die Ultraprodukt ∏_{i→U} A_{i} (auch geschrieben ∏_{i∈I} A_{i}/U) die Quotient von der Produkt ∏_{i} A_{i} durch die Äquivalenzrelation

(a_{i})_{i} ∼^{U} (a′_{i})_{i} gdw {i : a_{i} = a′_{i}} ∈ U.

Wenn a_{i} ∈ A_{i}, sei lim_{i→U} a_{i} := (a_{i})_{i}/ ∼^{U}∈ ∏_{i→U} A_{i}.

Wenn U ⊆ P(I) ein Ultrafilter ist und a_{i} sind Elementen von Mengen A_{i} (i ∈ I), ist der Ultralimes lim_{i→U} a_{i} die Klasse von der Sequenz (a_{i})_{i} durch die Äquivalenzrelation (a_{i})_{i} ∼^{U} (a′_{i})_{i} gdw {i : a_{i} = a′_{i}} ∈ U. Wenn A_{i} Mengen sind, ist die Ultraprodukt die Menge aller Ultralimites,

∏_{i→U} A_{i} := ^{∏_{i∈I} A_{i}}/_{∼^{U}} = { lim_{i→U} a_{i} : a_{i} ∈ A_{i}} .

Es gilt lim_{i→U}(a_{i}, b_{i}) = (lim_{i→U} a_{i}, lim_{i→U} b_{i}).

Für Funktionen f_{i} : A_{i} → B_{i}, definieren wir

lim_{i→U} f_{i} : ∏_{i→U} A_{i} → ∏_{i→U} B_{i}

durch

( lim_{i→U} f_{i})( lim_{i→U} a_{i}) := lim_{i→U} f_{i}(a_{i}).

Wenn (M_{i} : i ∈ I) L-Strukturen sind, ist die Ultraprodukt M = ∏_{i→U} M_{i} die L-Struktur sodass

• als Mengen, M := ∏_{i→U} M_{i};

• R^{M} := ∏_{i→U} R^{M_{i}} für R ∈ L ein Relationszeichen;

• f^{M} := lim_{i→U} f^{M_{i}} für f ∈ L ein Funktionszeichen;

• c^{M} := lim_{i→U} c^{M_{i}} für c ∈ L eine Konstante.

Satz 3.4 (Łos). Für L-Strukturen M_{i}, eine L-Formel ϕ(\overline{x}), und \overline{a}_{i} ∈ M_{i},

∏_{i→U} M_{i} ⊨ ϕ( lim_{i→U} \overline{a}_{i}) gdw \{i : M_{i} ⊨ ϕ(\overline{a}_{i})\} ∈ U.

Beweis. Übung.

Wenn U ⊆ P(I) ein Ultrafilter ist, und M eine L-Struktur ist, die Ultrapotenz M^{U} ist ∏_{i→U} M. Dann ist M ⊆ M^{U} durch die

Lemma 3.5. In Bezüg auf die diagonale Einbettung

a ↦ lim_{i→U} a

ist M eine elementare Unterstruktur, M ⪯ M^{U}.

Beweis. Übung.

Ein Ultrafilter U heißt Hauptultrafilter, wenn es gibt i_{0} ∈ I sodass U = {X ⊆ I : i_{0} ∈ X}. Dann ∏_{i→U} M_{i} ≅ M_{i_{0}}.

4 Kompaktheit

Satz 4.1 (Compactness). Wenn jede endliche Teilmenge einer L-Theorie T konsistent ist, ist T konsistent.

Beweis. Sei M_{T′} ⊨ T′ für T′ ⊆_{end} T.

Für T′ ⊆_{end} T, sei [T′] = {T′′ : T′ ⊆ T′′ ⊆_{end} T } ⊆ P^{end}(T). Sei B = {[T′] : T′ ⊆_{end} T } ⊆ P(P^{end}(T)). Dann ist B eine Filterbasis, weil [T′] ∩ [T′′] = [T′ ∪ T′′], und [T′] ≠ ∅ weil T′ ∈ [T′]. Sei U ⊇ B ein Ultrafilter auf P^{end}(T).

Sei M = ∏_{T′→U} M_{T′}. Dann für σ ∈ T, {T′ : M_{T′} ⊨ σ} ⊇ {T′ : σ ∈ T′} = [{σ}] ∈ U, und nach

Łos, M ⊨ σ.

Dann M ⊨ T, und so ist T konsistent.

5 Elementare Erweiterungen

Satz 5.1 (Tarski test). Sei M eine L-Struktur und A eine Teilmenge. Dann Die folgenden Aussagen sind äquivalent:

(i) A die Grundmenge einer elementaren Unterstruktur ist;

(ii) für jede L(A)-Formel in einer freier Variable ϕ(x), wenn M ⊨ ϕ(b) für einige b ∈ M, gilt M ⊨ ϕ(a) für einige a ∈ A.

Beweis.

(i) ⇒ (ii): Sei A die elementare Unterstruktur, die Grundmenge A hat. Falls M ⊨ ∃x.ϕ(x), dann A ⊨ ∃x.ϕ(x); wähle ein a ∈ A mit A ⊨ ϕ(a); aber dann durch Elementarität, M ⊨ ϕ(a) wie gesucht.

(ii) ⇒ (i): Aus (ii) mit ϕ(x) = x ≐ x folgt A ≠ ∅, und aus (ii) mit ϕ(x) = x ≐ f(\overline{a}) folgt, dass A geschlossen unter Funktionen ist. Daher ist A die Grundmenge eine Unterstruktur A.

Wir zeigen durch Induktion über Formelkomplexität, dass für jeden L(A)- Satz σ

A ⊨ σ ⇔ M ⊨ σ.

Dies gilt für atomare σ nach der Definition von Unterstrukturen, und wenn es für σ und σ′ gilt, gilt es offensichtlich auch für ¬σ und (σ ∧ σ′).

Nun nehmen wir an, dass σ = ∃x.ϕ(x), und die Induktionshypothese für ϕ(a) für jede a ∈ A gilt.

Wenn A ⊨ σ, gilt A ⊨ ϕ(a) für einige a ∈ A, somit M ⊨ ϕ(a) durch die Induktionshypothese, daher M ⊨ σ. Umgekehrt, wenn M ⊨ σ, gilt M ⊨ ϕ(b) für einige b ∈ M, so, by (i), M ⊨ ϕ(a) for some a ∈ A, so A ⊨ ϕ(a) by the induction hypothesis, so A ⊨ σ.

TODO: Lowenheim-Skolem; Vaught?

6 TYPEN UND SATURATIERHEIT 7

6 Typen und Saturatierheit

…

Example: non-principal countable ultrapower in countable lang is ℵ_{1}-saturated.

7 Elimination der Quantificatoren