MATHEMATISCHES INSTITUT DER UNIVERSITÄT BONN Arbeitsgruppe Mathematische Logik Prof. Dr. Peter Koepke

Bonn, den 06.06.2002

Einführung in die Mathematische Logik SS 2002

Übungsaufgaben, Folge 8, Abgabe: 20.06 nach der Vorlesung

Aufgabe 1 Für jede natürliche Zahl n sei f_{n}: ℝ → ℝ und es sei f: ℝ → ℝ. Ferner seien r, s ∈ ℝ. Wählen Sie in jeder der Teilaufgaben (a)-(f) eine geeignete Symbolmenge S, eine geeignete S-Interpretation ℑ = (𝔄, β) und einen S-Ausdruck φ, so daß ℑ ⊧ φ gleichwertig ist mit der jeweils angegebenen Aussage.

(a) lim_{x→r} f(x) = s.

(b) f ist stetig an der Stelle r.

(c) f ist stetig.

(d) f ist gleichmäßig stetig.

(e) Die Folge (f_{n})_{n∈ℕ} konvergiert punktweise gegen f.

(f) Die Folge (f_{n})_{n∈ℕ} konvergiert gleichmäßig gegen f.

Aufgabe 2 Es sei ℑ_{0} = (𝔄_{0}, β_{0}) eine S_{0}-Interpretation und ℑ_{1} = (𝔄_{1}, β_{1}) eine S_{1}-Interpretation, beide über demselben Träger A. Ferner sei S :≡ S_{0} ∩ S_{1}. Zeigen Sie:

(a) Es sei t ein S-Term. Wenn für alle x ∈ var(t) und für alle ℓ ∈ S, die in t vorkommen, β_{0}(x) = β_{1}(x) sowie ℓ^{𝔄_{0}} = ℓ^{𝔄_{1}} gilt, dann gilt ℑ_{0}(t) = ℑ_{1}(t).

(b) Es sei φ ein S-Ausdruck. Wenn für alle x ∈ frei(φ) und für alle ℓ ∈ S, die in φ vorkommen, β_{0}(x) = β_{1}(x) sowie ℓ^{𝔄_{0}} = ℓ^{𝔄_{1}} gilt, dann gilt ℑ_{0} ⊧ φ genau dann, wenn ℑ_{1} ⊧ φ gilt.

(c) Gelten die Aussagen (a) und (b) auch dann noch, wenn 𝔄_{0} und 𝔄_{1} unterschiedliche Träger haben? Begründen Sie Ihre Antwort.

Aufgabe 3 (a) Beweisen Sie das Substitutionslemma aus der Vorlesung. Untersuchen Sie dabei auch

noch einmal detailliert den in der Vorlesung bereits behandelten Quantorenfall.

(b) Die Symbolmenge S besitze ein einstelliges Funktionssymbol g, ein zweistelliges Funktionssymbol f, ein zweistelliges Relationssymbol R, ein dreistelliges Relationssymbol P und ein Konstantensymbol c. Es sei φ der S-Ausdruck

(∃v_{0} Rv_{0}fv_{1}v_{2} ∧ ∀v_{2} P v_{0}v_{1}v_{2}). Bestimmen Sie die folgenden S-Ausdrücke.

(α) φ \frac{c v_{0} gv_{0}}{v_{0} v_{1} v_{2}}

(β) φ \frac{fv_{1}v_{2} fv_{1}v_{2} c}{v_{0} v_{1} v_{2}}

(γ) φ \frac{v_{2} gv_{0} fv_{0}v_{2} c}{v_{0} v_{1} v_{2} v_{3}}

(c) Beweisen oder widerlegen Sie: Ist S eine Symbolmenge, φ ein S-Ausdruck und sind t_{0} und t_{1} S-Terme und x_{0} sowie x_{1} verschiedene Variablen, so sind [φ \frac{t_{0}}{x_{0}} ] \frac{t_{1}}{x_{1}} und φ \frac{t_{0} t_{1}}{x_{0} x_{1}} logisch äquivalent.

Aufgabe 4 Formalisieren die folgenden Aussagen in einer geeigneten Sprache S, und verwenden Sie das in der Vorlesung eingeführte formale Beweiskalkül, um einen Zusammenhang zwischen „matupeln“ und „Eine Mause haben“ abzuleiten.

1. Wer bedrüpt ist, makst nicht.

2. Wer knaselt, hat eine Mause.

3. Jeder, der nicht deuken kann, makst.

4. Alle Drumser nehmen Pfuff.

5. Wer kein Pli ist, matupelt nicht.

6. Kein betuxter Klep kann deuken.

7. Wer Pfuff nimmt, ist bedrüpt.

8. Nur betuxte Kleps knaseln nicht.

9. Jeder Pli ist ein Drumser.

Homepage der Vorlesung:

http://www.math.uni-bonn.de/people/logic/Lectures/SoSe2002/Vorlesung.html
Newsgroup: uni-bonn.math.logik