Let $\mathfrak{A} = \langle A, \dots \rangle$ and $\mathfrak{B} = \langle B, \dots \rangle$ be structures for a signature $\mathscr{L}$. For each ordinal $\gamma$ we define a game of perfect information between two players, Spoiler and Duplicator:

For each $\xi < \gamma$ Spoiler picks an element from $A$ or $B$, and Duplicator responds with an element from the other set. Together they determine a pair $(a_{\xi}, b_{\xi})$ in $A \times B$. After $\gamma$ rounds, Duplicator wins if there is an isomorphism, carrying each $a_{\xi}$ to $b_{\xi}$, from the substructure of $\mathfrak{A}$ generated by the $a_{\xi}$ sequence to the substructure of $\mathfrak{B}$ generated by the $b_{\xi}$ sequence. Else Spoiler wins.

This is the *Ehrenfeucht-Fraïssé game* $G_{\gamma}(\mathfrak{A},\mathfrak{B})$ of length $\gamma$ on $(\mathfrak{A}, \mathfrak{B})$. Note, as François did in the comments, that in some contexts this term designates a different game.

If $\mathfrak{A}$ and $\mathfrak{B}$ are isomorphic, then clearly Duplicator can win the game for any $\gamma$. Moreover, if $\mathfrak{A}$ and $\mathfrak{B}$ are finite or countable, then they are isomorphic iff Duplicator has a winning strategy for $G_{\omega}(\mathfrak{A},\mathfrak{B})$. Such games may therefore be used toward establishing isomorphisms.

Ehrenfeucht-Fraïssé games can also show that a structural property isn't expressible in a first order language. Given a class $K$ of finite structures for a relational signature $\mathscr{L}$, to show that there is no first order $\mathscr{L}$ theory $\Gamma$ whose class of finite models is precisely $K$, it suffices to show that for each $n$ there are $\mathscr{L}$ structures $\mathfrak{A}_n \in K$ and $\mathfrak{B}_n \in \neg K$ such that Duplicator can win $G_n(\mathfrak{A}_n,\mathfrak{B}_n)$. This is because if Duplicator can win, then $\mathfrak{A}_n$ and $\mathfrak{B}_n$ verify the same sentences of quantifier rank $\leq n$. (I forget whether this works when $\mathscr{L}$ has function symbols.)

What are some lesser known uses for these games, or for minor variations on them? I have a special interest in models of set theory.

5more comments