[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 9, Abgabe: 04.01.2001 in der Vorlesung

Aufgabe 1 Zeigen Sie, dass der Satz (∗) Ich gehe Känguruhs aus dem Weg aus den folgenden Sätzen (a) — (j) logisch folgt.

(a) Die einzigen Tiere in diesem Haus sind Katzen.

(b) Jedes Tier ist als Schoßtier geeignet, das gerne in den Mond guckt.

(c) Wenn ich ein Tier verabscheue, so gehe ich ihm aus dem Weg.

(d) Nur solche Tiere sind Fleischfresser, die nachts umherschweifen.

(e) Jede Katze tötet Mäuse.

(f) Nur die Tiere in diesem Haus mögen mich leiden.

(g) Känguruhs sind nicht als Schoßtiere geeignet.

(h) Nur Fleischfresser töten Mäuse.

(i) Ich verabscheue Tiere, die mich nicht leiden mögen.

(j) Tiere, die nachts umherschweifen, gucken gerne in den Mond. Wählen Sie hierzu eine passende formale Sprache L, übersetzen Sie die Aussagen (∗) sowie (a) bis (j) in L-Formeln φ_{∗}, φ_{a}, …, φ_{j} und zeigen Sie φ_{a}, …, φ_{j} ⊧ φ_{∗}.

Aufgabe 2 Es sei n eine natürliche Zahl, n ≥ 1. Axiomatisieren Sie in der Sprache L_{Äq} die folgenden Modellklassen:

(a) die Modellklasse der strikten linearen Ordnungen;

(b) die Modellklasse der Äquivalenzrelationen mit genau n Äquivalenzklassen;

(c) die Modellklasse der Äquivalenzrelationen mit unendlich vielen Äquivalenzklassen;

(d) die Modellklasse der Äquivalenzrelationen mit unendlich vielen Äquivalenzklassen, die alle höchstens n Elemente enthalten;

(e) die Modellklasse der Äquivalenzrelationen mit unendlich vielen Äquivalenzklassen, die alle unendlich viele Elemente enthalten.

Aufgabe 3 Es sei n eine natürliche Zahl, n ≥ 1, und p sei eine Primzahl. Axiomatisieren Sie jeweils in einer geeigneten formalen Sprache die folgenden Modellklassen:

(a) die Modellklasse der torsionsfreien Gruppen;

(b) die Modellklasse der reell abgeschlossenen Körper;

(c) die Modellklasse der Körper mit genau p^{n} Elementen.

Erinnerung: Eine Gruppe heißt torsionsfrei, wenn für jede natürliche Zahl m die m-fache Verknüpfung eines jeden, vom neutralen Element e verschiedenen Elements mit sich selbst von e verschieden ist. Ein Körper heißt angeordnet, wenn seine Elemente durch eine lineare Ordnung < geordnet sind, die a+c < b+c für a < b sowie 0 < a·b für 0 < a und 0 < b erfüllt. Ein Körper heißt reell abgeschlossen, wenn er angeordnet ist, jedes a > 0 ein Quadrat ist und jedes Polynom von ungeradem Grad eine Nullstelle hat.

Aufgabe 4 Es sei L eine formale Sprache. Es seien ⊢_{L}^{1} bzw. ⊢_{L}^{2} bzw. ⊢_{L}^{3} die ⊆-kleinsten Teilmengen von 𝒫(Fml(L)) × Fml(L), die die Regeln des Sequenzenkalküls erfüllen, wenn man

• bei ⊢_{L}^{1} bei der Instanzierungsregel (∀1) auf die Voraussetzung φ, s kollisionsfrei,

• bei ⊢_{L}^{2} bei der Universalisierungsregel (∀2) auf die Voraussetzung y ∉ fr(Φ) ∪ var(φ),

• bei ⊢_{L}^{3} bei der Gleichheitssregel (=) auf die Voraussetzung φ ∈ At(L), verzichtet und jeweils alle anderen Regeln unverändert lässt. Untersuchen Sie, ob ⊢_{L}^{1} bzw. ⊢_{L}^{2} bzw. ⊢_{L}^{3} korrekt sind.

Im Folgenden ausser Konkurrenz noch eine Aufgabe mit hohem Schwierigkeitsgrad. Bei ihrer Lösung erzielte Punkte werden Ihrem Punktekonto gutgeschrieben.

Aufgabe 5 Es sei L = (I, J, K, t) eine formale Sprache und Φ sei eine L-Theorie. Zwei L-Strukturen 𝔄 = (A, (R_{i})_{i∈I}, (f_{j})_{j∈J}, (c_{k})_{k∈K}, t) und 𝔅 = (B, (S_{i})_{i∈I}, (g_{j})_{j∈J}, (d_{k})_{k∈K}, t) heißen isomorph, in Zeichen 𝔄 ≅ 𝔅, falls es eine Bijektion π: A → B gibt mit

• ∀i ∈ I (R_{i}(π(a_{0}), …, π(a_{t(i)−1})) ⟷ S_{i}(π(a_{0}), …, π(a_{t(i)−1}))),

• ∀j ∈ J π(f_{j}(a_{0}, …, a_{t(j)−1})) = g_{j}(π(a_{0}), …, π(a_{t(j)−1})),

• ∀k ∈ K π(c_{k}) = d_{k}.

Für λ ∈ Card sei Mod_{λ}^{L}(Φ) :≡ \{𝔄 ∈ Mod^{L}(Φ) | \overline{\overline{A}} = λ\}. Dann ist ≅ eine Äquivalenzrelation auf Mod_{λ}^{L}(Φ). Es sei Mod_{λ}^{L}(Φ)/ ≅ ein vollständiges Repräsentantensystem dieser Äquivalenzrelation, d.h., die Elemente von Mod_{λ}^{L}(Φ)/ ≅ sind paarweise nicht äquivalent und jedes Element von Mod_{λ}^{L}(Φ) ist zu einem Element von Mod_{λ}^{L}(Φ)/ ≅ äquivalent. Es sei schließlich

I(λ, Φ) :≡ \overline{\overline{Mod_{λ}^{L}(Φ)/ ≅}}.

(a) Zeigen Sie I(λ, Φ) ≤ 2^{λ}, falls λ ≥ \overline{\overline{I ∪ J ∪ K}} + ℵ_{0}.

(b) Geben Sie eine Theorie Φ (in einer geeigneten Sprache L) an mit I(λ, Φ) = 1 für alle λ ≥ ω.

(c) Es sei Φ ⊆ Fml(L_{Äq}) eine Axiomatisierung der Modellklasse der strikten linearen Ordnungen. Zeigen Sie I(λ, Φ) = 2^{λ} für alle λ ≥ ω. Tipp: Für X ⊆ λ definiere eine Menge λ(X) wie folgt. Für α ∈ λ setze

λ_{α}(X) :≡ \{ \begin{matrix}ℤ × \{α\}, & falls α ∈ X, \\ \{(α, α)\}, & falls α ∉ X, \end{matrix}

und definiere λ(X) :≡ ⋃_{α<λ} λ_{α}(X). Anschaulich entsteht λ(X) aus λ, indem jeder Punkt α ∈ X durch (eine Kopie von) ℤ ersetzt wird. Definiere auf λ(X) eine Relation <_{λ(X)} durch

(k, ζ) <_{λ(X)} (l, η) :≡ (ζ ∈ η oder (ζ = η und k < l)), wobei < die kanonische Ordnung der Menge der ganzen Zahlen bezeichnet. Es sei 𝔄(X) :≡ (λ(X), <_{λ(X)}). Zeige: Für X, Y ⊆ λ mit X ≠ Y sind 𝔄(X) und 𝔄(Y) nicht isomorph.