1
$\begingroup$

I was reading up on Ehrenfeucht-Fraïssé and came by this example at http://www.math.cornell.edu/~mec/Summer2009/Raluca/lesson3.html

enter image description here

Shouldn't there be a line between b4 and b2 (or b3 and b1), otherwise I don't see how the duplicator has a winning strategy in 3 rounds. Is this a mistake or ami I missing something?

thank you.

$\endgroup$

1 Answer 1

4
$\begingroup$

Spoiler wins the $3$-move EF game by picking $a_1$, $a_2$, $a_3$ in any order. You can confirm this by observing that there is a formula of quantifier rank at most $3$ that is satisfied by $A$ but not by $B$, namely:

$$ \exists x\exists y\exists z \ .\ x\neq y \wedge y \neq z \wedge z \neq x \wedge r(x, y) \wedge r (y, z) \wedge r(z, x) $$

where $r$ is the adjacency relation. Since $A$ has $3$ vertices and $B$ has $4$, Spoiler will also win any $k$-move game for $k\ge 4$, probably the question meant to ask about the $2$ and $3$-move games respectively, instead.

$\endgroup$
1
  • 1
    $\begingroup$ But spoiler also wins the 2-round game by picking $b_1$ and $b_3$, in any order. $\endgroup$ Commented Mar 1, 2019 at 0:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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