EF-Spiel

EF-Spiel

Ehrenfeucht-Fraïssé-Spiele (EF-Spiele) sind eine Beweistechnik der Modelltheorie. Durch EF-Spiele lässt sich die Äquivalenz zweier Strukturen zeigen bzw. widerlegen. Strukturen dienen in der beschreibenden Komplexitätstheorie meist als Formalismus zur Beschreibung von Objekten wie Wörtern oder Graphen. Ehrenfeucht-Fraïssé-Spiele liefern so ein Hilfsmittel zum Beweisen von unteren Schranken, also zum Beweis, dass sich eine gegebene Klasse von Strukturen nicht durch eine bestimmte Logik ausdrücken lässt.

Entwickelt wurden sie von Andrzej Ehrenfeucht auf Grundlage der theoretischen Arbeit des Mathematikers Roland Fraïssé.

Ein EF-Spiel wird von zwei Spielern gespielt, gewöhnlich bezeichnet mit Spoiler und Duplicator (nach Joel Spencer) oder Samson und Delilah (nach Neil Immerman) [1].

Inhaltsverzeichnis

Bezeichnungen

  • Sei \mathcal{A} eine Struktur. Dann bezeichne |\mathcal{A}| das entsprechende Universum (Grundmenge, Trägermenge).
  • STRUKT[σ] bezeichne die Menge aller endlichen Strukturen der Signatur σ.

Das n-Runden-EF-Spiel

Ehrenfeucht-Fraïssé-Spiele in ihrer herkömmlichen Form haben einen engen Bezug zu Logiken erster Stufe. Diese Grundform ist wie folgt definiert.

Definition

Seien

\mathcal{A}, \mathcal{B} zwei Strukturen der gleichen Signatur,
\mathbf{a'} \in |\mathcal{A}|^k, \mathbf{b'} \in |\mathcal{B}|^k,\ \ k, n \in \mathbb{N}.

Ein n-Runden-Spiel wird auf den Interpretationen (\mathcal{A},\mathbf{a'}),(\mathcal{B},\mathbf{b'}) definiert:

Das EF-Spiel G_n((\mathcal{A},\mathbf{a'}),(\mathcal{B},\mathbf{b'})) hat n Runden, die Ausgangsmenge ist \{(a'_0,b'_0),\ \ldots\ ,(a'_{k-1},b'_{k-1})\}\subseteq |\mathcal{A}|\times|\mathcal{B}|;
  • in jeder Runde i (i<n) wählt zunächst Samson ein beliebiges a_i \in |\mathcal{A}| oder ein b_i \in |\mathcal{B}|, welches noch nicht zuvor gewählt wurde
  • falls Samson ein Element aus |\mathcal{A}| gewählt hat, wählt daraufhin Delilah auf dieselbe Weise ein beliebiges b_i \in |\mathcal{B}|, sonst ein a_i \in |\mathcal{A}|
  • das resultierende Tupel (ai,bi) wird zur Ausgangsmenge hinzugefügt.
Nach n Runden resultiert eine Menge von 2-Tupeln \{(a_0,b_0),\ \ldots\ ,(a_{n-1},b_{n-1}),(a'_0,b'_0),\ \ldots\ ,(a'_{k-1},b'_{k-1})\}\subseteq|\mathcal{A}|\times|\mathcal{B}|.
  • Falls durch diese Menge ein partieller Isomorphismus \varphi: |\mathcal{A}|\rightarrow|\mathcal{B}| definiert wird, hat Delilah gewonnen, ansonsten hat Samson gewonnen.
Per Definition gewinnt Delilah das Spiel G_n((\mathcal{A},\mathbf{a'}),(\mathcal{B},\mathbf{b'})), falls sie eine zwingende Gewinnstrategie hat.

Oft gilt k = 0; man schreibt G_n(\mathcal{A},\mathcal{B}) und die Ausgangsmenge ist leer.

Eigenschaften von EF-Spielen

Satz

Zwei Strukturen \mathcal{A}, \mathcal{B} sind n-äquivalent, \mathcal{A}\equiv_n\mathcal{B} \iff Delilah gewinnt G_n(\mathcal{A},\mathcal{B}).

