[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 4, Abgabe: 16.11.2000 in der Vorlesung

Definition. Es seien A und R Klassenterme mit R ⊆ A×A. R heißt (starke) Wohlordung auf A, falls folgende drei Eigenschaften gelten:

(i) ∀x, y, z ∈ A (¬xRx ∧ ((xRy ∧ yRz) → xRz) ∧ (x ≠ y → (xRy ∨ yRx)); (ii) ∀b ⊆ A (b ≠ ∅ → ∃x ∈ b∀y ∈ b (y = x ∨ xRy)); (iii) ∀x ∈ A {y | yRx} ∈ V.

Aufgabe 1 Es sei R eine Wohlordnung auf A und S eine Wohlordnung auf B.

(a) Beweisen Sie folgendes Fundierungsschema: Falls φ(x, z⃗) eine ∈-Formel ist, so gilt ∀z⃗ (∃x ∈ A φ(x, z⃗) ⟶ ∃x ∈ A (φ(x, z⃗) ∧ ∀y (yRx ⟶ ¬φ(y, z⃗)))). Wie kann man dieses Fundierungsschema umgangssprachlich ausdrücken?

(b) Es sei F: A → A ordnungstreu. Dann gilt xRF (x) oder x = F (x) für alle x ∈ A. Insbesondere ist ran(F) kein Anfangsstück von A, d.h., es gibt kein u ∈ A mit ran(F) = {x | xRu}.

(c) Es gibt höchstens eine bijektive und ordnungstreue Abbildung (Isomorphismus) von (A, R) auf (B, S).

(d) Es gilt genau eine der folgenden drei Aussagen:

(i) (A, R) und (B, S) sind isomorph, d.h., es gibt einen Isomorphismus von (A, R) auf (B, S).

(ii) (A, R) ist isomorph zu einem Anfangsstück von (B, S). (iii) (B, S) ist isomorph zu einem Anfangsstück von (A, R). Tipp: Betrachten Sie F :≡ {(x, y) ∈ A × B | {u | uRx} ist isomorph zu {u | uSy}}.

Aufgabe 2 (a) Zeigen Sie, dass durch

(α_{1}, β_{1}) <_{On × On} (α_{2}, β_{2}) :≡ ( max{α_{1}, β_{1}} < max{α_{2}, β_{2}} ∨
(max{α_{1}, β_{1}} = max{α_{2}, β_{2}} ∧ α_{1} < α_{2}) ∨
(max{α_{1}, β_{1}} = max{α_{2}, β_{2}} ∧ α_{1} = α_{2} ∧ β_{1} < β_{2}))

eine Wohlordnung auf On × On definiert ist.

Zeigen Sie ferner, dass durch (m, n) ↦ (max{m, n})^{2} + r(m, n) mit

r(m, n) = \{ \begin{matrix}m, & falls m < n \\ m + n, & falls n ≤ m \end{matrix}

eine ordnungstreue Bijektion von (ω × ω, <_{On × On} ∩ ω × ω) auf (ω, ∈) definiert ist.

(b) Geben Sie eine Wohlordnung <′ von ω × ω an, so dass es ein Polynom p mit rationalen Koeffizienten gibt, das eine ordnungstreue Bijektion zwischen (ω ×ω, <′) und (ω, ∈) ist. Tipp: Betrachten Sie die Diagonalen D_{i} = {(m, n) | m + n = i}.

Benutzen Sie hierbei Addition, Subtraktion, Multiplikation und Division natürlicher Zahlen auf naive Weise. Diese Operationen werden im weiteren Verlauf der Vorlesung noch formal definiert.

Aufgabe 3 (a) Es sei Nat(x) :≡ (Succ(x) ∧ ∀y ∈ x Succ(y)). Zeigen Sie ω = {x | Nat(x)}.

(b) Es sei n eine konkret gegebene natürliche Zahl. Zeigen Sie ˜0 = min(ω) und ñ =

min(ω \ \{˜0, …, { \atop n − 1}\}).

(c) Es sei FIN das Axiomensystem von Folge 3, Aufgabe 4. Zeigen Sie, dass aus FIN die Negation des Unendlichkeitsaxioms folgt.

Aufgabe 4 Nach Zermelo werden die natürlichen Zahlen als Mengen durch iteriertes Mengenbilden modelliert: 0 ≡ ∅, 1 ≡ {∅}, 2 ≡ {{∅}}, … Wir wollen diese Zermelo-Zahlen in der ∈- Sprache formalisieren. Hierzu setzen wir

L(u, x) :≡ ∅ ∈ u ∧ x ∈ u ∧ {x} ∉ u ∧
∀v ∈ u ((v ≠ ∅ → ∃w ∈ u v = {w}) ∧ (v ≠ x → {v} ∈ u))
Zz(x) :≡ ∃u L(u, x)

Gilt L(u, x), so nennen wir u auch eine Leiter für x. Es sei nun ω^{∗} :≡ {x | Zz(x)}. Zeigen Sie, dass durch

x_{0} <^{∗} x_{1} :≡ x_{0} ≠ x_{1} ∧ ∃u_{0}, u_{1} (L(u_{0}, x_{0}) ∧ L(u_{1}, x_{1}) ∧ u_{0} ⊆ u_{1})

eine Wohlordnung auf ω^{∗} definiert ist.