Ehrenfeucht–Fraïssé game

Definition

Let $L$ be a relational signature, that is, a signature with relation symbols and constant symbols but no function symbols. Let $\mathcal{A}$ and $\mathcal{B}$ be $L$-structures with domains $A$ and $B$, and let $n \ge 0$ be an integer. The Ehrenfeucht–Fraïssé game $G_n(\mathcal{A}, \mathcal{B})$ is played by two players, Spoiler and Duplicator, in $n$ rounds.

1. In round $i$, Spoiler chooses one of the two structures and an element of it.
2. Duplicator then chooses an element of the other structure.
3. After round $i$, let $a_i \in A$ and $b_i \in B$ be the two elements chosen in that round.

Consider the correspondence $c^{\mathcal{A}} \mapsto c^{\mathcal{B}}$ for the constant symbols $c$, together with $a_i \mapsto b_i$ for $i = 1, \dots, n$. Duplicator wins the play when it is a well-defined injective map that preserves and reflects each relation of $L$. That is, it is an isomorphism between the substructures generated by the chosen elements and the constants. Otherwise Spoiler wins. Duplicator has a winning strategy when Duplicator has a rule for choosing moves that wins every play, whatever Spoiler does.