Korollar

\forall n \in\mathbb{N}: \mathcal{A}\equiv_n\mathcal{B} \iff \mathcal{A} und \mathcal{B} sind elementar äquivalent.

Beweisen von unteren Schranken

Um zu beweisen, dass eine Menge I ⊆ STRUKT[σ] nicht durch FO[σ]-Formeln definiert werden kann, genügt es zu zeigen, dass es für jedes n ∈ \mathbb{N} zwei Strukturen \mathcal{A} \in I und \mathcal{B} \in STRUKT[\sigma]\setminus I gibt, so dass Delilah eine Gewinnstrategie für G_n(\mathcal{A},\mathcal{B}) hat.

EF-Spiele für die Prädikatenlogik zweiter Stufe

Ehrenfeucht-Fraïssé-Spiele können relativ problemlos auf Logiken zweiter Stufe erweitert werden. Das Beweisen von Gewinnstrategien wird hierbei jedoch deutlich schwieriger. Eine eingeschränkte Variante sind Spiele für die existentielle Prädikatenlogik zweiter Stufe (SO∃, ESO). SO∃ spielt durch die Charakterisierung der Komplexitätsklasse NP eine wichtige Rolle in der beschreibenden Komplexitätstheorie.

Beschränkt man die SO∃-Logik weiter auf monadische Prädikate (MSO∃), so ist diese Version der EF-Spiele äquivalent zu den Ajtai-Fagin-Spielen [2].

SO∃-Spiele

Definition

Seien

\mathcal{A}, \mathcal{B} zwei Strukturen der gleichen Signatur
c, n \in \mathbb{N},\ \mathbf{s} \in \mathbb{N}^c

die Eingaben für ein SO∃-Spiel.

  • Samson wählt die c Prädikate P_i^\mathcal{A} der Stelligkeit si über |\mathcal{A}|
  • Delilah wählt daraufhin die c Prädikate P_i^\mathcal{B} der Stelligkeit si über |\mathcal{B}|
  • Auf der beiden erweiterten Strukturen wird schließlich das Ehrenfeucht-Fraïssé-Spiel G_n((\mathcal{A},\mathbf{P}^\mathcal{A}),(\mathcal{B},\mathbf{P}^\mathcal{B})) gespielt.

Bei MSO∃-Spielen (Beschränkung auf monadische Prädikate) gilt si = 1 für alle i.

Ajtai-Fagin-Spiele

Ajtai-Fagin-Spiele sind in dem Sinne äquivalent zu den MSO∃-Spielen, als dass Delilah das Ajtai-Fagin-Spiel auf einer Menge I ⊆ STRUKT[σ] gewinnt, genau dann, wenn es für jedes c und jedes n zwei Strukturen \mathcal{A} \in I und \mathcal{B} \in STRUKT[\sigma]\setminus I gibt, so dass sie das entsprechende MSO∃-Spiel gewinnt. Ajtai-Fagin-Spiele sind jedoch formal leichter handhabbar als MSO∃-Spiele.

Definition

Ein Ajtai-Fagin-Spiel wird auf einer Menge von Strukturen I ⊆ STRUKT[σ] gespielt:

  • Zuerst wählt Samson zwei Zahlen c, n \in \mathbb{N}
  • Delilah wählt daraufhin eine Struktur \mathcal{A} \in \emph{I}
  • Samson wählt die monadischen Prädikate P_1^\mathcal{A},\ \ldots\ ,P_c^\mathcal{A} über |\mathcal{A}|
  • Delilah wählt nun eine weitere Struktur \mathcal{B} \in STRUKT[\sigma]\setminus\emph{I} sowie die monadischen Prädikate P_1^\mathcal{B},\ \ldots\ ,P_c^\mathcal{B} über |\mathcal{B}|
  • Nun wird auf den beiden erweiterten Strukturen das Ehrenfeucht-Fraïssé-Spiel G_n((\mathcal{A},\mathbf{P}^\mathcal{A}),(\mathcal{B},\mathbf{P}^\mathcal{B})) gespielt

