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

Bonn, den 19.06.2002

Berechenbarkeitstheorie Aufgabenblatt 8

Aufgabe 1 (a) Beweisen Sie, daß die Menge

{⟨e, σ, x, y, s⟩ | φ_{e,s}^{σ}(x) = y} rekursiv ist.

(b) Beweisen Sie, daß die Menge

L_{1} = {⟨e, σ, x, y⟩ | φ_{e}^{σ}(x) = y} rekursiv abzählbar ist.

Aufgabe 2 Seien A und B beliebige Mengen. Beweisen Sie die Äquivalenz folgender Aussagen:

1. Es gilt B ≤_{T} A.

2. Es existieren rekursive Funktionen f und g, so daß gilt:

x ∈ B ⇔ ∃σ[σ ∈ W_{f(x)} ∧ σ ⊂ A],

x ∉ B ⇔ ∃σ[σ ∈ W_{g(x)} ∧ σ ⊂ A].

\underline{Hinweis}: Benutzen Sie Aufgabe 1 mit φ_{e}^{A} = χ_{B} und y = 1 bzw y = 0, um f und g zu finden. Für die andere Richtung verwenden Sie den Komplementierungs-Satz („Complementation-Theorem“).

Aufgabe 3 Beweisen Sie: [A ⊕ B]_{T} ist die kleinste obere Schranke („least upper bound“) der Grade („degrees“) \underline{a} = [A]_{T} und \underline{b} = [B]_{T}. Zu zeigen ist also: Es sei \underline{a} ∪ \underline{b} = [A ⊕ B]_{T}, dann gilt

1. \underline{a} ≤_{T} (\underline{a} ∪ \underline{b}).

2. \underline{b} ≤_{T} (\underline{a} ∪ \underline{b}).

3. ∀\underline{c}[\underline{a} ≤_{T} \underline{c} ∧ \underline{b} ≤_{T} \underline{c} ⇒ (\underline{a} ∪ \underline{b}) ≤_{T} \underline{c}].

Homepage der Vorlesung:

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