Übungen zur Vorlesung Mathematische Logik

SS 2009, Blatt 6

Aufgabe 1. Sei S := {E} mit zweistelligem E; 𝔊_{1} und 𝔊_{2} seien die Graphen:

\begin{aligned}& & & & 𝔊_{1} \\ e & & & & & & & f \\ & • & & & & & • \\ & & & a & b \\ & & • & & & • \\ & & & c & d \\ & & • & & & • \\ & • & & & & & • \\ g & & & & & & & h \end{aligned}  \begin{aligned}& & 𝔊_{2} \\ & A & & B \\ & • & & • \\ C & D & & E & F \\ • & • & & • & • \\ & • & & • \\ & G & & H \end{aligned}

1. Die Graphen 𝔊_{1} und 𝔊_{2} sind isomorph. Geben Sie einen Isomorphismus an.

2. Prüfen Sie, ob 𝔊_{i} ⊧ φ_{j} für i ∈ {1, 2} und j ∈ {1, 2, 3}, wobei

φ_{1} := ∃x∃y∃z(Exy ∧ Eyz ∧ Ezx)
φ_{2} := ∀x∀y(¬Exy → ∃z(Exz ∧ Ezy))
φ_{3} := ∀x∃y_{1}∃y_{2}∃y_{3}∃y_{4}(Exy_{1} ∧ Exy_{2} ∧ Exy_{3} ∧ Exy_{4}).

Aufgabe 2. Sei S eine Symbolmenge, 𝔅 eine S-Struktur mit Träger B, und M ⊆ B. Gelte weiterhin

M ≠ ∅ oder S enthält ein Konstantensymbol.

Zeigen Sie, daß die Menge

X := {t^{𝔅}[a_{1}, …, a_{n}] | n ≥ 0, a_{1}, …, a_{n} ∈ M, t ∈ T_{n}^{S}}

Träger einer Substruktur von 𝔅 ist, d.h. daß es eine Struktur 𝔄 mit 𝔄 ⊆ 𝔅 und A = X gibt.

Aufgabe 3. Sei S := {+, ·, 0, 1, ≤, f, d}, wobei die Funktionssymbole f und d ein- und zweistellig sind. Sei ℜ eine S-Struktur mit Träger ℝ, in der +, ·, 0, 1 und ≤ wie üblich interpretiert sind, f^{ℜ} : ℝ → ℝ eine Funktion und d^{ℜ} die Abstandsfunktion ist, d.h. d^{ℜ}(r, r′) = |r − r′| für alle r, r′ ∈ ℝ. Symbolisieren Sie:

1. f^{ℜ} ist gleichmässig stetig.

2. Wenn f^{ℜ} streng monoton ist, dann ist f^{ℜ} injektiv.

3. f^{ℜ} ist differenzierbar.

Aufgabe 4. Für eine Menge M seien

P_{e}(M) := {Y ⊆ M | Y ist endlich }
P_{e,ce}(M) := {Y ⊆ M | Y ist endlich oder M∖Y ist endlich}

1. Ist P_{e}(M) Träger einer Substruktur der Booleschen Algebra P (M) und damit selbst eine Boolesche Algebra?

2. Is P_{e,ce}(M) Träger einer Substruktur der Booleschen Algebra P (M) und damit selbst eine Boolesche Algebra?

Aufgabe 5. Für n ∈ ℕ seien die Mengen V_{n} und \overline{n} induktiv wie folgt definiert:

V_{0} := ∅, \overline{0} := ∅,
V_{n+1} := P (V_{n}), \overline{n + 1} := \overline{n} ∪ \{\overline{n}\}.

Weiter sei V_{ℕ} := ⋃_{n∈ℕ} V_{n}. Zeigen Sie:

1. V_{n} ist endlich.

2. V_{n} ⊆ V_{m} für n < m.

3. Aus x ∈ V_{n} folgt x ⊆ V_{n}.

4. Aus x ∈ V_{ℕ} folgt x ⊆ V_{ℕ}.

5. \overline{n} ∈ V_{n+1}∖V_{n}.

6. V_{ℕ} ist abzählbar.

Geben Sie \overline{0}, \overline{1}, \overline{2} und \overline{3} explizit an.

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