MATHEMATISCHES INSTITUT Bonn, den 25.04.2002 DER UNIVERSITÄT BONN Prof. Dr. Peter Koepke

Einführung in die Mathematische Logik SS 2002

Übungsaufgaben, Folge 2, Abgabe: 02.05.2002 vor der Vorlesung

Aufgabe 1 Zeigen Sie, dass die in der Vorlesung eingeführten Regeln des Sequenzenkalküls korrekt sind.

Aufgabe 2 Zeigen Sie, dass die folgenden Regeln ableitbar sind:

\frac{Φ A}{Φ ¬¬A};  \frac{Φ ¬¬A}{Φ A};  \frac{{Φ A \atop Φ B}}{Φ (A ∧ B)};  \frac{Φ A B}{Φ (A → B)}; \frac{Φ (A ∧ B)}{Φ A}.

Hierbei steht (A ∧ B) als Abkürzung für ¬(¬A ∨ ¬B) und (A → B) als Akürzung für (¬A ∨ B).

Aufgabe 3 (a) Geben Sie einen Kalkül an, der genau die aussagenlogischen Ausdrücke erzeugt.

(b) Geben Sie einen Kalkül an, der genau die arithmetischen Ausdrücke erzeugt, d.h., alle arithemtisch korrekt gebildeten Terme, in denen neben Variablen (x_{0}, x_{1}, …) und den Konstanten 0 und 1 nur die Addition (+) und die Multiplikation ( ·) vorkommen.

Aufgabe 4 Die Mengen M, M_{0}, M_{1}, M_{2}, … seien jeweils höchstens abzählbar und nicht leer.

(a) Beweisen Sie, dass die Menge ⋃_{n∈ℕ} M_{n} höchstens abzählbar ist.

(b) Zeigen Sie, dass auch die Menge {(a_{0}, …, a_{n−1}) | n ∈ ℕ und a_{i} ∈ M für i < n} der endlichen Folgen mit Werten in M abzählbar ist.

(c) Ist auch die Menge {(a_{i})_{i∈ℕ} | a_{i} ∈ M für alle i ∈ ℕ} abzählbar?

Tipp: Betrachten Sie den Fall M = {0, 1}.

Homepage der Vorlesung:

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