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

Bonn, den 27.06.2002

Einführung in die Mathematische Logik SS 2002

Übungsaufgaben, Folge 10, Abgabe: 04.07 nach der Vorlesung

Das Mathematische Institut sucht DRINGEND studentische Hilfskräfte für Anfängervorlesungen. Interessierte Studenten mögen sich per e-mail oder Telephon bei Herrn Dr. Torsten Hefer (hefer@math.uni-bonn.de; 0228/73-5278) melden.

Die Klausur wird am 9.Juli um 12.30 im Kleinen Hörsaal stattfinden. Alle Teilnehmer der Vorlesung, die an der Klausur teilnehmen wollen, mögen sich bitte unter Angabe von Name, Matrikelnummer und Wohnort bei den Übungsleitern oder bei Stefan Bold (Fach in der Beringstr. 1) anmelden.

Aufgabe 1 (a) Bilden Sie zwei Formelmengen Φ_{G1}, Φ_{G2}, die beide die Gruppenaxiome formalisieren. Verwenden Sie dabei für Φ_{G1} das Alphabet 𝔸_{1} = {∘, 1} und für Φ_{G2} das Alphabet 𝔸_{2} = {∘,^{−1} , 1}.

(b) Formalisieren und beweisen Sie im Beweiskalkül die folgenden Aussagen. Verwenden Sie dabei das Alphabet 𝔸_{1} und das System Φ_{G1}.

(i) Das Neutrale Element der Gruppe ist eindeutig. (ii) Für jedes Element der Gruppe ist das Inverse eindeutig. (iii) Die Gruppenopperation ist bezüglich des Neutralen Elements kommutativ. (iv) Linksinverses und Rechtsinverses sind identisch, d.h. die Gruppenoperation ist

bezüglich des Inversen Elements kommutativ.

(c) Formalisieren und beweisen Sie im Beweiskalkül die eben aufgeführten Aussagen. Verwenden Sie diesmal das Alphabet 𝔸_{2} und das System Φ_{G2}.

Aufgabe 2 (a) Formalisieren Sie das folgende Torsionsaxiom ϕ_{T or}.

ϕ_{T or} :=„Jedes Gruppenelement ergibt mit sich selbst verknüpft das Neutrale Element.“ Verwenden Sie hierbei entweder das Alphabet 𝔸_{1} oder 𝔸_{2}.

(b) Beweisen Sie im Beweiskalkül, daß eine Gruppe, die dem Torsionsaxiom ϕ_{T or} genügt, kommutativ ist. Verwenden Sie dabei eine der beiden Formalisierungen Φ_{G1}, Φ_{G2} aus Aufgabe 3.

Aufgabe 3 Es sei 𝒮 eine Menge von Symbolmengen, die ⊆-gerichtet ist, d.h., für alle S_{0}, S_{1} ∈ 𝒮 existiert ein S_{2} ∈ 𝒮 mit S_{0} ∪ S_{1} ⊆ S_{2}. Für jedes S ∈ 𝒮 sei Φ_{S} eine Menge von S-Ausdrücken, und es gelte Φ_{S_{0}} ⊆ Φ_{S_{1}} falls S_{0} ⊆ S_{1}. Setze S_{∞} :≡ ⋃_{S∈𝒮} S und Φ_{∞} :≡ ⋃_{S∈𝒮} Φ_{S}.

(a) Zeigen Sie, daß die folgenden beiden Aussagen äquivalent sind.

(i) Für jedes S ∈ 𝒮 gilt Wf_{S} Φ_{S} (d.h. Φ_{S} ist widerspruchsfrei). (ii) Es gilt Wf_{S_{∞}} Φ_{∞} (d.h. Φ_{∞} ist widerspruchsfrei).

(b) Zeigen Sie: Wenn für alle S ∈ 𝒮 Φ_{S} eine Henkin-Mengen ist, so ist auch Φ_{∞} eine Henkin-Menge.

Aufgabe 4 Gegeben seien folgende Formeln:

φ_{(i)} :≡ ∀v_{0}¬ Rv_{0}v_{0}
φ_{(ii)} :≡ ∀v_{0}∀v_{1} (¬ v_{0} = v_{1} → (Rv_{0}v_{1} ∨ Rv_{1}v_{0}))
φ_{(iii)} :≡ ∀v_{0}∀v_{1}∀v_{2} ((Rv_{0}v_{1} ∧ Rv_{1}v_{2}) → Rv_{0}v_{2})
φ_{(iv)} :≡ ∀v_{0}∀v_{1}∃v_{2} (Rv_{0}v_{1} → (Rv_{0}v_{2} ∧ Rv_{2}v_{1}))
φ_{(v)} :≡ ∀v_{0}∃v_{1}∃v_{2} (Rv_{1}v_{0} ∧ Rv_{0}v_{2})
φ_{NT} :≡ ∃v_{0}∃v_{1} Rv_{0}v_{1}
φ_{ME} :≡ ∃v_{0}∀v_{1} (Rv_{1}v_{0} ∨ v_{0} = v_{1})
φ_{LE} :≡ ∃v_{0}∀v_{1} (Rv_{0}v_{1} ∨ v_{0} = v_{1})
φ_{LEP} :≡ ∀v_{0}∃v_{1}∀v_{2} (Rv_{0}v_{2} → (Rv_{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}}. Hinweis: Für den Fall, dass die Mengen konsistent sind, zeigen Sie statt der Konsistenz die Erfüllbarkeit, indem Sie geeignete Modelle angeben. Für den Fall, dass die Mengen inkonsistent sind, zeigen Sie statt der Inkonsistenz die Nicht-Erfüllbarkeit.

Homepage der Vorlesung:

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