Übungen zur Vorlesung Mathematische Logik SS 2008, Blatt 7

Aufgabe 32.

1. Ist für beliebige φ und ψ die Regel \begin{matrix}Γ & φ \\ Γ & ψ \\ Γ & (φ ∧ ψ) \end{matrix} ableitbar?

2. Ist für beliebige φ und ψ die Sequenz (φ ∨ ¬ψ) ψ φ ableitbar?

Aufgabe 33. Sei S = {R} mit zweistelligem R. Man zeige jeweils mittels des Isomorphielemmas, daß die S-Strukturen 𝔄 und 𝔅 nicht isomorph sind.

1. Die Graphen 𝔄 = [figure]und 𝔅 = [figure]

2. Die Graphen 𝔄 = [figure]und 𝔅 = [figure]

3. Die Graphen 𝔄 = [figure]und 𝔅 = [figure] [figure]

4. Die Ordnungen 𝔄 = (ℕ, <) und 𝔅 = (ℤ, <)

5. Die Strukturen 𝔄 = (ℤ, ≡_{2}) und 𝔅 = (ℤ, ≡_{3}), wobei ≡_{n} für n ∈ ℕ definiert ist durch ≡_{n}= {(p, q) | p, q ∈ ℤ, n|q − p}.

Aufgabe 34. Sei die {E}-Struktur 𝔊 ein Graph. Man gebe für n ≥ 0 eine Formel φ_{n}(x, y) an, sodaß für alle a, b ∈ G gilt:

𝔊 ⊧ φ_{n}[a, b] ⟺ es gibt einen Weg der Länge n von a nach b in 𝔊.

Für n ≥ 0 ist ein Tupel (a_{0}, …, a_{n}) ∈ G^{n+1} ein Weg in 𝔊 gdw. für i = 1, …, n gilt: (a_{i−1}, a_{i}) ∈ E^{𝔊}; (a_{0}, …, a_{n}) ist dann ein Weg in 𝔊 von a_{0} nach a_{n} der Länge n. Aufgabe 35. Sei Φ ⊆ L^{S} widerspruchsfrei und ℑ^{Φ} die Henkin-Interpretation zu Φ. Man zeige:

1. Falls jedes φ ∈ Φ die Gestalt φ = ∀x_{1} … ∀x_{n}ψ mit atomarem ψ hat, so gilt ℑ^{Φ} ⊧ Φ. Man folgere: die Struktur 𝔗^{Φ_{Grp}} ist eine Gruppe.

2. Gilt ℑ^{Φ} ⊧ Φ, so hat ℑ^{Φ} die folgende universelle Eigenschaft: Für jedes Modell ℑ = (𝔄, β) von Φ wird durch h : \overline{t} ↦ ℑ(t) für t ∈ T^{S} ein Homomorphismus h : 𝔗^{Φ} → 𝔄 definiert. (Insbesondere ist zu zeigen, daß h wohldefiniert ist.)

Aufgabe 36. Seien V_{n} und V_{ℕ} wie in Aufgabe 31 definiert. Sei \underline{ε} ein zweistelliges Relationssymbol und

\underline{ε}^{V_{n}} = \{(x, y) | x, y ∈ V_{n}, x ∈ y\} ,
\underline{ε}^{V_{ℕ}} = \{(x, y) | x, y ∈ V_{ℕ}, x ∈ y\} .

Gilt (V_{5}, \underline{ε}^{V_{5}}) ⊧ φ, (V_{ℕ}, \underline{ε}^{V_{ℕ}}) ⊧ φ für folgende Aussagen φ?

(EXT) φ = ∀x∀y(∀z(\underline{ε}zx ↔ \underline{ε}zy) → x ≡ y)
(PAAR) φ = ∀x∀y∃z∀w(\underline{ε}wz ↔ (w ≡ x ∨ w ≡ y))
(POT) φ = ∀x∃y∀z(\underline{ε}zy ↔ ∀v(\underline{ε}wz ← \underline{ε}wx))
(AUS) φ = ∀x_{1} … ∀x_{n}∀x∃y∀z(\underline{ε}zy ↔ (\underline{ε}zx ∧ ψ(z, x_{1} …, x_{n}))) für ψ(z, x_{1}, …, x_{n}) beliebig.

Abgabe: Mittwoch, 18. Juni 2008, vor der Vorlesung.