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?


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.

  • $\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 May 9 '18 at 8: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.