[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 11, Abgabe: 18.01.2001 in der Vorlesung

Aufgabe 1 (Beziehungen zwischen Eigenschaften einer Theorie) Sei L eine beliebige Sprache und Φ eine Formelmenge. Wir wollen Φ L-quasikategorisch nennen, wenn Φ keine endlichen Modelle hat und eine Kardinalzahl κ ≥ \overline{\overline{L}} existiert, so dass Φ κ-kategorisch ist. Füllen Sie die folgende Tabelle aus. Belegen Sie Ihre Antworten durch einen Beweis oder durch ein kurzes Gegenbeispiel.

WAHR FALSCH
(a) Jedes erfüllbare Φ ist L-konsistent.
(b) Jedes L-quasikategorische Φ ist L-vollständig.
(c) Jedes L-konsistente Φ ist L-vollständig.
(d) Jedes L-vollständige Φ ist L-konsistent.
(e) Jedes L-quasikategorische Φ ist L-konsistent.
(f) Jedes L-vollständige Φ ist erfüllbar.
(g) Jedes L-konsistente Φ ist erfüllbar.

Tipp: Die Beweise für die wahren Aussagen bestehen zumeist nur aus einem Zitat eines Ergebnisses in der Vorlesung oder einer einfachen Kombination von solchen Zitaten.

Aufgabe 2 (Unvollständige Theorien) Zeigen Sie, dass die Theorien Φ_{aGr} und Φ_{aoK} unvollständig sind. Tipp: Eine Begründung steht in den Abschnitten 18.5.2 und 18.5.6 des Skripts. Bitte seien Sie bei ihrer Begründung ausführlicher als das Skript.

Aufgabe 3 (Konsistenz) In Analogie zu Abschnitt 15.3.5 setzen wir

φ_{(i)} :≡ ˙∀ v̇_{0} ˙¬ Ṙv̇_{0}v̇_{0}
φ_{(ii)} :≡ ˙∀ v̇_{0} ˙∀ v̇_{1} ˙( ˙¬ v̇_{0} ≐ v̇_{1} ˙→ ˙(Ṙv̇_{0}v̇_{1} ˙∨ Ṙv̇_{1}v̇_{0}˙)˙)
φ_{(iii)} :≡ ˙∀ v̇_{0} ˙∀ v̇_{1} ˙∀ v̇_{2} ˙(˙(Ṙv̇_{0}v̇_{1} ˙∧ Ṙv̇_{1}v̇_{2}˙) ˙→ Ṙv̇_{0}v̇_{2}˙)
φ_{(iv)} :≡ ˙∀ v̇_{0} ˙∀ v̇_{1} ˙∃ v̇_{2} ˙(Ṙv̇_{0}v̇_{1} ˙→ ˙(Ṙv̇_{0}v̇_{2} ˙∧ Ṙv̇_{2}v̇_{1}˙)˙)
φ_{(v)} :≡ ˙∀ v̇_{0} ˙∃ v̇_{1} ˙∃ v̇_{2} ˙(Ṙv̇_{1}v̇_{0} ˙∧ Ṙv̇_{0}v̇_{2}˙)
φ_{NT} :≡ ˙∃ v̇_{0} ˙∃ v̇_{1} Ṙv̇_{0}v̇_{1}
φ_{ME} :≡ ˙∃ v̇_{0} ˙∀ v̇_{1} ˙(Ṙv̇_{1}v̇_{0} ˙∨ v̇_{0} ≐ v̇_{1}˙)
φ_{LE} :≡ ˙∃ v̇_{0} ˙∀ v̇_{1} ˙(Ṙv̇_{0}v̇_{1} ˙∨ v̇_{0} ≐ v̇_{1}˙)
φ_{LEP} :≡ ˙∀ v̇_{0} ˙∃ v̇_{1} ˙∀ v̇_{2} ˙(Ṙv̇_{0}v̇_{2} ˙→ ˙(Ṙv̇_{2}v̇_{1} ˙∨ v̇_{1} ≐ v̇_{2}˙)˙)

Prüfen Sie, ob die folgenden Formelmengen konsistent sind:

(a) {φ_{(i)}, φ_{(iii)}, φ_{ME}, φ_{LE}, φ_{NT}},

(b) {φ_{(i)}, φ_{(iii)}, φ_{(v)}, φ_{ME}},

(c) {φ_{(i)}, φ_{(iii)}, φ_{LEP}, ¬φ_{ME}},

(d) {φ_{(i)}, φ_{(ii)}, φ_{(iii)}, φ_{LEP}, ¬φ_{ME}}. Tipp: Für den Fall, dass die Mengen konsistent sind, verwenden Sie Satz 17.8, und zeigen Sie statt der Konsistenz die Erfüllbarkeit, indem Sie geeignete Modelle angeben. Für den Fall, dass die Mengen inkonsistent sind, verwenden Sie Satz 17.25, und zeigen Sie statt der Inkonsistenz die Nicht-Erfüllbarkeit.

Aufgabe 4 (Ableiten im Sequenzenkalkül) Wir betrachten die Theorie Φ_{aoK} der angeordneten Körper. Schreiben Sie die folgenden Aussagen (i) – (iii) als Formeln der Sprache L_{aoK} und leiten Sie diese Formeln aus Φ_{aoK} im Sequenzenkalkül ab.

(i) ∀x∀y (−x) · (−y) = x · y; (ii) ∀x (x > 0 → −x < 0); (iii) 0 < 1. Tipp: Zeigen Sie die Ableitbarkeit der Formeln in der hier angegebenen Reihenfolge. Um eine Idee für die formalen Beweise zu bekommen, können Sie zunächst den Vollständigkeitssatz heranziehen und zeigen, dass die Formeln aus Φ_{aoK} folgen. Übertragen Sie dann diese Beweise in formale Beweise im Sequenzenkalkül.