MATHEMATISCHES INSTITUT DER UNIVERSITÄT BONN Prof. Dr. Philip Welch

Bonn, den 26.06.2002

Berechenbarkeitstheorie Aufgabenblatt 9

Das Mathematische Institut sucht DRINGEND studentische Hilfskräfte für die 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.

Aufgabe 1 (a) Beweisen Sie, daß B ∈ Σ_{n} aus B ≤_{m} A ∧ A ∈ Σ_{n} folgt.

(b) A und B seien definiert durch ⟨x, y⟩ ∈ A ⇔ ∀z < y R(x, y, z),

⟨x, y⟩ ∈ B ⇔ ∃z < y R(x, y, z).

Zeigen Sie, daß A, B ∈ Σ_{n} aus R ∈ Σ_{n}, und A, B ∈ Π_{n} aus R ∈ Π_{n} folgt.

Aufgabe 2 Die Mengen Fin, Cof und Rec seien definiert durch

Fin = {e | W_{e} ist endlich},

Cof = \{e | \overline{W}_{e} ist endlich\},

Rec = {e | W_{e} ist rekursiv}.

Zeigen Sie, daß Fin ∈ Σ_{2}, Cof ∈ Σ_{3} und Rec ∈ Σ_{3} gilt.

Aufgabe 3 Es gelte n ≥ 1. Beweisen Sie, daß B ≤_{1} A aus B ≤_{m} A mit A = ∅^{(n)} folgt.

Bemerkung: Es ist auch möglich folgendes zu zeigen: Es gelte n ≥ 1, B ≤_{1} A aus B ≤_{m} A mit B = ∅^{(n)} folgt. Mit Aufgabe 3 folgt daraus, daß man die Σ_{n}-Vollständigkeit von A statt mit B ≤_{1} A auch durch „A ∈ Σ_{n} und für alle B ∈ Σ_{n} gilt B ≤_{m} M“ zeigen kann.

Aufgabe 4 Beweisen Sie das

Tot =_{def} {e | W_{e} = ℕ},

Π_{2}-Vollständig ist ist.

Homepage der Vorlesung:

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