Satz

Sei I ⊆ STRUKT[σ].

Delilah gewinnt das Ajtai-Fagin-Spiel auf I \iff I ist nicht durch MSO∃[σ]-Logik definierbar.

Referenzen

  1. Stanford Encyclopedia of Philosophy, Logic and Games.
  2. Neil Immerman: Descriptive Complexity. Springer, ISBN 978-0387986005

Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Spiel — das; (e)s, e; 1 nur Sg; etwas (eine Aktivität), das man freiwillig ohne Zweck und zum Vergnügen macht (wie es besonders Kinder tun): das Spiel mit den Puppen || K : Spielgefährte, Spielkamerad, Spieltrieb, Spielwiese, Spielzimmer 2 etwas, womit… …   Langenscheidt Großwörterbuch Deutsch als Fremdsprache

  • Spiel (Begriffsklärung) — Spiel steht für: Spiel, eine Tätigkeit, die zum Vergnügen ausgeführt wird Spiel (Pädagogik), Spielpädagogik, Spieldidaktik, Spielen im Dienste der Bildungsförderung Lernspiel, ein Spiel, das zur Vermittlung von Wissen oder Fertigkeiten eingesetzt …   Deutsch Wikipedia

  • Spiel des Wissens — Daten zum Spiel Verlag I.Q. 2000 Products, Playtoy Industries, Milton Bradley (1984), University Games (1995), Jumbo (1998, 2000, 2007) Erscheinungsjahr 1984, 1995, 1998, 2000, 2007 Art Brettspiel Mitspieler 2 bis 6 …   Deutsch Wikipedia

  • Spiel des Lebens (Spiel) — Spiel des Lebens Daten zum Spiel Autor Milton Bradley (1860), Reuben Klamer (1960) Verlag MB Spiele, Hasbro Erscheinungsjahr …   Deutsch Wikipedia

  • Spiel im Morgengrauen — ist eine Novelle Arthur Schnitzlers von 1926/27. Inhaltsverzeichnis 1 Inhaltsangabe 2 Interpretation 2.1 Formales 2.2 Eros und Thanatos …   Deutsch Wikipedia

  • Spiel des Lebens (Brettspiel) — Spiel des Lebens Daten zum Spiel Autor Milton Bradley (1860), Reuben Klamer (1960) Verlag MB Spiele, Hasbro Erscheinungsjahr 18 …   Deutsch Wikipedia

  • Spiel (Drama) — Spiel ist ein Drama von Samuel Beckett. Es wurde zwischen 1962 und 1963 geschrieben. Die Uraufführung war in deutscher Sprache am 14. Juni 1963 am Ulmer Theater in Ulm. Die englischsprachige Premiere wurde 1964 am Old Vic in London unter dem… …   Deutsch Wikipedia

  • Spiel Gut — Das Prädikat „spiel gut“ wird vom Arbeitsausschuss Kinderspiel und Spielzeug e.V. für besonderes Spielzeug verliehen. Dabei entscheidet ein ehrenamtliches und von Spielwarenindustrie und Spielwarenhandel unabhängiges Gremium aus Pädagogen,… …   Deutsch Wikipedia

  • Spiel gut — Das Prädikat „spiel gut“ wird vom Arbeitsausschuss Kinderspiel und Spielzeug e.V. für besonderes Spielzeug verliehen. Dabei entscheidet ein ehrenamtliches und von Spielwarenindustrie und Spielwarenhandel unabhängiges Gremium aus Pädagogen,… …   Deutsch Wikipedia

  • Spiel mit dem Feuer — bezeichnet: Spiel mit dem Feuer (1934), einen Film von Ralph Arthur Roberts aus dem Jahr 1934 Spiel mit dem Feuer (1935), einen Film von Erle C. Kenton aus dem Jahr 1935 Spiel mit dem Feuer (1957), einen Film von Robert Parrish aus dem Jahr 1957… …   Deutsch Wikipedia

  • Spiel nicht mit den Schmuddelkindern — Studioalbum von Franz Josef Degenhardt Veröffentlichung 1965 Label Polydor …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”