Übungen zur Vorlesung Mathematische Logik

SS 2009, Blatt 11

Aufgabe 1.

(a). Sei S beliebig. Geben Sie einen L_{II}^{S}-Satz φ an, so daß

Mod(φ) = {𝔄 | 𝔄 S-Struktur, A endlich, |A| gerade}.

(b). Seien X und Y einstellige Relationsvariablen. Geben Sie einen L_{II}^{S_{Grp}}- Ausdruck φ(X, Y) mit freien Variablen X und Y an, so daß für alle Gruppen 𝔊 und alle M, U ⊆ G gilt: 𝔊 ⊧ φ[M, U] genau dann, wenn U der Träger der von M erzeugten Untergruppe von 𝔊 ist. Hierbei bedeutet 𝔊 ⊧ φ[M, U], daß (𝔊, γ) ⊧ φ mit γ(X) = M und γ(Y) = U gilt.

Aufgabe 2. 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.

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

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

(c). Gilt für L_{M II}^{S} das Analogon des Endlichkeitssatzes?

Aufgabe 3. Sei S beliebig. Zeigen Sie, daß zu jedem L_{II}^{S}-Satz ein logisch äquivalenter L_{II}^{S}-Satz existiert, in dem keine Funktionsvariablen vorkommen.

Aufgabe 4. Sei S endlich.

(a). Sei φ ∈ L_{0}^{S} fest. Zeigen Sie: Es gibt ein polynomielles Verfahren, welches angesetzt auf die Kodierung einer endlichen Struktur 𝔄, 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 zunächst die zu zeigende Aussage durch eine für solche Induktionen geeignete Aussage über Ausdrücke ersetzt wird.

(b). Sei φ = ∃X_{1} … ∃X_{m}ψ ein fester L_{II}^{S}-Satz, wobei X_{1}, …, X_{m} Relationsvariablen beliebiger Stellenzahl sind und ψ keine Quantoren zweiter Stufe enthält. Zeigen Sie: Es gibt ein NPTIME-Verfahren, welches angesetzt auf die Kodierung einer endlichen Struktur 𝔄, deren Träger die Gestalt [n] für ein geeignetes n ∈ ℕ hat, entscheidet, ob 𝔄 ⊧ φ.

Aufgabe 5. Wir setzen voraus, daß ZFC widerspruchsfrei ist. Für jedes r ∈ ℝ sei c_{r} ein neues Konstantensymbol, so daß 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, 15. Juli, vor der Vorlesung.

Die Übungsblätter und die Einteilung der Übungen findet man auch unter

http://home.mathematik.uni-freiburg.de/bjoern/lehre/logik09/logik09.html