# Ehrenfeucht-Fraisse games over finite sequences (i.e. words) and separability by first order formulas

Lets given a finite set (called an alphabet) $\Sigma$ and consider the set of first order formulas with atomic formulas $$= , \quad < , \quad R_a \quad (a \in \Sigma).$$ For a given word $w \in \Sigma^{\ast}$ (i.e. a sequence with letters from $\Sigma$), the interpretation is as follows: We set $\mbox{Dom}(w) = \{1,\ldots, |w|\}$ and $R_a := \{ i \in \mbox{Dom}(w) \mid w_i = a \}$, and $=, <$ are interpreted as usual. Hence the variables are the positions in the word, and the predicates are for determining what letter we have at a specific position.

Example: Let $w = ababa$ with $\Sigma = \{a,b\}$. Then $\mbox{Dom}(w) = \{1,2,3,4,5\}$ and $R_a = \{1,3,5\}$, $R_b = \{2,4\}$. Hence the sentence $$\forall x ( R_b(x) \rightarrow \exists y ( R_a(y) \land y > x ) )$$ is satisfied by $w$, whereas $\forall x ( R_a(x) )$ is not satisfied.

An Ehrenfeucht-Fraisse-Game between two Players Player I and Player II on two words $u, v$ with $p \ge 0$ turns is played according to the following rules: Player I starts, he chooses some word and marks an arbitrary position in it, then Player II takes turn and marks a position in the other word. This procedure goes on for $p$ turn, after which both players have marked $p$ position (where a position could be marked multiple times).

The markings are then interpreted as assignments of positions to variables $x_1, x_2, \ldots, x_p$ for the word choosen by each player. For example, if we have $u = ab, v = baa$, Player I chooses $v$ and marks the first $a$, then Player II marks the first $a$ in $u$, then Player I marks the second $a$ in $v$ and then Player I the first $a$ in $u$, we have for $u$ the variable assignment $x_1 = x_2 = 1$ and for $v$ we have $x_1 = 2, x_2 = 3$.

Player II wins, iff with this assignment, every atomic formula over $\{x_1, \ldots, x_p\}$ which is true for $u$ is also true for $v$ and vice versa.

In the above example, Player I wins, as the formula $x_1 < x_2$ is true on $v$ but not on $u$ with the given assignments (but $R_a(x_1), R_a(x_2)$ are both true).

Now, a fundamental theorem for such Ehrenfeucht-Fraisse-Games is:

Player II has a winning strategy in the above given with $p$ turns iff no formula with $p$ variables and quantifier depth at most $p$ distinguishes both words.

So, for example consider $$u = ababab, \quad v = bababa.$$ Then the first order formula $$\exists x \forall y ( ( x < y \lor x = y ) \land R_a(x) )$$ is true on $u$, but not on $v$, hence a formula of quantifier depth two can "separate" both words. But I can find no winning way for Player I with two turns. More, I think this is not possible, i.e. Player II has a winning strategy. For by symmetry suppose Player I chooses $u$ and marks some position with symbol $x \in \{a,b\}$. Then Player II chooses a position in the middle of $v$ with the same symbol $x$. Then its Player I's turn again, and if he chooses a position greater than the previously choosen one, Player II is free to choose one that is greater too with the same symbol, and if Player I choose a smaller position Player II can react in the same way (same if Player I chooses the same position in the second turn). Hence after two moves all formulas of the form $x_1 < x_2$, $R_a(x_2)$ etc are fullfilled on both words? So, this contradicts the fundamental theorem about Ehrenfeucht-Fraisse-Games.

What am I missing, does anybody sees where my reasoning breaks down?

• In your first example, that sentence is not satisfied. Did you mean to switch $R_a$ and $R_b$? – Alex Kruckman May 9 '18 at 12:57
• @AlexKruckman Yes, thank you! I accidently switched $R_a$ and $R_b$! – StefanH May 9 '18 at 13:02

What you're missing is that Player I can play in different structures on different turns. In fact, in general, if a sentence $\varphi$ separates structures $M$ and $N$, each alternation of quantifier type in $\varphi$ corresponds to a switch of which structure Player I plays in, in the winning strategy corresponding to $\varphi$.
• Player I plays (as $x$) the least element of $u$, so we have $R_a(x)$.
• If Player II plays (as $x$) an element of $v$ labeled by $b$, she loses. So we may assume she plays some element labeled by $a$. This means that she does not play the least element of $v$.
• Player I plays (as $y$) the least element of $v$. So we have $y<x$.
• Now Player II must play (as $y$) some element of $u$ such that $y<x$. But there is no such $y$ in $u$, since $x$ is the least element.
• Oh, yes! I somehow thought both players must stick to their initial choice. The examples in my book do exactly that, so I had not considered the idea that the words could be choosen anew at each turn by Player I. And yes, I somehow had the feeling that the alternation (here switching to an $\forall$ is where the problem is) and the proofs really puzzled me as they just handled the case of $\exists$. But now, yes by switching structures this is all fine, also with the negation. – StefanH May 9 '18 at 13:30