[figure]

Mathematisches Institut der Universität Bonn Abt. für Grundlagenforschung der Mathematik

Prof. Dr. Peter Koepke

Einführung in die Mathematische Logik WS 2000/2001

Übungsaufgaben, Folge 5, Abgabe: 23.11.2000 in der Vorlesung

Aufgabe 1 Es gelte G: V → V und F sei der durch <-Rekursion auf On und die Rekursionsvorschrift G bestimmte kanonische Term. Beweisen Sie detailliert die Eindeutigkeitsaussage des Rekursionssatzes: Wenn F′ ein Klassenterm ist, so dass F′: On → V gilt und F′ die Rekursionsvorschrift erfüllt (∀α ∈ On F′(α) = G(F′ ↾ α)), so gilt F′ = F.

Aufgabe 2 (a) Zeigen Sie durch transfinite Induktion (Ordinalzahlinduktion): Addition und Multiplikation von Ordinalzahlen sind assoziativ. Außerdem gelten folgende Monotonieregeln: Falls β < γ, so β + α ≤ γ + α sowie α + β < α + γ und β · α ≤ γ · α sowie (falls α ≠ 0) α · β < α · γ.

(b) Rechtfertigen Sie anhand des Rekursionssatzes aus der Vorlesung, dass es eine Funktion f: ω → ω gibt mit f(n) = n!. Geben Sie hierzu einen Klassenterm G (in der Form G = {u | φ}) an mit G: V → V, so dass f die Einschränkung des durch <-Rekursion auf On und die Rekursionsvorschrift G bestimmten kanonischen Terms F auf ω ist. Wählen Sie G so, dass F die Fakultätsfunktion mit der üblichen Definition (F (α+1) = F (α)·(α+1)) auf ganz On fortsetzt, wobei an Limesstellen δ gelten soll F (δ) = sup_{α<δ} F (α).

Aufgabe 3 (a) Zeigen Sie 2^{ω} = ω.

(b) Das Resultat aus (a) kann so gedeutet werden: ω ist ein Fixpunkt der Funktion α ↦ 2^{α}. Zeigen Sie, dass jede monotone und stetige Funktion F: On → On beliebig große Fixpunkte hat, genauer: Sei F: On → On ordnungstreu und es gelte F (δ) = sup_{α<δ} F (α) für jede Limesordinalzahl δ. Dann existiert zu jedem γ ∈ On eine Limesordinalzahl δ > γ mit F (δ) = δ. Was bedeutet dieses Resultat für die Funktionen α ↦ ξ + α, α ↦ ξ · α, α ↦ ξ^{α}? Tipp: Wenn Sie keine Idee haben, wie der Fixpunkt gefunden werden kann, schauen Sie in den Beweis des aus dem Grundstudium bekannten Banachschen Fixpunktsatz.

Aufgabe 4 Zeigen Sie: Jede Ordinalzahl ist eindeutig darstellbar als δ+n, wobei δ eine Limesordinalzahl oder δ = 0 und n ∈ ω ist.