12. November 2002

Seminar zur Logik: Nichtstandardanalysis

Ultraprodukte und Ultrapotenzen

— Christian Panten —

Vorbemerkung:

Wir fixieren eine Sprache L=(I,J,K,t) und eine nicht-leere Menge S.

Definition 1 (Äquivalenz-Relation)

Sei S eine Menge. Und für alle s ∈ S gebe es eine L-Struktur 𝔄_{s} mit Grundmenge A_{s}. Weiter sei U ein Ultrafilter. Die Äquivalenz-Relation ∼ auf B :≡ ×_{s∈S}A_{s} sei durch

f ∼ g :≡ {s ∈ S | f(s) = g(s)} ∈ U

definiert.

Diese Äquivalenz-Relation ist wohldefiniert.

Beweis:

. f ∼ f, da S ∈ U
. f ∼ g ⇒ g ∼ f, da {s ∈ S | f(s) = g(s)} = {s ∈ S | g(s) = f(s)}
. f ∼ g, g ∼ h ⇒ f ∼ h, da
{s ∈ S | f(s) = g(s)} ∩ {s ∈ S | g(s) = h(s)} =
\underbrace{\{s ∈ S | f(s) = g(s) = h(s)\}}_{∈U, wegen der Schnitteigenschaft von Filter} ⊂ \underbrace{\{s ∈ S | f(s) = h(s)\}}_{∈U,wegen der Abschlußeigenschaft von Filter}

q.e.d.

Zur Erinnerung (Filter und Ultrafilter)

Sei I eine Menge. Dann heißt F Filter auf I, wenn gilt:

(1) F ≠ ∅ und ∅ ∉ F

(2) A, B ∈ F ⇒ A ∩ B ∈ F

(3) A ∈ F, A ⊆ B ⊆ I ⇒ B ∈ F

F heißt Ultrafilter, wenn zusätzlich folgendes gilt:

(4) A ⊆ I ⇒ (A ∈ F ⇔ I \ A ∉ F)

Definition 2 (L-Struktur 𝔄)

Nun definieren wir eine L-Struktur 𝔄 auf A :≡ B/ ∼ :≡ {[h] | h ∈ B}. Relationen: R_{i}([h_{0}] … [h_{t(i)−1}]) :≡ {s ∈ S |R_{i}^{𝔄_{s}} (h_{0}(s) … h_{t(i)−1}(s)) } ∈ U Funktionen: f_{j}([h_{0}] … [h_{t(j)−1}]) :≡ [(f_{j}^{𝔄_{s}} (h_{0}(s) … h_{t(j)−1}(s)) | s ∈ S)] Konstanten: c_{k} :≡ [(c_{k}^{𝔄_{s}} | s ∈ S)]

Die so definierte L-Struktur ist wohldefiniert. Beweis:

R_{i}([h_{0}] … [h_{n−1}]) :≡ {s ∈ S |R_{i}^{𝔄_{s}} (h_{0}(s) … h_{n−1}(s)) } ∈ U

Sei (h_{0}, …, h_{n−1}), (h′_{0}, …, h′_{n−1}) ∈ A^{n} mit ∀j ∈ {0, …, n − 1} h_{j} ∼ h′_{j}

Nun ist zu zeigen:

{s ∈ S | R_{i}^{𝔄_{s}} (h_{0}(s) … h_{n−1}(s)) } ∈ U ⇔
{s ∈ S | R_{i}^{𝔄_{s}} (h′_{0}(s) … h′_{n−1}(s)) } ∈ U

Wegen der Symmetrie genügt es „⇒“ zu zeigen: Sei {s ∈ S | R_{i}^{𝔄_{s}} (h_{0}(s) … h_{n−1}(s)) } ∈ U.

∀j ∈ {0, …, n − 1} {s ∈ S | h_{j}(s) = h′_{j}(s)} ∈ U

⇒ ⋂_{j≤n−1} {s ∈ S | h_{j}(s) = h′_{j}(s)} ∈ U wegen Filtereigenschaft (2)

⇒ \underbrace{\{s ∈ S | R_{i}^{𝔄_{s}} (h_{0}(s) … h_{n−1}(s)) \}}_{∈U} ∩ \underbrace{⋂_{j≤n−1} \{s ∈ S | h_{j}(s) = h′_{j}(s)\}}_{∈U}

⊂ {s ∈ S | R_{i}^{𝔄_{s}} (h′_{0}(s) … h′_{n−1}(s)) } ∈ U wegen Filtereigenschaft (3)

□

f_{j}([h_{0}] … [h_{n−1}]) :≡ [(f_{j}^{𝔄_{s}} (h_{0}(s) … h_{n−1}(s)) | s ∈ S)]

