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

Bonn, den 03.07.2002

Berechenbarkeitstheorie Aufgabenblatt 10

Aufgabe 1 Sei T ⊆ 2^{<ℕ} ein unendlicher rekursiver Baum.

(a) Beweisen Sie: Wenn [T] = {f} gilt, so ist f rekursiv.

(b) Beweisen Sie, daß [T] ein Element g besitzt, so daß g ≡_{T} A gilt, wobei A eine rekursiv abzälhbare Menge ist.

Aufgabe 2 Es sei T eine nichtleere Teilmenge von X^{<ℕ} (X = 2 oder X = ℕ).

Zeigen Sie: Wenn T ein perfekt Baum ist, so hat [T] 2^{ℕ}-viele Elemente. Hinweis: Zeigen Sie, daß eine Injektion F : 2^{ℕ} → [T] existiert. Definieren Sie dafür zuerst eine Injektion F_{0} : 2^{<ℕ} → T, so daß F_{0}(σ)|F_{0}(τ) aus σ|τ folgt für alle σ, τ ∈ 2^{<ℕ}.

Aufgabe 3 Vollenden Sie den Beweis aus der Vorlesung, daß es 2^{ℕ}-viele (d.h. Kontinuum-viele) \underline{a}, \underline{b} mit \underline{a}|_{T} \underline{b} gibt. Hinweis: In der Beweisskizze war noch zu zeigen, daß [T] 2^{ℕ}-viele unvergleichbare f ∈ 2^{ℕ} enthält.

(a) Zeigen Sie, daß T \underline{perfekt} ist.

(b) Zeigen Sie: Für f, g ∈ [T] folgt [f]_{T} |_{T} [g]_{T} aus f ≠ g.

Aufgabe^{∗} 4 Sei \{\underline{b}_{n}\} eine abzählbare Menge von nicht-rekursiven Graden. Beweisen Sie, daß eine abzählbare Menge von Graden \{\underline{a}_{n}\} existiert, so daß gilt:

(i) ∀m, n (n ≠ m ⇒ \underline{a}_{m}|_{T} \underline{a}_{n}), (ii) ∀m, n (\underline{a}_{m}|_{T} \underline{b}_{n}). Hinweis: Kombinieren Sie die Konstruktionen aus den Beweisen der Sätze 2 und 4 aus §4. Setzen Sie als Voraussetzungen: R_{⟨e,n,m⟩} : χ_{A_{m}} ≠ φ_{e}^{B_{n}}, S_{⟨e,n,m⟩} : χ_{B_{m}} ≠ φ_{e}^{A_{n}}, T_{⟨e,n,m⟩} : χ_{A_{n}} ≠ φ_{e}^{A_{m}}( für n ≠ m).

Homepage der Vorlesung:

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