MATHEMATISCHES INSTITUT DER UNIVERSITÄT BONN Prof. Dr. Philip Welch Bonn, den 24.05.2002

Berechenbarkeitstheorie Aufgabenblatt 6

Aufgabe 1 Sei f ∈ Crm eine totale Funktion. Die Menge B sei definiert durch

B := {f(n) | n ∈ ℕ} = ran f = {f(0), f(1), ⋯}.

(a) Angenommen, f sei strikt monoton (d.h. f(n) < f(n + 1) für alle n ∈ ℕ). Beweisen Sie, daß dann B ∈ Crm gilt. (Zu zeigen ist χ_{B} ∈ Crm.)

(b) Was passiert ohne die Voraussetzung „f ist strikt monoton“?

Aufgabe 2 Seien g, h ∈ Crm partielle Funktionen.

(a) Zeigen Sie, daß eine partielle Funktion f ∈ Crm existiert, so daß gilt (i) f(γ) ↓ ⇔ g(γ) ↓ ∨ h(γ) ↓ . (ii) f(γ) ↓ ⇒ f(γ) = g(γ) ∨ f(γ) = h(γ).

(b) Kann auch gefordert werden, daß

g(γ) ↓ ⇒ f(γ) = g(γ) gelten soll?

Aufgabe 3 Beweisen Sie, daß rekursive Funktionen f und g existieren, so daß für alle x gilt:

ran φ_{f(x)} = dom φ_{x},

dom φ_{g(x)} = ran φ_{x}.

Aufgabe 4 Beweisen Sie die Existenz zweier nichtrekursiven Mengen A und B, die unter ≤_{m} nicht vergleichbar sind.

Homepage der Vorlesung:

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