Übungen zur Vorlesung Mathematische Logik SS 2008, Blatt 9

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

(b) Sei 𝔊 = (G, E^{𝔊}) ein Graph. 𝔊 heißt zusammenhängend, wenn es für alle a, b ∈ G einen Weg von a nach b in 𝔊 gibt (siehe Aufgabe 34). Zeigen Sie, daß die Klasse der zusammenhängenden Graphen nicht in der ersten Stufe axiomatisierbar ist.

Aufgabe 43. Sei S endlich oder S = S_{∞}. Zeigen Sie:

1. Die Menge {Γ φ | Γ φ Sequenz und ⊢ Γ φ} ist aufzählbar.

2. Falls Φ aufzählbar ist, so auch die Menge {ψ | Φ ⊢ ψ}.

Aufgabe 44. Sei 𝔄 eine endliche S-Struktur. Zeigen Sie:

1. Ist 𝔄 eine Struktur mit genau n Elementen, so ist 𝔄 isomorph zu einer Struktur mit Träger {1, …, n}.

2. Ist S endlich, so gibt es einen Satz φ_{𝔄}, der 𝔄 charakterisiert, d.h.

Mod(φ_{𝔄}) = {𝔅 | 𝔅 ≅ 𝔄} .

3. Ist S beliebig, so gibt es eine Satzmenge Φ_{𝔄}, die 𝔄 charakterisiert, d.h.

Mod(Φ_{𝔄}) = {𝔅 | 𝔅 ≅ 𝔄} .

Aufgabe 45. Eine Satzmenge Φ ist unabhängig gdw.

für kein φ ∈ Φ gilt Φ \ {φ} ⊧ φ.

In Aufgabe 23 wurde gezeigt, daß die Theorie der Äquivalenzrelationen Φ_{Äq} unabhängig ist. Zeigen Sie:

1. Zu jedem endlichen Φ gibt es ein unabhängiges Φ_{0} ⊆ Φ mit Mod(Φ_{0}) = Mod(Φ).

2. Gilt Teil 1 auch für unendliches Φ?

Aufgabe 46. Sei 𝔊 = (G, E^{𝔊}) ein Graph. 𝔊 heißt azyklisch, wenn er keine Zykel hat; Zykel in 𝔊 sind Wege (a_{0}, …, a_{m}) in 𝔊 (siehe Aufgabe 34) mit m ≥ 2, für die gilt: a_{i} ≠ a_{i+2} für i = 0, …, m − 2 und (a_{0}, a_{m}) ∈ E^{𝔊}. Zeigen Sie, daß die Klasse der azyklischen Graphen in der ersten Stufe axiomatisierbar, aber nicht endlich axiomatisierbar ist.

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