Mathematische Logik - Sommersemester 2014

Übungsaufgaben  Prof. Dr. Peter Koepke
Serie 7  Dr. Philipp Schlicht

Aufgabe 25 (4 Punkte). Es sei S_{Ar} = {0, 1, +, ·} die erststufige Sprache der Arithmetik. Setze

φ_{t} = ∃v_{2} v_{0} ≡ v_{1} · v_{2}.

Konstruieren Sie eine S_{Ar}-Struktur 𝔄 mit den folgenden Eigenschaften.

(1) In 𝔄 und in der Standardstruktur der natürlichen Zahlen gelten die gleichen S_{Ar}-Sätze (d.h. S_{Ar}-Formeln ohne freie Variablen).

(2) Es existiert ein a ∈ |𝔄| \ {0^{𝔄}} mit der Eigenschaft, dass die Menge

{b ∈ |𝔄| | 𝔄 ⊧ φ_{t}[a, b]}

unendlich ist. (Tipp: Erweitern Sie die Sprache um abzählbar viele neue Konstantensymbole und verwenden Sie entweder den Kompaktheitssatz oder eine Ultraproduktkonstruktion)

Gegeben sei eine nicht-leere Menge I. Wir nennen einen Filter F auf I einen Ultrafilter auf I, falls für alle X ⊆ I entweder X ∈ F oder I \ X ∈ 𝔉 gilt.

Aufgabe 26. (8 Punkte) Beweisen Sie die folgenden Aussagen.

(1) Ein Filter F auf I ist genau dann ein Ultrafilter, wenn er ein maximaler Filter auf I ist (d.h. für jeden Filter F′ auf I mit F ⊆ F′ gilt bereits F = F′).

(2) Es sei U ein Ultrafilter auf I und ⟨M_{i} | i ∈ I⟩ eine Sequenz endlicher Mengen mit der Eigenschaft, dass

X_{n} = { i ∈ I | M_{i} enthält mindestens n Elemente}

für alle n ∈ ℕ ein Element von U ist. Dann ist die Menge ∏_{U} M_{i} unendlich.

(3) Ist I eine unendliche Menge, so ist die Menge der koendlichen Teilmengen von I (d.h. die Menge der X ⊆ I mit I \ X endlich) ein Filter auf I. Dieser Filter ist kein Ultrafilter.

(4) Ist F ein Filter auf einer Menge I, so existiert ein Ultrafilter U auf I mit F ⊆ U. (Tipp: Verwenden Sie das Zorn’sche Lemma und Teil 1 )

Aufgabe 27 (6 Punkte). Beweisen Sie den Kompaktheitssatz mit Hilfe einer Ultraproduktkonstruktion. (Tipp: Betrachten Sie für eine endlich konsistente Formelmenge Φ (d.h. jede endliche Teilmenge von Φ ist konsistent) die Menge I aller endlichen Teilmengen von Φ. Zeigen Sie, dass die Menge

F = {X ⊆ I | ∃σ ∈ I ∀τ ∈ I [σ ⊆ τ → τ ∈ X]}

ein Filter auf I ist. Verwenden Sie dann die Aufgaben 17, 22 und 26 )

Abgabe: Montag, den 02. Juni 2014, vor der Vorlesung.