Ehrenfeucht-Fraïssé-Spiel

Das Spiel ${\mathfrak{G}}_m(\mathcal{A},\mathcal{B})$ wird über $m$ Runden gespielt.

• Spieler: Herausforderer (H) und Duplikatorin (D).
• Zug: In Runde $i$ wählt H ein Element aus einer der beiden Strukturen (z.B. $a_i\in A$). D muss mit einem Element aus der anderen Struktur antworten (z.B. $b_i\in B$).
• Gewinnbedingung: Nach $m$ Runden haben wir Paare $(a_1,b_1),\dots ,(a_m,b_m)$. D gewinnt, wenn die Abbildung $a_i\mapsto b_i$ ein Partieller Isomorphismus ist.
• Intuition: D gewinnt, wenn die ausgewählten Unterstrukturen "gleich aussehen".