Transcript
UE GRUNDBEGRIFFE DER MATHEMATISCHEN LOGIK ¨ (SS 2016): UBUNGSBLATT 3, 05.04.2016
Aufgabe 1. Es seien A und B L-Strukturen. Dann heisst A Unterstruktur von B (bezeichnet A ⊆ B) wenn A ⊆ B und (1) f¨ ur n-stelliges R ∈ L, RA = RB ∩ An (2) f¨ ur n-stelliges f ∈ L ist f A = f B An (3) f¨ ur Konstanten c ∈ L ist cA = cB . Zeigen Sie, dass f¨ ur jede nicht-leere Teilmenge X von B es eine Unterstruktur A von B gibt, so dass X ⊆ A und f¨ ur alle C ⊆ B mit X ⊆ C gilt A ⊆ C. Die B Struktur A wird durch hXi bezeichnet und heisst die von X in B erzeugte Unterstruktur . Hinweis: Die Struktur hXiB hat Universum [ {tB [b1 , · · · , bn ] : b1 , · · · , bn ∈ X, t(x1 , · · · , xn ) L-term}. n∈N
Aufgabe 2. Eine Formel, die keine Quantoren enth¨alt heisst quantorenfrei . Sei A ⊆ B und sei β eine Belegung in A. Zeigen Sie die folgenden Aussagen: (1) f¨ ur jeden L-Term t, tA [β] = tB [β] (2) f¨ ur jede quantorenfreie L-Formel ϕ, A ϕ[β] gdw B ϕ[β]. Hinweis: Benutzen Sie Induktion u ¨ber den Aufbau der L-Terme und LFormeln. Aufgabe 3. Seien A und B L-Strukturen. Eine Abbildung π : A → B heisst Isomorphismus von A auf B (bezeichnet π : A ∼ = B) wenn (1) π eine Bijektion von A auf B ist, (2) f¨ ur n-stelliges Relationssymbol R ∈ L und a1 , · · · , an ∈ A: (a1 · · · an ) ∈ RA gdw (π(a1 ) · · · π(an )) ∈ RB , (3) f¨ ur n-stelliges Funktionssymbol f ∈ L und a1 , · · · , an ∈ A: π(f A (a1 , · · · , an )) = f B (π(a1 ), · · · , π(an )), (4) f¨ ur Konstanten c ∈ L, π(cA ) = cB ist. Die Strukturen A und B heissen isomorph wenn es einen Isomorphismus π:A∼ = B gibt. (1) Sei π : A ∼ ur jede Formel ϕ = ϕ(x1 , · · · , xn ) = B. Zeigen Sie, dass f¨ und alle a1 , · · · , an in A, A ϕ[a0 , · · · , an−1 ] gdw B ϕ[π(a0 ), · · · , π(an−1 )]. 1
2
UE GRUNDBEGRIFFE DER MATHEMATISCHEN LOGIK
(2) Sei A eine L-Struktur. Eine Teilmenge X von An heisst definierbar in A wenn es eine Formel ϕ = ϕ(x1 , · · · , xn ) gibt, so dass X = {(a1 , · · · , an ) ∈ An : A ϕ[a1 , · · · , an ]}. Zeigen Sie, dass wenn X ⊆ An definierbar und π ein Isomorphismus von A auf A ist, dann {π(a) : a ∈ X} = X. Aufgabe 4. Sei L0 = {+, · , 0}, L1 = {+, 0} Sprachen. Betrachten Sie die L0 -Struktur A und L1 -Struktur B, wobei A = B = R und +A , +B , 0A , 0B , ·A die u ¨blichen Objekte auf R sind. Sei X := {(r0 , r1 ) ∈ R2 : r0 < r1 }, d.h. X ist die Kleiner-Beziehung auf R. Zeigen Sie, dass (1) X defnierbar in A ist, (2) X nicht definierbar in B ist. Hinweis: Um zu zeigen dass X in B nicht defnierbar ist, betrachten Sie einen geigneten Isomorphismus von B auf sich selbst. ¨ del Research Center, University of Vienna, Wa ¨ hringerstrasse 25, Kurt Go 1090 Vienna, Austria E-mail address:
[email protected]
