Übungen zur Vorlesung Mathematische Logik SS 2008, Blatt 6

Aufgabe 27. Sei S = {+, ·, 0, 1, ≤, f, d}, wobei die Funktionssymbole f und d einund 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. f^{ℜ} ist differenzierbar.

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

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

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

a) Die Graphen G_{1} und G_{2} sind isomorph. Geben Sie einen Isomorphismus an.

b) Prüfen Sie, ob G_{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 29. (a) Welche der folgenden Sequenzen sind korrekt?

1. φ ψ (φ ∨ ∃xψ)

2. ∃xφ ∀xφ (b) Welche der folgenden Regeln sind korrekt?

1. \begin{matrix}Γ & φ_{1} & ψ_{1} \\ Γ & φ_{2} & ψ_{2} \\ Γ & (φ_{1} ∨ φ_{2}) & (ψ_{1} ∨ ψ_{2}) \end{matrix}
2. \begin{matrix}Γ & φ \\ Γ & ∀xφ \end{matrix}

Aufgabe 30. Berechnen Sie [[∃v_{3}f(v_{3}, v_{3}) ≡ v_{1}]\frac{v_{3}}{v_{1}} ] \frac{f(v_{1},v_{2})}{v_{3}}.

Aufgabe 31. (Diese Aufgabe wird auf dem nächsten Übungsblatt fortgesetzt.) Im Folgenden bezeichne P(X) die Potenzmenge von X. Die Mengen V_{n} und \overline{n} für n ∈ ℕ seinen 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. Sei A = \{\overline{n} | n ∈ ℕ\}, 0^{A} = \overline{0} und σ^{A} : A → A sei definiert durch σ^{A}(\overline{n}) = \overline{n + 1}. Zeigen Sie, daß die Struktur (A, σ^{A}, 0^{A}) die Peanoaxiome (P1) bis (P3) erfüllt.

Abgabe: Mittwoch, 11. Juni 2008, vor der Vorlesung.