4
$\begingroup$

In Libkin's "Elements on finite model theory" Theorem 3.6 states the following: Let $k > 0$, and let $L_1,L_2$ be linear orders of length at least $2^k$ then $L_1\equiv_k L_2$---where $\equiv_k$ means that the duplicator wins a $k$-move Ehrenfeucht-Fraïssé game.

To motivate the theorem it is preceded by the example of linear orders $L_1, L_2$ with $|L_1|=3$ and $|L_2|$ and $k=2$ such that $\equiv_k$ fails.

Looking at $k=2$ and $k=3$ I don't see why the length of $L_1$ and $L_2$ has to be at least $2^k$. Can't it be less?

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

It can indeed be less. For example, it's easy to show (and I suspect you noticed this) that $[3]\equiv_2[4]$ (where $[n]$ denotes the linear order with $n$ elements). There is no claim in the text that Theorem $3.6$ is optimal; the point is that that lower bound has a particularly intuitive proof.

$\endgroup$
1
  • $\begingroup$ Thanks for your answer! The proof, which I have not studied yet, seems rather involved. That's why I thought the bound might be optimal. I noticed $[3]\equiv_2[4]$. Then I found $[7]\equiv_3[8]$ and $[7]not\equiv_3[8]$ with the optimal 7 not being much smaller than $2^3$ of the theorem. $\endgroup$
    – Joel Adler
    Commented May 9, 2018 at 8:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .