The example is Proposition 2.4.10 of David Marker's Model theory book.
The key claim is that $(\mathbb{Z}, <) \equiv N$, where $N:= L \times \mathbb{Z}$ , for any linear order $L$ (equiped with lexicographical ordering).
Before I proceed, I will first acknowledge that there is a similar post, Ehrenfeucht-Fraïssé games on linear orders
But I'm afraid it does not fully address my confusion.
So we obviously want to make use of Ehrenfeucht–Fraïssé game to prove this claim, there lies my first confusion: how do we set up this 'game' ?
The example later begin by defining a distance function dist(a, b) = $|b-a|$, why is this crucial ?
And finally (for those that have the book as reference), there is this 'magic number': $3^{n-m}$. How did the author came up with this ?
Sorry if my question is on the amateur side, I'm still trying to get use to this back and forth argument.
Cheers and thanks !
Best Answer
The game has two players, player A and player B and a fixed number of rounds $n$. In each round $m$ Player A will pick an element $a_m\in\mathbb Z$ or an element $b_m\in L\times\mathbb Z$, and player B will respond by picking an element from the other model. B wins if at the end of the game the tuples $(a_1,\dots,a_n)$ and $(b_1,\dots,b_n)$ are locally isomorphic. If B has a winning strategy for a game of length $n$ for any $n\in\mathbb N$, then the models can be shown to be elementary equivalent.
Note that in this specific case, a local isomorphism only has to reflect the behaviour of the order: so if $a_i<a_j$, then we also should have $b_i<b_j$.
Player A can choose which model to pick elements from. Clearly if A picks from $\mathbb Z$, then B can just mirror this pick with an element from $l\times \mathbb Z$ for some $l\in L$, so we assume A picks elements from $L\times \mathbb Z$. The problem that B faces, is that A can pick elements that are infinitely far apart, while B only can pick elements finitely far apart. This is where the distance function and the number $3^{n-m}$ comes into play: B leaves enough space to accommodate for any of the possible orders in which A could pick the remaining elements.
For example, if there are four rounds, A picks $(0,0)$; B picks $0$; A picks $(1,0)$, then there are several possibilities for the remaining rounds. If $B$ picks, for example, $3$, then he gets into trouble: A can choose $(0,100)$ next, which is in between $(0,0)$ and $(1,0)$, hence $B$ needs to pick in between $0$ and $3$. But if B picks $1$, then A can pick any element between $(0,0)$ and $(0,100)$ to win, or if $B$ picks $2$, then A can pick any element between $(0,100)$ and $(1,0)$ to win. There is not enough space in between $0$ and $3$ for B to be able to answer any pick that A makes.
By choosing numbers that are at least $3^{n-m}$ apart from their closest neighbours, B makes sure to keep enough space for the remaining $n-m$ rounds of the game. I believe actually $2^{n-m}$ should to be enough: B reflects the choice of A by playing exactly in the middle of the interval in which A picked. Since there are $2^{n-m}$ numbers in the interval for each round, B can always pick a middle number and leave intervals of at least $2^{n-m-1}$ between all of the picks to accommodate for the next round.