Sei (h_{0}, …, h_{n−1}), (h′_{0}, …, h′_{n−1}) ∈ A^{n} mit ∀l ∈ {0, …, n − 1} h_{l} ∼ h′_{l} Nun ist zu zeigen:

(f_{j}^{𝔄_{s}} (h_{0}(s) … h_{n−1}(s)) | s ∈ S) ∼ (f_{j}^{𝔄_{s}} (h′_{0}(s) … h′_{n−1}(s)) | s ∈ S)

\underbrace{⋂_{l≤n} \underbrace{\{s ∈ S | h_{l}(s) = h′_{l}(s)\}}_{∈U}}_{∈U} ⊂

{s ∈ S | f_{j}^{𝔄_{s}} (h_{0}(s) … h_{n−1}(s)) = f_{j}^{𝔄_{s}} (h′_{0}(s) … h′_{n−1}(s)) } ∈ U

wegen Filtereigenschaft(3).

⇔ f_{j} ([h_{0}] … [h_{n−1}]) ∼ f_{j} ([h′_{0}] … [h′_{n−1}])

□

q.e.d.

Definition 3 (Ultraprodukt und Ultrapotenz)

Die oben definierte L-Struktur heißt das Ultraprodukt der (𝔄_{s} | s ∈ S) über U. Wir bezeichnen das Ultraprodukt mit ∏_{s∈S} 𝔄_{s}/U. Sind alle 𝔄_{s} gleich einer L-Struktur 𝔅, so schreiben wir 𝔅^{S}/U. Diese L-Struktur heißt dann die Ultrapotenz von 𝔅 über U.

Satz 4 (Satz von Łoś)

Sei 𝔄 :≡ ∏_{s∈S} 𝔄_{s}/U.

(a) Sei r(x_{0}, ..., x_{n})∈ Tm(L) und seien [h_{0}], ..., [h_{n}] ∈ A. Dann gilt r^{𝔄}[[h_{0}], ..., [h_{n}]] = [ (r^{𝔄_{s}} [h_{0}(s), ..., h_{n}(s)] | s ∈ S) ].

(b) Sei φ (x_{0}, …, x_{n}) ∈ Fml(L) und seien [h_{0}], ..., [h_{n}] ∈ A. Dann gilt 𝔄 ⊧ φ[[h_{0}], …, [h_{n}]] ⟷ {s ∈ S | 𝔄_{s} ⊧ φ [h_{0}(s), …, h_{n}(s)] } ∈ U.

Zur Erinnerung (T m(L) und Belegung von Termen)

Sei L eine Sprache. Dann hat die Menge T m(L) der Terme von L folgende Eigenschaften:

. ∀n < ω v_{n} ∈ T m(L) . ∀k ∈ K c_{k} ∈ T m(L) . ∀x_{0}, …, x_{n} ∈ T m(L) ∀f_{n} ∈ F : f_{n}x_{0} … x_{n} ∈ T m(L)

Belegung von Termen Sei β eine Belegung.

(1) v_{n}^{𝔄}[β] :≡ β(v_{n})

(2) c_{k}^{𝔄}[β] :≡ c_{k}

(3) (f_{j}s(0) … s(n))^{𝔄}[β] :≡ f_{j}(s(0)^{𝔄}[β], …, s(n)^{𝔄}[β])

Beweis:

(a) Induktion über den Termenaufbau

Fall 1 r = v_{n} eine Variable Sei [h] ∈ A.

[(r^{𝔄_{s}}[h(s)] | s ∈ S)] = [(h(s) | s ∈ S)] = [h] = r^{𝔄}[[h]]
□

Fall 2 r = c_{k} eine Konstante

[(r^{𝔄_{s}} | s ∈ S)] = [(c_{k}^{𝔄_{s}} | s ∈ S)] = c_{k} = r^{𝔄}
□

Fall 3 r = f_{j}r_{0} … r_{n} mit r_{0}, …, r_{n} ∈ T m(L) und r_{0}, …, r_{n} erfüllen (a) Seien [h_{1}], …, [h_{k}] ∈ A.

r^{𝔄}[[h_{1}], …, [h_{k}]] =^{Belegung} f_{j}^{𝔄} (r_{0}^{𝔄}[[h_{1}], …, [h_{k}]], …, r_{n}^{𝔄}[[h_{1}], …, [h_{k}]])

=^{Vor} f_{j}^{𝔄}( [(r_{0}^{𝔄_{s}}[h_{1}(s), …, h_{k}(s)] | s ∈ S)] , …, [(r_{n}^{𝔄_{s}}[h_{1}(s), …, h_{k}(s)] | s ∈ S)] )

