Übungen zur Vorlesung Mathematische Logik SS 2008, Blatt 10

Aufgabe 47. Sei S = {0, f} für ein Konstantensymbol 0 und ein einstelliges Funktionssymbol f. Weiter sei

Φ = {∀x ¬f(x) ≡ 0 ,
∀x (x ≡ 0 ∨ ∃y x ≡ f(y)) ,
∀x∀y (f(x) ≡ f(y) → x ≡ y)}.

Geben Sie drei paarweise nicht isomorphe, abzählbare Modelle von Φ an.

Aufgabe 48. Eine Ordnung 𝔄 = (A, ≤^{𝔄}) ist eine Wohlordnung gdw. jede nicht leere Teilmenge X ⊆ A ein Minimum hat, d.h.: für alle X ⊆ A mit X ≠ ∅ gibt es ein a ∈ X, sodaß für alle b ∈ X : a ≤^{𝔄} b. Sei 𝔄 = (A, ≤^{𝔄}) eine Ordnung. Zeigen Sie, daß folgende Aussagen äquivalent sind:

1. 𝔄 ist eine Wohlordnung.

2. Es gibt keine Folge (a_{i})_{i∈ℕ} paarweise verschiedener Elemente von A mit

… ≤^{𝔄} a_{3} ≤^{𝔄} a_{2} ≤^{𝔄} a_{1}.

Zeigen Sie, daß die Klasse der Wohlordnungen nicht in der ersten Stufe axiomatisierbar ist.

Aufgabe 49. Für eine Symbolmenge S sei L_{M II}^{S} (die monadische Sprache der zweiten Stufe) die Menge der L_{II}^{S}-Ausdrücke, in denen - neben den Zeichen der ersten Stufe - nur einstellige Relationsvariablen auftreten.

1. Geben Sie einen L_{M II}^{{≤}}-Satz φ an, sodaß Mod(φ) die Klasse der Wohlordnungen ist.

2. Geben Sie einen L_{M II}^{{R}}-Satz φ an, sodaß Mod(φ) die Klasse der zusammenhängenden Graphen ist.

Gilt für L_{II}^{S} das Analogon des Endlichkeitssatzes? (Vergleiche Aufgaben 42 und 48.)

Aufgabe 50. Sei S endlich und φ ∈ L_{0}^{S} fest. Man zeige: Es gibt ein polynomielles Verfahren, das angesetzt auf eine endliche Struktur \underline{\underline{𝔄}}, deren Träger die Gestalt [n] für ein geeignetes n ≥ 1 hat, entscheidet, ob 𝔄 ⊧ φ. Beschränken Sie sich der Einfachheit halber auf S = {R} für ein zweistelliges Relationssymbol R.

Zur Kodierung: Wir verwenden das Alphabet Σ = {0, 1}; für die Struktur 𝔄 = ([n], R^{𝔄}) stehe im Register R_{1} das Wort \underbrace{1 … 1}_{n mal} und in R_{2} das Wort der Länge n^{2}, an dessen

((i − 1) · n + j)-ter Stelle eine 1 steht, wenn (i, j) ∈ R^{𝔄}, und eine 0 sonst. Zum Beispiel steht für 𝔄 = ([3], {(1, 1), (1, 3), (2, 1), (2, 3), (3, 3)}) in R_{2} das Wort 101101001.

Hinweis: Führen Sie den Beweis durch Induktion über den Aufbau von φ, wobei man zunächst die zu zeigende Aussage durch eine für solche Induktionen geeignete Aussage für Formeln ersetzt.

Aufgabe 51. Wir setzen voraus, daß ZFC widerspruchsfrei ist. Für jedes r ∈ ℝ sei c_{r} ein neues Konstantensymbol, sodaß c_{r} ≠ c_{s} für r ≠ s. Zeigen Sie, daß die folgende Satzmenge erfüllbar ist:

ZFC ∪ \{¬c_{r} ≡ c_{s} | r, s ∈ ℝ, r ≠ s\} ∪ \{c_{r}\underline{∈}\underline{ω} | r ∈ ℝ\}.

Es gibt also ein Modell der Mengenlehre, in dem es überabzählbar viele natürliche Zahlen gibt. Erklären Sie diesen scheinbaren Widerspruch.

Abgabe: Mittwoch, 9. Juli 2008, vor der Vorlesung.