[figure]

Mathematisches Institut der Universität Bonn Abt. für Grundlagenforschung der Mathematik

Prof. Dr. Peter Koepke

Einführung in die Mathematische Logik WS 2000/2001 Übungsaufgaben, Folge 10, Abgabe: 11.01.2001 in der Vorlesung

Aufgabe 1 In den Teilaufgaben (a) — (d) sei ⊢^{(a)}, …, ⊢^{(d)} jeweils die ⊆-kleinste Menge U, die außer den Regeln des Sequenzenkalküls folgendes erfüllt:

(a) \frac{(Φ ∪ \{φ_{1}\}, ψ_{1}) ∈ U (Φ ∪ \{φ_{2}\}, ψ_{2}) ∈ U}{(Φ ∪ \{˙(φ_{1} ˙∨ φ_{2}˙)\}, ˙(ψ_{1} ˙∨ ψ_{2}˙)) ∈ U};

(b) \frac{(Φ ∪ \{φ_{1}\}, ψ_{1}) ∈ U (Φ ∪ \{φ_{2}\}, ψ_{2}) ∈ U}{(Φ ∪ \{˙(φ_{1} ˙∨ φ_{2}˙)\}, ˙(ψ_{1} ˙∧ ψ_{2}˙)) ∈ U};

(c) \frac{(Φ ∪ \{φ\}, ψ) ∈ U}{(Φ ∪ \{ ˙∀ x φ\}, ˙∃ x ψ) ∈ U};

(d) \frac{(Φ, φ\frac{ḟy}{x}) ∈ U}{(Φ, ˙∀ xφ) ∈ U} (ḟ einstellig, ḟ, y kommen in Φ ∪ \{ ˙∀ x φ\} nicht vor). Untersuchen Sie, ob ⊢^{(a)}, …, ⊢^{(d)} korrekt sind.

Aufgabe 2 Zeigen Sie, dass folgende Regeln ableitbar sind.

(a) \frac{Φ, φ ⊢ χ Φ, ψ ⊢ χ}{Φ, ˙(φ ˙∨ ψ˙) ⊢ χ};

(b) \frac{Φ ⊢ φ}{Φ ⊢ ˙(φ ˙∨ ψ˙)};

(c) \frac{Φ, φ\frac{y}{x} ⊢ ψ}{Φ, ˙∃ x φ ⊢ ψ} (y ∉ fr(Φ ∪ \{ψ\}) ∪ var(φ));

(d) \frac{Φ ⊢ φ\frac{s}{x}}{Φ ⊢ ˙∃ x φ} (φ, s kollisionsfrei).

Aufgabe 3 Es sei L eine formale Sprache und es sei Ψ ⊆ Fml(L).

(a) Argumentieren Sie: Durch s_{1} ≈ s_{2} :≡ Ψ ⊢ s_{1} ≐ s_{2} ist eine Äquivalenzrelation auf Tm(L) definiert und analog zum in der Vorlesung betrachteten Fall, dass Ψ eine Henkin-Menge ist, kann auf A :≡ Tm(L)/ ≈ eine L-Struktur 𝔄 definiert werden.

(b) Charakterisieren Sie 𝔄 im Fall, dass Ψ L-inkonsistent ist.

(c) Falls Ψ L-konsistent ist, gilt ∀φ ∈ At(L) (𝔄 ⊧ φ[β] ⟷ Ψ ⊢ φ), wobei die Belegung β jeder Variablen ihre ≈-Äquivalenzklasse zuordnet.

(d) Zeigen Sie, dass in (c) die Voraussetzung φ ∈ At(L) nicht weggelassen werden kann. Tipp: Betrachten Sie eine formale Sprache L mit genau einem einstelligen Relationssymbol Ṙ und setzen Sie Ψ :≡ {∃v̇_{0}Ṙv̇_{0}} ∪ { ˙¬ Ṙv̇_{n} | n < ω}.

Aufgabe 4 Es sei L eine formale Sprache und ⊢′_{L} sei die ⊆-kleinste Teilmenge U von 𝒫(Fml(L))×Fml(L), die die Regeln des Sequenzenkalküls und

\overline{(Φ ∪ \{ ˙∃ x φ\}, ˙∀ x φ) ∈ U}

erfüllt. Zeigen Sie, dass ⊢′_{L} eine echte, nicht triviale Erweiterung von ⊢_{L} ist: ⊢_{L}⫋⊢′_{L}⫋ 𝒫(Fml(L)) × Fml(L). Tipp: Zum Nachweis der Nichttrivialität zeige man z.B. ˙∃ v̇_{0} v̇_{0} ≐ v̇_{0} ⊬′ ˙∃ v̇_{0} ˙∃ v̇_{1} ˙¬ v̇_{0} ≐ v̇_{1}.

Im Folgenden ausser Konkurrenz noch eine Aufgabe mit höherem Schwierigkeitsgrad. Bei ihrer Lösung erzielte Punkte werden Ihrem Punktekonto gutgeschrieben.

Aufgabe 5 Es sei L = L_{Arith} die Sprache der Arithmetik, siehe 15.3.6, und Φ_{Körper} sei die Theorie der Körper, siehe 15.3.7. Formalisieren Sie die Eigenschaft der Nullteilerfreiheit in einer L_{Arith}- Formel φ und geben Sie einen formalen Beweis für Φ_{Körper} ⊢_{L} φ an.