=^{Def. von f} [(f_{j}^{𝔄_{s}}(r_{0}^{𝔄_{s}}[h_{1}(s), …, h_{k}(s)], …, r_{n}^{𝔄_{s}}[h_{1}(s), …, h_{k}(s)]) | s ∈ S)]

=^{Belegung} [((f_{j}r_{0} … r_{n})^{𝔄_{s}}[h_{1}(s), …, h_{k}(s)] | s ∈ S)]

= [(r^{𝔄_{s}}[h_{1}(s), …, h_{k}(s)] | s ∈ S)]

□

Zur Erinnerung (F ml(L) und Belegung von Formeln)

Sei L eine Sprache. Dann hat die Menge F ml(L) der Formeln von L folgende Eigenschaften: . At(L) ⊂ F ml(L) . ∀φ, ψ ∈ F ml(L) : (φ ∧ ϕ) ∈ F ml(L) . ∀φ ∈ F ml(L) : ¬φ ∈ F ml(L) . ∀n < ω∀φ ∈ F ml(L) : ∀v_{n}φ ∈ F ml(L)

Wobei man mit At(L) die atomaren Formeln von L bezeichnet: . At(L) := {s_{1} = s_{2} | s_{1} ∈ F ml(L) ∧ s_{2} ∈ F ml(L)}

∪ {R_{i}s_{0} … s_{n} | i ∈ I ∧ s : n + 1 ⟶ T m(L)}

Belegung von Formeln

Sei β eine Belegung.

. 𝔄 ⊧ s_{1} = s_{2} [β] :≡ s_{1}^{𝔄}[β] = s_{2}^{𝔄}[β]

. 𝔄 ⊧ R_{i}s_{0} … s_{n} [β] :≡ R_{i} (s_{0}^{𝔄}[β], …, s_{n}^{𝔄}[β]) . 𝔄 ⊧ (φ_{1} ∧ φ_{2})[β] :≡ (𝔄 ⊧ φ_{1}[β] ∧ 𝔄 ⊧ φ_{2}[β]) . 𝔄 ⊧ ¬φ[β] :≡ ¬𝔄 ⊧ φ[β]

. 𝔄 ⊧ ∀v_{n}φ[β] :≡ ∀a ∈ A 𝔄 ⊧ φ [β \frac{a}{v_{n}} ]

(b) Induktion über den Formelaufbau Fall 1.1 φ ∈ At(L) : φ = r_{1} = r_{2} mit r_{1}, r_{2} ∈ T m(L)

Seien [h_{1}], …, [h_{n}] ∈ A.

𝔄 ⊧ φ[[h_{1}], …, [h_{n}]] ⇔^{Belegung} r_{1}^{𝔄}[[h_{1}], …, [h_{n}]] = r_{2}^{𝔄}[[h_{1}], …, [h_{n}]]

⇔^{(a)} [(r_{1}^{𝔄_{s}}[h_{1}(s), …, h_{n}(s)] | s ∈ S)] = [(r_{2}^{𝔄_{s}}[h_{1}(s), …, h_{n}(s)] | s ∈ S)]

⇔ (r_{1}^{𝔄_{s}}[h_{1}(s), …, h_{n}(s)] | s ∈ S) ∼ (r_{2}^{𝔄_{s}}[h_{1}(s), …, h_{n}(s)] | s ∈ S)

⇔^{Def. von ∼} {s ∈ S | r_{1}^{𝔄_{s}}[h_{1}(s), …, h_{n}(s)] = r_{2}^{𝔄_{s}}[h_{1}(s), …, h_{n}(s)]} ∈ U

⇔^{Belegung} {s ∈ S | 𝔄_{s} ⊧ φ[h_{1}(s), …, h_{n}(s)]} ∈ U

□

Fall 1.2 φ ∈ At(L) : φ = R_{i}r_{0} … r_{n} mit r_{0}, …, r_{n} ∈ T m(L) Seien [h_{1}], …, [h_{l}] ∈ A.

𝔄 ⊧ φ[[h_{1}], …, [h_{l}]] ⇔^{Belegung} R_{i}(r_{0}^{𝔄}[[h_{1}], … [h_{l}]] … r_{n}^{𝔄}[[h_{1}], … [h_{l}]])

⇔^{(a)} R_{i}( [(r_{0}^{𝔄_{s}}[h_{1}(s), …, h_{l}(s)])] , …, [(r_{n}^{𝔄_{s}}[h_{1}(s), …, h_{l}(s)])] )

