Übungen zur Vorlesung Mathematische Logik

SS 2009, Blatt 9

Aufgabe 1. Zeigen Sie für jede Symbolmenge S, daß die Klasse der unendlichen S-Strukturen in der ersten Stufe axiomatisierbar ist, aber nicht endlich axiomatisierbar.

Aufgabe 2. Eine Ordnung 𝔄 = (A, ≤^{𝔄}) ist eine Wohlordnung genau dann, wenn jede nicht leere Teilmenge X ⊆ A ein Minimum hat, d.h.: für alle X ⊆ A mit X ≠ ∅ gibt es ein a ∈ X, so daß für alle b ∈ X gilt: a ≤^{𝔄} b.

(a). Welche der folgenden Ordnungen sind Wohlordungen?

(ℕ, ≤^{𝔑}), (ℤ, ≤^{ℨ}), (ℝ, ≤^{ℜ})

Hierbei sind ≤^{𝔑}, ≤^{ℨ}, ≤^{ℜ} jeweils die natürlichen Ordnungsrelationen auf ℕ, ℤ bzw. ℝ.

(b). Sei 𝔄 = (A, ≤^{𝔄}) eine Ordnung. Zeigen Sie, daß folgende Aussagen äquivalent sind:

(i) 𝔄 ist eine Wohlordnung

(ii) Es gibt keine Folge (a_{i})_{i∈ℕ} paarweise verschiedener Elemente von

A mit

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

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

Aufgabe 3. Sei 𝔊 = (G, E^{𝔊}) ein Graph.

(a). Ein Tupel (a_{0}, …, a_{n}) ∈ G^{n+1} ist ein Weg in 𝔊 gdw. für i ∈ {1, …, n} gilt: (a_{i−1}, a_{i}) ∈ E^{𝔊}. (a_{0}, …, a_{n}) ist dann ein Weg der Länge n von a_{0} nach a_{n} in 𝔊. Geben Sie für n ≥ 1 einen {E}-Ausdruck φ_{n}(x, y) an, so daß für alle a, b ∈ G gilt:

𝔊 ⊧ φ_{n}[a, b] ⟺ es gibt einen Weg der Länge n von a nach b

in 𝔊, aber keinen der Länge n − 1.

(b). 𝔊 heißt zusammenhängend, wenn es für alle a, b ∈ G einen Weg von a nach b in 𝔊 gibt. Zeigen Sie, daß die Klasse der zusammenhängenden Graphen nicht in der ersten Stufe axiomatisierbar ist.

Aufgabe 4. Sei 𝔊 = (G, E^{𝔊}) ein Graph. 𝔊 heißt azyklisch genau dann, wenn er keine Zykel hat. Zykel in 𝔊 sind Wege (a_{0}, …, a_{n}) in 𝔊 (siehe Aufgabe 3) mit n ≥ 2 und paarweise verschiedenen a_{i}, so daß (a_{n}, a_{0}) ∈ E^{𝔊}. Zeigen Sie, daß die Klasse der azyklischen Graphen in der ersten Stufe axiomatisierbar, aber nicht endlich axiomatisierbar ist.

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

Abgabe: Mittwoch, 1. 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