## EF games and FO logic: Winning Strategies

If we take a closer look at lesson #3, we see that winning strategies for the Ehrenfeucht-Fraïssé games translate
naturally into first order logic.

In lesson #3, we described a winning strategy for the Spoiler as follows:

- There is a possible move for the Spoiler such that

forall possible answer moves of the Duplicator

there is a possible move for the Spoiler such that

forall possible answer moves of the Duplicator

...

after n rounds, the Spoiler wins

This translates into saying that:

- There exists a node in the graph A (that the Spoiler will choose as part of his winning strategy) such that

forall nodes in B (that is for any node that the Duplicator might choose in response)

there exists another node in A/B (that the Spoiler will choose) such that

forall nodes in B/A(that the Duplicator might choose)

......

some FO sentence with quantifier rank n becomes true on A, and false on B, or viceversa.

## Example 1:

Instead of trying to guess appropriate moves for the Spoiler, let us first look
at the two graphs and try to identify a property (expressible in first oreder logic)
that only one of the graphs has. At first glance we notice that in the graph B there is one node with no outgoing edges,
namely b_{4}, whereas in the graph A, all nodes have one outgoing edge.
So we can formulate the property that distinguishes between the two graphs by:

This yelds a strategy for the Spoiler to win the EF game on A, B after 2 rounds.
The spoiler picks b_{4} in the first round. After the Duplicator has picked some node a_{i} in the graph A,
the Spoiler picks the node a_{k} in A for which E(a_{i}, a_{k}) is true. Spoiler wins, because
Duplicator is unable to pick a node b_{*} in B for which E(b_{4}, b_{*}) is true. So the Duplicator
is unable to respond in a way in which the partial isomorphism in maintained.

It is worth mentioning that the observation above is actually a theorem.

**Theorem (Ehrenfeucht,Fraïssé):** Let A, B be two graphs. The following statements are equivalent:

- A and B satisfy the same first-order sentences of quantifier rank n.
- A~
_{n}B, i.e. the Duplicator wins the n-move Ehrenfeucht-Fraïssé game on A and B

## Example 2

Consider the graph depicted below. Show that:

- A~
_{2}B, i.e. the Duplicator wins the 2-move EF game on A,B
- The Spoiler wins the 3-move EF game on A,B

a. The Duplicator can win in such a way that there is an edge between x_{1} and x_{2} if and
only if there is an edge between y_{1} and y_{2}, where x_{1} ,y_{1},
x_{2} ,y_{2} represent the nodes chosen in the first 2 rounds. Hence {x_{1},x_{2}}
and {y_{1},y_{2}} will be partially isomorphic.

b. In contrast, the Spoiler can win the 3-move game by picking three elements in B with no edge between them.
A first order sentence of quantifier rank 3 that captures this difference is:

The Spoiler wins by picking 3 nodes b

_{i}, b

_{j} and b

_{k} from B for which the following
proposition is true:

**Exercise:** Find a different FO sentence of quantifier rank 3 that witnesses the difference between A and B.
Use it to formulate a different strategy for the Spoiler to win the 3-move EF game on A and B.