Übungen zur Vorlesung Mathematische Logik SS 2008, Blatt 11

Aufgabe 52. (a) Es sei S beliebig. Geben Sie einen L_{II}^{S}-Satz φ an, sodaß

Mod(φ) = {𝔄 | 𝔄 S-Struktur, A endlich, |A| gerade}.

(b) Seien X und Y einstellige Relationsvariablen. Gebe Sie einen L_{M II}^{S_{Grp}}-Ausdruck φ(X, Y) mit freien Variablen X, Y an, sodaß für alle Gruppen 𝔊 und alle M, U ⊆ G gilt: 𝔊 ⊧ φ[M, U] genau dann, wenn U der Träger der von M erzeugten Untergruppe von 𝔊 ist. (𝔊 ⊧ φ[M, U] bedeutet (𝔊, γ) ⊧ φ mit γ(X) = M und γ(Y) = U).

Aufgabe 53. Sei S höchstens abzählbar und T ⊆ L_{0}^{S} eine Theorie, die nur unendliche Modelle besitzt (insbesondere hat T also ein abzählbares Modell). Weiterhin seien alle abzählbaren Modelle von T paarweise isomorph. Zeigen Sie, daß T vollständig ist.

Aufgabe 54. Sei T eine Theorie, Φ R-aufzählbar und T = Φ^{⊧}. Zeigen Sie, daß T bereits R-axiomatisierbar ist.

Aufgabe 55. Für eine Symbolmenge S sei

Φ_{e}^{S} = {φ ∈ L_{0}^{S} | φ ist im Endlichen erfüllbar}.

Zeigen Sie für S = {E} mit einem zweistelligen Relationssymbol E, daß Φ_{e}^{S} R-aufzählbar ist. Ist auch Φ_{e}^{S_{∞}} R-aufzählbar? Zeigen Sie, daß Φ_{e}^{S_{∞}} nicht R-entscheidbar ist.

Aufgabe 56. Sei S endlich und φ = ∃X_{1} … ∃X_{m}ψ ein fester L_{II}^{S}-Satz, wobei X_{1}, …, X_{m} Relationsvariablen beliebiger Stellenzahl sind und ψ keine Quantoren zweiter Stufe enthält. Zeigen Sie: Es gibt ein NPTIME-Verfahren, das angesetzt auf eine endliche S-Struktur \underline{\underline{𝔄}}, deren Träger die Gestalt [n] für ein geeignetes n ∈ ℕ hat, entscheidet, ob 𝔄 ⊧ φ.

Hinweis: Verwenden Sie Aufgabe 50.

Abgabe: Mittwoch, 16. Juli 2008, vor der Vorlesung.