Übungen zur Vorlesung Mathematische Logik

SS 2009, Blatt 10

Aufgabe 1. Sei S := {P, R, f, g}, wobei P und f zweistellig, R und g einstellig sind. Geben Sie einen termreduzierten S-Ausdruck an, der logisch äquivalent ist zu

∀x ((P g(x)f(x, y) ∧ Rf(x, g(y))) ∨ g(g(z)) ≡ f(g(y), g(z))) .

Aufgabe 2.

(a). Geben Sie eine syntaktische Interpretation I von S_{Grp} in S_{G} an, so daß für alle Gruppen 𝔄 = (A, ∘) gilt: 𝔄^{−I} = (A, ∘,^{−1} , e) ist eine Gruppe.

(b). Geben Sie eine syntaktische Interpretation I von S_{Ar} in S_{Ar} an, so daß

(ℕ, +, ·, 0, 1) = (ℤ, +, ·, 0, 1)^{−I}.

(Hinweis: Jede natürliche Zahl ist Summe von vier Quadratzahlen.)

Aufgabe 3.

(a). Sei S_{1} = {+, ·, 0} und R_{1} = (ℝ, +, ·, 0). Zeigen Sie, daß die Kleinergleich-Beziehung ≤ in R_{1} elementar definierbar ist, d.h. daß ein S_{1}-Ausdruck φ existiert, so daß für alle a, b ∈ ℝ gilt: R_{1} ⊧ φ[a, b] genau dann, wenn a ≤ b.

(b). Sei S_{2} = {+, 0} und R_{2} = (ℝ, +, 0). Zeigen Sie, daß die Kleinergleich-Beziehung ≤ nicht in R_{2} elementar definierbar ist. (Hinweis: Arbeiten Sie mit einem geeigneten Automorphismus von R_{2}.)

Aufgabe 4. Sei S eine Symbolmenge, P ∉ S ein einstelliges Relationssymbol und S^{∗} = S ∪ {P }. Zeigen Sie, daß es zu jedem φ ∈ L_{0}^{S} ein φ^{P} ∈ L_{0}^{S^{∗}} gibt, so daß für alle S-Strukturen 𝔄 und alle S-abgeschlossenen B ⊆ A gilt:

[B]^{𝔄} ⊧ φ ⟺ (𝔄, B) ⊧ φ^{P} .

Hierbei ist (𝔄, B) diejenige S^{∗}-Expansion von 𝔄, für die das Symbol P durch B interpretiert wird.

Aufgabe 5. Seien Ψ ⊆ L_{0}^{S_{1}} und Φ ⊆ L_{0}^{S}. Eine syntaktische Interpretation I von S_{1} in S ist eine Interpretation von Ψ in Φ genau dann, wenn es zu jedem 𝔄 ⊧ Ψ ein 𝔅 ⊧ Φ ∪ Φ_{I} gibt mit 𝔄 ≅ 𝔅^{−I}.

(a). Zeigen Sie, daß dann für alle φ ∈ L_{0}^{S_{1}} gilt:

Ψ ⊧ φ ⟺ Φ ∪ Φ_{I} ∪ {χ^{I} | χ ∈ Ψ} ⊧ φ^{I}.

(b). Sei S_{1} = {R} mit dreistelligem R, S = {E} mit zweistelligem E, Ψ = ∅ und Φ = Φ_{Graph}. Geben Sie eine Interpretation von Ψ in Φ an.

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