⇔^{Def. von Relationen} {s ∈ S | R_{i}^{𝔄_{s}} (r_{0}^{𝔄_{s}}[h_{1}(s), …, h_{l}(s)], …, r_{n}^{𝔄_{s}}[h_{1}(s), …, h_{l}(s)]) } ∈ U

⇔^{Belegung} {s ∈ S | 𝔄_{s} ⊧ φ[h_{1}(s), …, h_{l}(s)]} ∈ U

□

Fall 2 φ = ¬ψ und (b) gilt für ψ ∈ F ml(L)

Seien [h_{1}], …, [h_{n}] ∈ A. Da U ein Ultrafilter ist, folgt:

{s ∈ S | 𝔄_{s} ⊧ ψ[h_{1}(s), …, h_{n}(s)]} ∉ U

⇔ {s ∈ S | ¬𝔄_{s} ⊧ ψ[h_{1}(s), …, h_{n}(s)]} ∈ U (1)

Damit folgt dann:

𝔄 ⊧ φ[[h_{1}], …, [h_{n}]] ⇔^{Belegung} ¬𝔄 ⊧ ψ[[h_{1}], …, [h_{n}]]

⇔^{Vor.} {s ∈ S | 𝔄_{s} ⊧ ψ[h_{1}(s), …, h_{n}(s)]} ∉ U

⇔^{(1)} {s ∈ S | ¬𝔄_{s} ⊧ ψ[h_{1}(s), …, h_{n}(s)]} ∈ U

⇔^{Belegung} {s ∈ S | 𝔄_{s} ⊧ φ[h_{1}(s), …, h_{n}(s)]} ∈ U

□

Fall 3 φ = (ψ ∧ χ) und (b) gilt für ψ, χ ∈ F ml(L)

Seien [h_{1}], …, [h_{n}] ∈ A. Da U ein Ultrafilter und gegen endliche Schnittund Obermengenbildung abgeschlossen ist, gilt:

∀x, y ⊆ S : (x ∈ U ∧ y ∈ U) ⇔ x ∩ y ∈ U (2)

Daraus folgt dann:

𝔄 ⊧ φ[[h_{1}], …, [h_{n}]] ⇔^{Belegung} 𝔄 ⊧ ψ[[h_{1}], …, [h_{n}]] ∧ 𝔄 ⊧ χ[[h_{1}], …, [h_{n}]]

⇔^{Vor.} {s ∈ S | 𝔄_{s} ⊧ ψ[h_{1}(s), …, h_{n}(s)]} ∈ U ∧ {s ∈ S | 𝔄_{s} ⊧ χ[h_{1}(s), …, h_{n}(s)]} ∈ U

⇔^{(2)} {s ∈ S | 𝔄_{s} ⊧ ψ[h_{1}(s), …, h_{n}(s)]} ∩ {s ∈ S | 𝔄_{s} ⊧ χ[h_{1}(s), …, h_{n}(s)]} ∈ U

⇔ {s ∈ S | 𝔄_{s} ⊧ ψ[h_{1}(s), …, h_{n}(s)] ∧ 𝔄_{s} ⊧ χ[h_{1}(s), …, h_{n}(s)]} ∈ U
⇔ {s ∈ S | 𝔄_{s} ⊧ φ[h_{1}(s), …, h_{n}(s)]} ∈ U
□

Fall 4 φ = ∀xψ und (b) gilt für ψ ∈ F ml(L) Seien [h_{0}], …, [h_{n}] ∈ A. Für diesen Fall ist zu zeigen, daß

(i) ∀[h] ∈ A {s ∈ S | 𝔄_{s} ⊧ ψ[h(s), h_{0}(s), …, h_{n}(s)]} ∈ U
(ii) {s ∈ S | ∀a ∈ A_{s} 𝔄_{s} ⊧ ψ[a, h_{0}(s), …, h_{n}(s)]} ∈ U (3)

äquivalent sind.

Beweis:

(i) ⇒ (ii) Angenommen: (ii) ist nicht erfüllt, d.h.

{s ∈ S | ∀a ∈ A_{s} 𝔄_{s} ⊧ ψ[a, h_{0}(s), …, h_{n}(s)]} ∉ U

⇒^{U Ultrafilter} Z := {s ∈ S | ∃a ∈ A_{s} ¬𝔄_{s} ⊧ ψ[a, h_{0}(s), …, h_{n}(s)]} ∈ U

Dann definiere die folgende Funktion (mit Hilfe des Auswahlaxions (AC)):

h : S ⟶ ⋃_{s∈S} A_{s}

