[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 12, Abgabe: 25.01.2001 in der Vorlesung

Aufgabe 1 Untersuchen Sie, ob die folgenden L_{Arith}-Modellklassen axiomatisierbar sind:

(a) die Modellklasse der endlichen Körper.

(b) die Modellklasse der unendlichen Körper.

(c) die Modellklasse der abzählbaren Körper.

(d) die Modellklasse der überabzählbaren Körper.

Aufgabe 2 Es sei L eine formale Sprache. Wir definieren die Menge P (L) der Formeln von L, die in pränexer Normalform sind, rekursiv durch

P_{0}(L) :≡ {φ ∈ Fml(L) | φ ist quantorenfrei};
P_{n+1}(L) :≡ P_{n}(L) ∪ { ˙∃ v̇_{i} φ | φ ∈ P_{n}(L) ∧ i < ω} ∪ { ˙∀ v̇_{i} φ | φ ∈ P_{n}(L) ∧ i < ω};
P (L) :≡ ⋃_{n<ω} P_{n}(L).

Zeigen Sie, dass es zu jedem φ ∈ Fml(L) ein φ′ ∈ P (L) gibt mit ⊧ ˙(φ ˙↔ φ′˙).

Aufgabe 3 Es sei (X, <) eine partielle Ordnung und n < ω. Ferner seien x_{1}, …, x_{n} ∈ X. Dann heißt (x_{1}, …, x_{n}) ein Weg in X (der Länge n) von x_{1} nach x_{n} falls gilt:

(i) Für 0 < i < n ist x_{i} der direkte <-Vorgänger von x_{i+1}. (ii) Für i ≠ j gilt x_{i} ≠ x_{j}. Ein Weg (x_{1}, …, x_{n}) heißt Kreis in X, falls x_{1} = x_{n} gilt. Die partielle Ordnung (X, <) heißt kreisfrei, falls X keine nichttrivialen Kreise (d.h., keine Kreise der Länge größer als 1) besitzt. Axiomatisieren Sie in der Sprache L_{Äq} die Modellklasse ℳ der kreisfreien partiellen Ordnungen. Hat ℳ eine endliche Axiomatisierung, d.h., gibt es ein endliches Φ ⊆ Fml(L) mit fr(Φ) = ∅, so dass Φ die Modellklasse ℳ axiomatisiert? Tipp: Überlegen (und zeigen) Sie: Mod^{L_{Äq}}(Ψ) hat genau dann eine endliche Axiomatisierung, wenn es ein endliches Φ ⊆ Ψ gibt, das Mod^{L_{Äq}}(Ψ) axiomatisiert.

Aufgabe 4 (Nichtstandardmodell von ℝ) Wir erweitern die Sprache L_{aoK} zur Sprache L_{ℝ}, indem wir für jede reelle Zahl r ein neues Konstantensymbol ċ_{r} hinzufügen. Dann erweitern wir die L_{aoK}-Struktur ℝ zu einer L_{ℝ}- Struktur ℝ̃ indem wir für r ∈ ℝ das Konstantensymbol ċ_{r} durch r interpretieren. Schliesslich setzen wir Φ :≡ {φ ∈ Fml(L_{ℝ}) | frei(φ) = ∅ ∧ ℝ̃ ⊧ φ}.

(a) Zeigen Sie, dass Φ ein Modell ℝ̃^{∗} der Kardinalität (2^{ℵ_{0}})^{+} hat, deren Trägermenge R̃^{∗} zur Menge der reellen Zahlen disjunkt ist.

(b) Zeigen Sie, dass auf R^{∗} :≡ (R̃^{∗} \ {ċ^{ℝ̃^{∗}} | r ∈ ℝ}) ∪ ℝ eine L_{aoK}-Struktur ℝ^{∗} definiert werden kann, so dass folgendes gilt: Für jedes φ ∈ Fml(L_{aoK}) und jede Belegung β mit Werten in ℝ (!) gilt ℝ ⊧ φ[β] genau dann wenn ℝ^{∗} ⊧ φ[β]. Schliessen Sie hieraus, dass ℝ^{∗} ein angeordneter Oberkörper des angeordneten Körpers ℝ ist.

(c) Zeigen Sie, dass es ein x ∈ ℝ^{∗} gibt mit 0 < x < r für jedes r ∈ ℝ.

Tipp: Wählen Sie ein y ∈ R^{∗} \ℝ und setzen Sie x = 1/y, falls r < y für alle r ∈ ℝ, bzw. x = −1/y, falls r > y für alle r ∈ ℝ, bzw. x = y − sup{r ∈ ℝ | r < y}, falls 0 < y < r für ein r ∈ ℝ, bzw. x = y − inf{r ∈ ℝ | y < r}, falls r < y < 0 für ein r ∈ ℝ.