---
tag: 1DVRN1T2Z0
kind: definition
name: Ehrenfeucht–Fraïssé game
msc: [03C07, 03C13]
defines: 2RE7YAZK8R
uses: [983GZBQYT4, 676H7EGTKJ, WDVVEYD6AT]
sources:
  - url: https://en.wikipedia.org/wiki/Ehrenfeucht–Fraïssé_game
---

## Definition

Let $L$ be a relational [[signature|WDVVEYD6AT]], that is, a signature with relation symbols and constant symbols but no function symbols.
Let $\mathcal{A}$ and $\mathcal{B}$ be $L$-[[structures|983GZBQYT4]] 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|676H7EGTKJ]] 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.

## Remarks

Example: let $\mathcal{A} = (\set{1, 2, 3}, <)$ and $\mathcal{B} = (\set{1, 2, 3, 4}, <)$.
Duplicator has a winning strategy in $G_2(\mathcal{A}, \mathcal{B})$.
In the first round, Duplicator answers the least element by the least, the greatest by the greatest, and an inner element by an inner element.
In the second round, an element below, equal to or above the first chosen element can then be matched on the other side.

Non-example: Duplicator has no winning strategy in $G_2((\Q, <), (\set{1, 2}, <))$.
Spoiler first picks $2$ in $\set{1, 2}$, and Duplicator answers some $q \in \Q$.
Spoiler then picks $q + 1$ in $\Q$, and no element of $\set{1, 2}$ lies above $2$.

Let $L$ be finite.
The theorem of Ehrenfeucht and Fraïssé says: Duplicator wins $G_n(\mathcal{A}, \mathcal{B})$ if and only if $\mathcal{A}$ and $\mathcal{B}$ satisfy the same sentences of quantifier depth at most $n$.
Hence $\mathcal{A} \equiv \mathcal{B}$ when Duplicator wins $G_n$ for every $n$.

## Explanations

### L1 human

The game turns the question "can first-order logic tell these two structures apart?" into a contest.
Each round of the game matches one quantifier of a sentence.
A winning strategy for Duplicator in $n$ rounds proves that no sentence with $n$ nested quantifiers separates the structures.