Ehrenfeucht-Fraisse-Spiele Flashcards
(5 cards)
Definition 3.18: lokaler Isomorphismus (skript 83)
Sei tau eine relationale Signatur und A~, B~ tau-Strukturen. Ein lokaler (oder partieller) Isomorphismus von A~ nach B~ ist eine injektive Abbildung p: dom(p) -> B wobei dom(p) teilmenge A, so dass für alle n element Nat.Z., alle n-stelligen Relationssymbole R element tau und alle a1, …, an element dom(p) gilt:
(a1, …, an) element R^A~ gdw. (pa1, …, pan) element R^B~
Satz von Ehrenfeucht, Fraisse (Satz 3.21, Skript 86)
Sei tau endlich und relational, A~, B~ tau-Strukturen.
1) Folgende Aussagen sind äquivalent:
i) A~ elementar äquivalent B~
ii) Die Duplikatorin gewinnt das Ehrenfeucht-Fraisse-Spiel G(A~, B~)
2) Für alle m element Nat.Z. sind folgende Aussagen äquivalent:
i) A~ m-äquivalent B~
ii) Die Duplikatorin gewinnt G_m(A~, B~)
Wann gewinnt der Herausforderer, wann die Duplikatorin im Spiel G(A~, B~)?
Der Herausforderer bestimmt in jedem Spiel zunächst eine Zuganzahl m, dann wird G_m gespielt.
Wenn also die Duplikatorin für jedes m element Nat.Z. eine Gewinnstrategie im Spiel G(A~, B~) hat, gewinnt die Duplikatorin. Sonst der Herausforderer.
Satz 3.22: Wann hat der Herausforderer eine Gewinnstrategie im Spiel G_m(A~, _a, B~, _b)?
(_a und _b bezeichnen eine Menge von zu wählenden Variablen aus dem Universum von A~ bzw B~)
(Skript 88)
Seien A~, B~ tau-Strukturen, _a = a1, .., ar element A, _b = b1, … , br element B. Wenn es eine Formel psi(_x) mit qr(psi) = m gibt, so dass A~ |= psi(_a) und B |= ‘nicht psi’(_b), dann hat der Herausforder eine Gewinnstrategie für G_m(A~, _a, B~, _b).
Anders gesagt: es gibt eine Formel mit Quantorenrang m, die A~ und B~ unterscheiden kann, dann gewinnt der Herausforderer in m Zügen
Satz 3.26 Ist Graphenzusammenhang definierbar? (Skript 89)
Es gibt keinen Satz psi element FO(tau), so dass für jeden (endlichen, ungerichteten) Graphen G= (V, E) gilt:
G |= psi gdw. G ist zusammenhängend
