MATHEMATISCHES INSTITUT DER UNIVERSITÄT BONN Arbeitsgruppe Mathematische Logik Prof. Dr. Peter Koepke

Bonn, den 06.06.2002

Einführung in die Mathematische Logik SS 2002

Übungsaufgaben, Folge 7, Abgabe: 13.06 nach der Vorlesung

Aufgabe 1 (a) Für jeden S-Ausdruck φ sei var(φ) die Menge der Variablen in φ und frei(φ) die Menge der freien Variablen in φ. Geben Sie eine formale Definition der Mengen var und frei an und rechtfertigen Sie diese anhand des Rekursionssatzes für das Ausdruckskalkül.

(b) Um die Definition der Modellbeziehung (𝔄, β) ⊧ φ korrekt durchzuführen, geben Sie

eine rekursive Definition einer Hilfsfunktion B_{𝔄}(φ) an, welche die intuitive Bedeutung

B_{𝔄}(φ) = {γ | γ ist eine Belegung in 𝔄 und (𝔄, γ) ⊧ φ} hat, und definieren sie hieraus (𝔄, β) ⊧ φ.

Aufgabe 2 Für jeden S-Ausdruck φ definiere die Menge geb(φ) der gebundenen Variablen von φ durch geb(φ) = ∅, falls φ ein atomarer Ausdruck ist, und geb((ψ ∧ χ)) = geb((ψ ∨ χ)) = geb(ψ) ∪ geb(χ) sowie geb(¬ψ) = geb(ψ) und geb(∃v_{i} ψ) = geb(∀v_{i} ψ) = geb(ψ) ∪ {v_{i}}.

(a) Berechnen Sie geb(φ) für die folgenden Ausdrücke φ.

(α) Rfv_{0}v_{1}gv_{2}

(β) ∀v_{0} ∀v_{1} ∀v_{2} ∃v_{3} (v_{3} = gv_{2} → (Rfv_{0}v_{1}v_{3} ∧ v_{1} = v_{4}))

(γ) ∃v_{3} (c = v_{4} ↔ ∃v_{6} ¬v_{6} = fgv_{0}v_{6}).

Hierbei sei R ein zweistelliges Relationssymbol, f ein zweistelliges und g ein einstelliges Funktionssymbol, c sei ein Konstantensymbol.

(b) Zeigen Sie, daß var(φ) = frei(φ)∪geb(φ) für jeden S-Ausdruck φ gilt. Gilt stets frei(φ)∩ geb(φ) = ∅?

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

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

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

Definition: 𝔄 und 𝔅 seien S-Strukturen. Eine Abbildung π : A → B ist ein Isomorphismus von 𝔄 auf 𝔅, kurz π : 𝔄 ≅ 𝔅, wenn gilt:

1. π ist eine Bijektion von A auf B.

2. Für r ∈ R_{n} und a_{1}, ⋯, a_{n} ∈ A gilt:

r^{𝔄}(a_{1}, ⋯, a_{n}) ⇔ r^{𝔅}(π(a_{1}), ⋯, π(a_{n})).

3. Für f ∈ F_{n} und a_{1}, ⋯, a_{n} ∈ A gilt:

π(f^{𝔄}(a_{1}, ⋯, a_{n})) = f^{𝔅}(π(a_{1}), ⋯, π(a_{n})).

4. Für c ∈ C gilt π(c^{𝔄}) = c^{𝔅}.

𝔄 und 𝔅 heißen isomorph, kurz 𝔄 ≅ 𝔅, genau dann, wenn es einen Isomorphismus π : 𝔄 ≅ 𝔅 gibt. Ein Automorphismus von 𝔄 ist ein Isomorphismus π : 𝔄 ≅ 𝔄 von 𝔄 auf 𝔄.

Definition: 𝔄 und 𝔅 seien S-Strukturen. Dann heißt 𝔄 Substruktur von 𝔅, kurz 𝔄 ⊆ 𝔅, wenn gilt:

1. A ⊆ B.

2. Für r ∈ R_{n} gilt r^{𝔄} = r^{𝔅} ∩ A^{n}.

3. Für f ∈ F_{n} und a_{1}, ⋯, a_{n} ∈ A gilt f^{𝔄}(a_{1}, ⋯, a_{n}) = f^{𝔅}(a_{1}, ⋯, a_{n}).

4. Für c ∈ C gilt c^{𝔄} = c^{𝔅}.

Aufgabe 4 (a) Zeigen Sie, daß die Automorphismen einer Struktur 𝔄 eine Gruppe bilden.

(b) Sei U eine Untergruppe der Automorphismengruppe einer Struktur 𝔄. Sei F die Menge der Fixpunkte von 𝔄 unter U, d.h. F = {a ∈ A | ∀π ∈ U(a = π(a))}. Zeigen Sie, daß 𝔉, die Struktur mit Träger F und den auf F eingeschränkten Relationen und Funktionen von 𝔄, eine Substruktur von 𝔄 ist.

(c) Geben Sie eine unendliche Struktur an, deren einziger Automorphismus die Identität ist.

(d) Geben Sie eine abzählbare Struktur mit überabzählbarer Automorphismengruppe an.

Homepage der Vorlesung:

http://www.math.uni-bonn.de/people/logic/Lectures/SoSe2002/Vorlesung.html
Newsgroup: uni-bonn.math.logik