[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 13, Abgabe: 01.02.2001 in der Vorlesung

Aufgabe 1 Es sei L eine formale Sprache, 𝔄 und 𝔅 seien L-Strukturen und π: 𝔄 → 𝔅 sei ein Isomorphismus. Zeigen Sie, dass π eine elementare Abbildung ist, d.h., für jede Belegung β in 𝔄 und jedes φ ∈ Fml(L) gilt 𝔄 ⊧ φ[β] genau dann wenn 𝔅 ⊧ φ[π ∘ β]. Folgern Sie, dass 𝔄 und 𝔅 elementar äquivalent sind: Für jedes φ ∈ Fml(L) mit fr(φ) = ∅ gilt 𝔄 ⊧ φ genau dann wenn 𝔅 ⊧ φ.

Aufgabe 2 Eine L_{Äq}-Formel φ heißt beschränkt, wenn jeder in φ vorkommende Quantor von der Form ˙∃ v̇_{n}˙(Ṙv̇_{n}v̇_{m} ˙∧ … ˙) bzw. ˙∀ v̇_{n}˙(Ṙv̇_{n}v̇_{m} ˙→ … ˙).

(a) Geben Sie (rekursiv) eine exakte Definition der Menge der beschränkten L_{Äq}-Formeln an.

(b) Es seien 𝔄 und 𝔅 strikte lineare Ordnungen, d.h., Modelle von

Φ_{SLO} :≡ { ˙∀ v̇_{0} ˙¬ Ṙv̇_{0}v̇_{0}, ˙∀ v̇_{0} ˙∀ v̇_{1} ˙( ˙¬ v̇_{0} ≐ v̇_{1} ˙→ ˙(Ṙv̇_{0}v̇_{1} ˙∨ Ṙv̇_{1}v̇_{0}˙)˙),
˙∀ v̇_{0} ˙∀ v̇_{1} ˙∀ v̇_{2} ˙(˙(Ṙv̇_{0}v̇_{1} ˙∧ Ṙv̇_{1}v̇_{2}˙) ˙→ Ṙv̇_{0}v̇_{2}˙)}.

Es sei 𝔄 eine Substruktur von 𝔅 und der Träger A von 𝔄 sei ein Anfangsstück des Trägers B von 𝔅, d.h., es gibt ein b ∈ B mit A = {a ∈ B | a < b}, wobei wir mit < die Interpretation von Ṙ in 𝔅 bezeichnen. Zeigen Sie: Ist β eine Belegung in 𝔄, so gilt für jede beschränkte L_{Äq}-Formel φ: 𝔄 ⊧ φ[β] ⟺ 𝔅 ⊧ φ[β].

(c) Bleibt (b) richtig, wenn man auf die Voraussetzung, dass A ein Anfangsstück von B ist oder dass φ beschränkt ist, verzichtet?

Aufgabe 3 Es sei L eine formale Sprache. Eine Formel φ ∈ Fml(L) heißt ∀-Formel von L, falls sie von der Form ˙∀ v̇_{i_{0}} … ˙∀ v̇_{i_{n−1}}ψ mit ψ quantorenfrei ist. Sie heißt ∃-Formel von L, falls sie von der Form ˙∃ v̇_{i_{0}} … ˙∃ v̇_{i_{n−1}}ψ mit ψ quantorenfrei ist.

(a) Geben Sie (rekursiv) eine exakte Definition der Menge der ∀-Formel von L und der Menge der ∃-Formeln von L an.

(b) Es seien 𝔄 und 𝔅 L-Strukturen und 𝔄 sei eine Substruktur von 𝔅. Ferner sei β eine Belegung in 𝔄. Zeigen Sie: (α) Falls φ eine ∀-Formel ist und 𝔅 ⊧ φ[β] gilt, so gilt 𝔄 ⊧ φ[β]. (β) Falls φ eine ∃-Formel ist und 𝔄 ⊧ φ[β] gilt, so gilt 𝔅 ⊧ φ[β]. Bleiben diese Aussagen richtig, wenn man auf die Voraussetzungen, dass φ eine ∀-Formel bzw. eine ∃-Formel ist, verzichtet?

Aufgabe 4 Es sei L eine abzählbare Sprache und 𝔄 sei eine L-Struktur. Ferner sei X ⊆ A und κ ∈ Card mit \overline{\overline{X}} ≤ κ < \overline{\overline{A}}. Zeigen Sie, dass es eine elementare Substruktur 𝔅 von 𝔄 gibt, deren Träger Kardinalität κ hat und X umfasst. Hierbei heißt 𝔅 elementare Substruktur von 𝔄, falls 𝔅 eine Substruktur von 𝔄 ist und für jede Belegung β in 𝔅 und jedes φ ∈ Fml(L) gilt: 𝔅 ⊧ φ[β] ⟺ 𝔄 ⊧ φ[β]. Tipp: Man kann o.E. annehmen, dass \overline{\overline{X}} = κ gilt. Mit Hilfe des Auswahlaxioms definiere dann für jede Formel ˙∃ v̇_{m}φ, deren freie Variablen unter v̇_{0}, …, v̇_{n−1} vorkommen, eine Funktion f_{˙∃ v̇_{m}φ}: A^{n} → A so, dass f_{˙∃ v̇_{m}φ}(a_{0}, …, a_{n−1}) ein Zeuge der Existenz 𝔄 ⊧ ˙∃ v̇_{m}φ[a_{0}, …, a_{n−1}] ist. Schliesse dann X gegen diese Funktionen ab.