Übungen zur Vorlesung Mathematische Logik SS 2008, Blatt 8

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

∃y ((¬P g(x, f(y)) ∨ Rg(x, y)f(g(x, y))) ∧ f(y) ≡ g(y, y)) .

Aufgabe 38. Geben Sie eine syntaktische Interpretation I von S_{Ar} in S_{Ar} an, sodaß

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

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

Aufgabe 39. (a) Sei S_{1} = {+, ·, 0} und R_{1} = (ℝ, +, ·, 0). Zeigen Sie, daß die Kleiner-Beziehung < in R_{1} elementar definierbar ist, d.h. daß ein S_{1}-Ausdruck φ existiert, sodaß für alle a, b ∈ ℝ gilt: R_{1} ⊧ φ[a, b] gdw. a < b.

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

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

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

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

2. Es sei S_{1} = {R} mit dreistelligem R, S = {E} mit zweistelligem E, Φ_{1} = ∅ und Φ = Φ_{Graph}. Geben Sie eine Interpretation von Φ_{1} in Φ an.

Aufgabe 41. Sei S = {+, −, ·, 0, 1}.

(a) Ein Körper K heißt algebraisch abgeschlossen, falls jedes nicht-konstante Polynom mit Koeffizienten in K eine Nullstelle in K besitzt. Geben Sie eine Menge Φ von S-Sätzen an, sodaß für jeden Körper K (aufgefaßt als S-Struktur) gilt:

K ist algebraisch abgeschlossen gdw. K ⊧ Φ.

(b) Der Fundamentalsatz der Algebra besagt, daß der Körper ℂ der komplexen Zahlen algebraisch abgeschlossen ist. Folgern Sie, daß für jede S-Struktur R mit R ≡ (ℝ, +, −, ·, 0, 1) jede Körpererweiterung K von R vom Grad 2 algebraisch abgeschlossen ist.

(Hinweise: 1. Für eine Symbolmenge S heißen zwei S-Strukturen A und B elementar äquivalent, in Zeichen A ≡ B, falls für alle S-Sätze φ ∈ L_{0}^{S} gilt: A ⊧ φ gdw. B ⊧ φ.

2. Verwenden Sie, daß für alle R ≡ (ℝ, +, −, ·, 0, 1) je zwei Körpererweiterungen von R vom Grad 2 isomorph sind als S-Strukturen.)

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