Show that two structures are not distinguishable in first order logic

Question

Show that two structures are not distinguishable in first order logic. It is about $\mathbb{A}=\langle \mathbb{R}\times \mathbb{Z}, \le\rangle$ and $\mathbb{B}=\langle \mathbb{Q}\times \mathbb{Z}, \le\rangle$. We can use only formula, not set of formulas. $\le$ denotes linear order, which is lexycographic.

Examples of order: $(\frac12, 5) \le (\frac12 6)$
$(\frac13, 100000) \le (\frac12, -10000)$
I don't know how to define it more precisely. $\le$ denotes lexycographic linear order. Comparing first elements of pairs we use standard $\le$ in $\mathbb{Q}$ or $\mathbb{ R}$. At the same for second element of pair: standard $\le $ on $\mathbb{Z}$

It does mean that we should show that for each $n$ these both structures duplicator has always winning strategy in $n$ rounds.

I am going to use fact that $\langle \mathbb{R},\le\rangle $ and $\langle \mathbb{Q},\le\rangle$ are not distinguishable.

Lets give strategy for duplicator:
If spoiler chose $(a, b) $ ten duplicator also chose pair of form $(\_, b)$. Thanks to this, building isomorphism duplicator must worry only about relation in the same chain. In other words, this strategy that relation between elements from different chains will be prevented.

Now, if duplicator has to only win on single chain. Lets suppose that there is no winning strategy for duplicator. However, in this situation there is no strategy for simpler game: $\langle \mathbb{R},\le\rangle $ and $\langle \mathbb{Q},\le\rangle$.
We got contradiction.

Am I ok ?

Answer 1

You seem to be using some "spoiler"/"duplicator" framework for your argument that is not common knowledge -- at least I have not heard about it before (but I'm not an expert in model theory either). So I can't say whether your argument works.

I can see a syntactic proof in the form of this general fact:

The first-order theory of total orders where every element has an immediate predecessor and an immediate successor is complete (and decidable).

Since $\mathbb A$ and $\mathbb B$ are both models of this complete theory (as is $(\mathbb Z,{\le})$), they are indistinguishable.

To prove the above fact, formulate the theory with an explicit function letter for the successor function. It then has quantifier elimination.

Namely, to eliminate the quantifier in $(\exists x)\varphi$ where $\varphi$ is quantifier-free, first rewrite $\varphi$ into disjunctive normal form, distribute the quantifier across the disjunctions, and now it is easy to eliminate it from each remaining conjunction of atoms. It is a bit tedious to handle $\neq$ atoms explicitly, but we can avoid that by rewriting $t_1\ne t_2$ to $S(t_1)\le t_2 \lor S(t_2)\le t_1$ during the DNF conversion.