Mathematisches Institut

Mengenlehre & Logik II

Sommersemester 2001 Benedikt Löwe

Blatt 11 Abgabetermin: 12. Juli 2001

Aufgabe 52

Zeigen Sie: Für jede natürliche Zahl n existiert eine berechenbare Bijektion β_{n} : ω^{n} → ω.

Hinweis: Induktion, wobei (15.3) den Induktionsanfang bildet.

Aufgabe 53

Zeigen Sie: Es gibt eine berechenbare Bijektion β : ω^{<ω} → ω. (An dieser Stelle sollten Sie zunächst definieren, was das genau heißt.)

Aufgabe 54

Wir wollen eine Ordinalzahl α berechenbar nennen, wenn es einen Kode w ∈ WO mit |w| = α gibt, der berechenbar ist (als reelle Zahl).

Zeigen Sie:

(1) Es gibt nur abzählbar viele berechenbare Ordinalzahlen.

(2) Die Ordinalzahlen ω · 2, ω^{2} und ω^{ω} sind berechenbar.

(3) Sei ω_{1}^{CK} die kleinste nicht berechenbare Ordinalzahl (diese Zahl wird “omegaeins-Church-Kleene” genannt). Zeigen Sie, daß ω_{1}^{CK} eine Limesordinalzahl ist.