h(s) := \{ \begin{matrix}a ∈ A_{s} mit ¬𝔄_{s} ⊧ ψ[a, h_{0}(s), …, h_{n}(s)] : & s ∈ Z \\ a ∈ A_{s} beliebig : & sonst \end{matrix}

Es gilt nun:

Z ⊂ \underbrace{\{s ∈ S | ¬𝔄_{s} ⊧ ψ[h(s), h_{0}(s), …, h_{n}(s)]\}}_{∈U, wegen Filtereigenschaft (3)}

Nach Voraussetzung ist aber das Kompliment dieser Menge in U

⇒ Widerspruch zur Definition von Ultrafilter (ii) ⇒ (i)

Sei h ∈ ×_{s∈S}A_{s} beliebig. Es gilt nun:

{s ∈ S | ∀a ∈ A_{s} 𝔄_{s} ⊧ ψ[a, h_{0}(s), …, h_{n}(s)]} ⊂

{s ∈ S | 𝔄_{s} ⊧ ψ[h(s), h_{0}(s), …, h_{n}(s)]}

Nach Voraussetzung (ii):

{s ∈ S | ∀a ∈ A_{s} 𝔄_{s} ⊧ ψ[a, h_{0}(s), …, h_{n}(s)]} ∈ U

⇒^{Filtereigenschaft (3)} {s ∈ S | 𝔄_{s} ⊧ ψ[h(s), h_{0}(s), …, h_{n}(s)]} ∈ U

q.e.d. (3)

Nun folgt der Beweis von Fall 4:

𝔄 ⊧ φ[[h_{1}], …, [h_{n}]] ⇔^{Belegung} ∀a ∈ A 𝔄 ⊧ ψ[a, [h_{0}], …, [h_{n}]]

⇔ ∀[h] ∈ A 𝔄 ⊧ ψ[[h], [h_{0}], …, [h_{n}]]

⇔^{Vor.} ∀[h] ∈ A {s ∈ S | 𝔄_{s} ⊧ ψ[h(s), h_{0}(s), …, h_{n}(s)]} ∈ U

⇔^{(3)} {s ∈ S | ∀a ∈ A_{s} 𝔄_{s} ⊧ ψ[a, h_{0}(s), …, h_{n}(s)]} ∈ U

⇔^{Belegung} {s ∈ S | 𝔄_{s} ⊧ φ[h_{0}(s), …, h_{n}(s)]} ∈ U

q.e.d.

Korollar 5 (L-Sätze)

Sei φ ∈ Fml_{0}(L). Dann gilt: ∏_{s∈S} 𝔄_{s}/U ⊧ φ ⟺ {s ∈ S | 𝔄_{s} ⊧ φ} ∈ U.

Beweis:

Der Beweis folgt sofort aus dem Satz von Łoś(b).

φ \underbrace{(x_{0}, …, x_{n})}_{n+1 freie Variablen} ∈ F ml_{n+1}(L)

q.e.d.

Zur Erinnerung (Einbettung, Isomorphismus, elementare Einbettung) Seien 𝔄 und 𝔅 L-Strukturen und h : |𝔄| ⟶ |𝔅| eine Abbildung. h ist eine Einbettung, wenn folgendes gilt:

(1) h ist injektiv

(2) ∀i ∈ I ∀x⃗ ∈ A^{t(i)}(R_{i}^{𝔄} x⃗ ↔ R_{i}^{𝔅}h(x⃗))

h heißt Isomorphismus, wenn zusätzlich noch folgendes gilt:

(3) h ist bijektiv

h ist eine elementare Einbettung, wenn gilt:

(1) ∀n < ω ∀φ ∈ F ml_{n}(L) :

(∀h_{1}, …, h_{n} ∈ |𝔄|^{n} : 𝔄 ⊧ φ[h_{1}, …, h_{n}] ⟷ 𝔅 ⊧ φ[h(h_{1}), …, h(h_{n})])

Korollar 6 (elementare Einbettung)

Sei 𝔅 eine L-Struktur. Dann ist durch ι(b) :≡ [ (b | s ∈ S) ] eine elementare Einbettung ι : 𝔅 ≺ 𝔅^{S}/U gegeben.

Beweis: Sei φ(x_{1}, …, x_{n}) ∈ F ml_{n}(L). Sei b_{1}, …, b_{n} ∈ |𝔅| beliebig. Dann gilt:

𝔅 ⊧ φ[b_{1}, …, b_{n}] ⇔ \underbrace{\{s ∈ S | 𝔅 ⊧ φ[b_{1}, …, b_{n}]\}}_{∈ \{∅, S\}} ∈ U

⇔^{Łoś(b)} 𝔅^{S}/U ⊧ φ[ι(b_{1}), …, ι(b_{n})]

q.e.d.

Bei einem Ultraprodukt müssen die einzelnen Faktoren nicht notwendig elementare Substrukturen des Ultraproduktes sein. I.A. sind sie zu diesem noch nicht einmal elementar äquivalent.

Beispiel 7 (Primzahlen)

Sei F der Filter der coendlichen Teilmengen der Menge ℙ der Primzahlen und U ⊃ F ein Ultrafilter. Für p ∈ ℙ sei 𝔽_{p} der Körper mit p Elementen (also 𝔽_{p} = ℤ/pℤ). Dann ist 𝔽 :≡ ∏_{p∈ℙ} 𝔽_{p}/U ein Körper der Charakteristik 0. Dies folgt aus dem Satz von Łoś(a) und aus der Eigenschaft, daß für alle p ∈ ℙ {q ∈ ℙ | 𝔽_{q} ⊧ ¬C_{p}} = ℙ \ {p} ∈ U ist.

Zur Erinnerung (elementare Substrukturen, elementare Abbildungen, elementar äquivalent, coendliche Teilmengen, Charakteristik) Seien 𝔄, 𝔅 L-Strukturen . Dann ist 𝔄 eine elementare Substruktur von 𝔅, wenn gilt:

(i) 𝔄 ⊂ 𝔅 (ii) id : 𝔄 ≺ 𝔅

𝔄 ≺ 𝔅 ist eine elementare Abbildung, wenn gilt:

(i) h : |𝔄| ⟶ |𝔅| (ii) ∀n < ω ∀φ ∈ F ml_{n}(L) ∀a⃗ ∈ |𝔄|^{n} (𝔄 ⊧ φ[a⃗] ↔ 𝔅 ⊧ φ[h(a⃗)])

𝔄 und 𝔅 sind elementar äquivalent, wenn gilt:

. T h(𝔄) ≡ T h(𝔅)
wobei T h(𝔄) :≡ {φ ∈ F ml_{0}(L) | 𝔄 ⊧ φ}

Filter der coendlichen Teilmengen der Menge ℙ:

. C := {A ⊆ ℙ | ℕ \ A ist endlich}

Charakteristik

. C_{p} :≡ ∑_{i<p} 1 = 0
. für 𝔽_{p} gilt: 𝔽_{p} ⊧ C_{p}

Zur Erinnerung (Hauptultrafilter)

U ist Hauptultrafilter von S, wenn gilt: ∃s_{o} ∈ S : U = {x ⊂ S | s_{o} ∈ x}

Korollar 8 (Hauptultrafilter)

Ist U ein Hauptultrafilter, d.h. ∃s_{0} ∈ S mit U = {x ⊂ S | s_{0} ∈ x}, so ist ∏_{s∈S} 𝔄_{s}/U ≅ 𝔄_{s_{0}}.

Beweis: Sei 𝔄 :≡ ∏_{s∈S} 𝔄_{s}/U. F : |𝔄| ⟶ |𝔄_{s_{0}}| mit F ([h]) = h(s_{o}) ist isomorph. Sei [f], [g] ∈ |𝔄|

[f] = [g] ⇔ f ∼ g ⇔^{U Hauptultrafilter} f(s_{0}) = g(s_{0})
⇔ F ([f]) = F ([g])

F injektiv angenommen: ∃[f], [g] ∈ |𝔄| : F ([f]) = F ([g]) und f ≁ g

F ([f]) = F ([g]) ⇔ f(s_{0}) = g(s_{0}) ⇔ {s ∈ S | f(s) = g(s)} ∈ U

⇔ f ∼ g Widerspruch zur Annahme

□

F surjektiv

da U Hauptultrafilter gilt:

\overline{\overline{|𝔄|}} = \overline{\overline{|𝔄_{s_{0}}|}}
□

Relationen Sei R_{i} eine n-stellige Relation von 𝔄 und [h_{1}], …, [h_{n}] ∈ |𝔄| zu zeigen: R_{i}^{𝔄}([h_{1}], …, [h_{n}]) ↔ R_{i}^{𝔄_{s_{0}}} (F ([h_{1}]), …, F ([h_{n}]))

R_{i}^{𝔄}([h_{1}], …, [h_{n}]) ⇔ {s ∈ S | R_{i}^{𝔄_{s}}(h_{1}(s), …, h_{n}(s))} ∈ U

⇔ s_{0} ∈ {s ∈ S | R_{i}^{𝔄_{s}}(h_{1}(s), …, h_{n}(s))}
⇔ R_{i}^{𝔄_{s_{0}}} (h_{1}(s), …, h_{n}(s))

□

q.e.d.

Satz 9 (Kompaktheitssatz) Sei Φ ⊂ Fml_{0}(L) und jede endliche Teilmenge s ⊂ Φ habe ein Modell 𝔄_{s}. Dann existiert ein Ultrafilter U auf S :≡ \{s ⊂ Φ | \overline{\overline{s}} < ℵ_{0}\}, so daß ∏_{s∈S} 𝔄_{s}/U ein Modell von Φ ist. Dies impliziert: Ist Φ endlich erfüllbar, so ist Φ erfüllbar. (Kompaktheitssatz) Beweis:

Zur Erinnerung (Kompaktheitssatz)

Sei Φ ⊂ F ml_{0}(L).

. Erf(Φ) ⇔ ∀Φ′ ⊂ Φ (\overline{\overline{Φ′}} < ℵ_{0} → Erf(Φ′)) . Φ ⊧ φ ⇔ ∃Φ′ ⊂ Φ (\overline{\overline{Φ′}} < ℵ_{0} ∧ Φ′ ⊧ φ)

Definiere für φ ∈ F ml_{0}(L) : <φ>:≡ {s ∈ S | φ ∈ s} und E :≡ { <φ> | φ ∈ Φ} Dann hat E die endliche Durchschnittseigenschaft, da

⋂_{i<n} <φ_{i}> ∋ {φ_{i} | i < n}

Zur Erinnerung (endliche Durchschnittseigenschaft)

E hat die endliche Durchschnittseigenschaft, wenn gilt: . ∀E′ ⊂ E (\overline{\overline{E′}} < ℵ_{0} → ⋂ E′ ≠ ∅)

Sei U ⊃ E ein Ultrafilter auf S.

U existiert: [Satz 12.12 (Skript)]

E ⊂ P ot(S) : ∃U Ultrafilter auf S ⇔ E hat die endliche Durchschnittseigenschaft

F :≡ \{y ⊂ S | ∃E′ ⊂ E (\overline{\overline{E′}} < ℵ_{0} ∧ y ⊃ \underbrace{⋂ E′}_{≠∅} )\}

Für diesen Beweis benötigen wir nur die eine Richtung („⇐“). zu zeigen: F ist ein eigentlicher Filter auf S, der E umfaßt. (1) E hat die endliche Durchschnittseigenschaft ⇒ ∅ ∉ F

(2) F ist gegen Obermengenbildung abgeschlossen.

x ⊂ y ⊂ S : x ∈ F ⇒ ∃E′ ⊂ E (\overline{\overline{E′}} < ℵ_{0} ∧ \underbrace{x}_{y} ⊃ ⋂ E′)

(3) y_{1} ⊃ ⋂ E′ und y_{2} ⊃ ⋂ E′′ mit E′, E′′ ⊂ E endlich

y_{1} ∩ y_{2} ⊃ ⋂ ( \underbrace{E′ ∪ E′′}_{⊂E endlich} )

⇒^{Def. von F} y_{1} ∩ y_{2} ∈ F

Nach dem Zorn’schen Lemma wähle nun ein ⊂-maximales Element U in

F := {G ⊂ P ot(S) | F ⊂ G ∧ G ist eigentlicher Filter auf S}

U ist ein Ultrafilter.

Sei φ ∈ Φ so gilt: 𝔄_{s} ⊧ φ für jedes s ∈ S mit φ ∈ s. Also ist: s ∈ <φ> Somit gilt:

{s ∈ S | 𝔄_{s} ⊧ φ} ⊃ <φ>

und weil <φ>∈ U ⇒^{Obermengenabschluß} {s ∈ S | 𝔄_{s} ⊧ φ} ∈ U

d.h. ∏_{s∈S} 𝔄_{s}/U ⊧ φ nach Korollar 5.

q.e.d.

Definition 10 (Δ-elementar)

Eine Klasse K von L-Strukturen heißt Δ-elementar genau dann, wenn ∃Φ ⊂ Fml_{0}(L) mit K = Mod^{L}(Φ). Wobei Mod^{L}(Φ) definiert ist als:

Mod^{L}(Φ) = {𝔄 | 𝔄 ist L-Struktur ∧ 𝔄 ⊧ Φ}

Satz 11 (Δ-elementar)

Sei κ eine Menge von L-Strukturen. κ ist genau dann Δ-elementar, wenn κ bzgl. elementarer Äquivalenz und gegen Ultraproduktbildung abgeschlossen ist.

Beweis:

Zur Erinnerung (Δ-elementar, elementar äquivalent) . κ Δ − elementar ⇔ ∃Φ ⊂ F ml_{0}(L) : κ = Mod^{L}(Φ) . 𝔄 und 𝔅 sind elementar äquivalent ⇔ T h(𝔄) ≡ T h(𝔅)

wobei Th(𝔄) :≡ {φ ∈ F ml_{0}(L) | 𝔄 ⊧ φ}

„ ⇒ “ Sei κ Δ-elementar, d.h. ∃Φ ∈ F ml_{0}(L) κ = Mod^{L}(Φ)

(1) Sei 𝔄 ∈ κ und 𝔅 eine L-Struktur mit 𝔄 ≡ 𝔅

⇒ 𝔅 ⊧ Φ also 𝔅 ∈ κ

(2) Sei S eine Menge und U ein Ultrafilter auf S und sei ∀s ∈ S : 𝔄_{s} ∈ κ

⇒ ∀s ∈ S : 𝔄_{s} ⊧ Φ

⇒^{Korollar 5} ∏_{s∈S} 𝔄_{s}/U ⊧ Φ

⇒ ∏_{s∈S} 𝔄_{s}/U ∈ κ

„ ⇐ “ Setze Φ :≡ {φ ∈ F ml_{0}(L) | ∀𝔄 ∈ κ : 𝔄 ⊧ φ}

⇒ κ ⊂ Mod^{L}(Φ)

Wir zeigen nun: Mod^{L}(Φ) ⊂ κ Fixiere dafür 𝔅 ∈ Mod^{L}(Φ). Sei Ψ :≡ T h(𝔅) und S :≡ \{s ⊂ Ψ | \overline{\overline{s}} < ℵ_{0}\}

zu zeigen: ∀s ∈ S ∃𝔄_{s} ∈ κ : 𝔄_{s} ⊧ s (3) Beweis: angenommen: es gilt nicht.

⇒ ∃s_{0} ∈ S mit 𝔄 ⊧ ¬ ⋀ s_{0} für alle 𝔄 ∈ κ ⇒ ¬ ⋀ s_{0} ∈ Φ ⇒ 𝔅 ⊧ ¬ ⋀ s_{0}

Da s_{0} ⊂ Ψ ≡ T h(𝔅) gilt aber: 𝔅 ⊧ ⋀ s_{0} Widerspruch

q.e.d. (3)

(3) ⇒^{Satz 9} es gibt einen Ultrafilter U auf S mit ∏_{s∈S} 𝔄_{s}/U ⊧ Ψ

κ ist abgeschlossen gegen Ultraproduktbildung

⇒ ∏_{s∈S} 𝔄_{s}/U ∈ κ

Ψ = T h(𝔅). Und 𝔅 und ∏_{s∈S} 𝔄_{s}/U sind elementar äquivalent. κ ist abgeschlossen bzgl. elementarer Äquivalenz ⇒ 𝔅 ∈ κ.

q.e.d.

Definition 12 (elementare Klassen von L-Strukturen )

Eine Klasse K von L-Strukturen heißt elementar genau dann, wenn ∃φ ∈ Fml_{0}(L) mit K = Mod^{L}(φ).

Korollar 13 (elementare Klassen von L-Strukturen )

Eine Klasse κ von L-Strukturen ist genau dann elementar, wenn sowohl κ als auch ihr Komplement κ^{∗} :≡ {𝔄 | 𝔄 ist eine L-Struktur und 𝔄 ∉ κ} bzgl. elementarer Äquivalenz und gegen Ultraproduktbildung abgeschlossen sind.

Beweis: „ ⇒ “ κ elementar ⇒ ∃φ ∈ F ml_{0}(L) : κ = Mod^{L}(φ) mit Φ = {φ} folgt die Behauptung des Korollars aus Satz 10.

„ ⇐ “ Sei κ und κ^{∗}Δ-elementar etwa κ = Mod^{L}(Φ) und κ^{∗} = Mod^{L}(Φ^{∗}) mit Φ, Φ^{∗} ∈ F ml_{0}(L) Angenommen: κ ist nicht elementar

daraus folgt, daß es zu jedem endlichen Φ′ ⊂ Φ eine L-Struktur 𝔄 gibt mit 𝔄 ⊧ Φ′ aber ¬𝔄 ⊧ Φ. ⇒ 𝔄 ∉ κ also 𝔄 ∈ κ^{∗} und somit 𝔄 ⊧ Φ^{∗} ⇒ Φ ∪ Φ^{∗} ist endlich erfüllbar ⇒^{Kompaktheit} ∃ ein Modell 𝔄 ⊧ Φ ∪ Φ^{∗} Jedoch gilt: κ ∩ κ^{∗} = ∅ ⇒ Widerspruch zur Annahme Also ist κ elementar.

q.e.d.