2
$\begingroup$

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?

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

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$.

Here's the winning strategy for Player I in your example.

  • 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.
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – StefanH May 9 '18 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.