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

Bonn, den 04.07.2002

Einführung in die Mathematische Logik SS 2002

Übungsaufgaben, Folge 11, Abgabe: 11.07 nach der Vorlesung

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

Aufgabe 1 A = (A, ∘, 1) und B = (B, +, 0) seien Strukturen, die die Gruppenaxiome erfüllen. Das Produkt dieser Strukturen ist definiert durch

A × B = (A × B, ⊕, e), mit e := \binom{1}{0} und \binom{x_{1}}{x_{2}} ⊕ \binom{y_{1}}{y_{2}} := \binom{x_{1} ∘ y_{1}}{x_{2} + y_{2}}.

(a) Bestimmen Sie Substrukturen von A × B, die isomorph zu A und B sind (und geben Sie die Isomorphismen an).

(b) Beweisen Sie, daß auch A × B die Gruppenaxiome erfüllt.

Aufgabe 2 Verwenden Sie die Formalisierung der Peano-Arithmetik, um im Beweiskalkül die folgende Aussage zu beweisen:

∀x∀y((¬(x = 0) ∧ ¬(y = 0)) → ¬((x + y) = 0)).

Beachten Sie dabei, daß Sie im Beweiskalkül alle Regeln der Aussagenlogik verwenden dürfen, Sie müssen im Beweis natürlich die jeweilige Regel der Aussagenlogik aufführen.

Aufgabe 3 Es sei S eine beliebige Sprache, Φ folgende Formelmenge:

Φ := {v_{0} = t | t ∈ T^{S}} ∪ {∃v_{0}∃v_{1}¬v_{0} = v_{1}}.

(a) Zeigen Sie die Widerspruchsfreiheit von Φ.

(b) Zeigen Sie, daß es in L^{S} keine widerspruchsfreie Obermenge von Φ gibt, die Beispiele enthält.

Aufgabe 4 Es sei S eine Symbolmenge. Mit L_{0}^{S} :≡ {φ ∈ L^{S} | frei(φ) = ∅} bezeichnen wir die Menge der S-Sätze. Eine Menge Φ von S-Sätzen heißt vollständig, falls für jeden S-Satz φ gilt Φ ⊧ φ oder Φ ⊧ ¬φ. Es sei Σ :≡ {Φ ⊆ L_{0}^{S} | Erf Φ und Φ ist vollständig}. Für jeden S-Satz φ setze ⟨φ⟩ :≡ {Φ ∈ Σ | Φ ⊧ φ}. Zeigen Sie:

(a) Die Menge {⟨φ⟩ | φ ∈ L_{0}^{S}} ist Basis einer Topologie 𝒯 auf Σ, d.h., durch 𝒯 :≡ {⋃_{φ∈Ψ}⟨φ⟩ | Ψ ⊆ L_{0}^{S}} ist eine Topologie auf Σ definiert.

(b) Jede Menge ⟨φ⟩ ist abgeschlossen in 𝒯.

(c) Die Topologie 𝒯 ist (quasi-)kompakt in dem Sinn, daß jede Überdeckung von Σ durch Mengen aus 𝒯 eine endliche Teilüberdeckung enthält. Ist 𝒯 auch hausdorffsch? (Hinweis: Benutzen Sie den Kompaktheitssatz.)