The theory of discrete endless orders is complete

In an answer to another question, Joel David Hamkins claims that the theory of endless discrete orders is complete. He suggested I ask this as a separate question so here I am : how do you prove this claim ?

Clearly the examples he gives show that this theory is not $\aleph_0$-categorical ($\Bbb{Z}$ and $\Bbb{Z}+\Bbb{Z}$ are not isomorphic. To see this, notice that any subset of $\Bbb{Z}$ that is bounded from below is well-ordered, whereas it's not the case for $\Bbb{Z}+\Bbb{Z}$ - I don't know if there's an easier proof).

I suspect that this theory isn't $\lambda$-categorical for any infinite cardinal $\lambda$ (although I'm not able to prove it), so I think that I can't use this method to prove completeness.

I know there are other ways to show completeness such as quantifier-elimination but I am not well aware of these and lack practice so I can't hope to prove it that way (but if you can show me, I would gladly have an answer using quantifier elimination).

So on a side note: what methods are there to prove that a certain theory is complete ?

You're quite right that this theory is not $\kappa$-categorical for any $\kappa$: consider the linear orders $\mathbb{Z}\cdot \kappa$ versus $\mathbb{Z}\cdot(\mathbb{Q}+\kappa)$, each of which is discrete and of size $\kappa$.

As to showing elementary equivalence, note that quantifier elimination won't work here: e.g. the formula "$\exists x\forall y(a<x<b$ but $a<y<b\implies x=y)$," that is, $a$ and $b$ are separated by exactly one point. This formula is not equivalent to any quantifier-free one.

Instead, the right tool to use here is Ehrenfeucht-Fraisse games. It's not too hard to come up with a winning strategy for Duplicator in the game $G_n(\mathbb{Z}, \mathcal{M})$ whenever $\mathcal{M}$ is an endless discrete linear order and $n\in\mathbb{N}$, so they are all elementarily equivalent to $\mathbb{Z}$ (and hence to each other). The key observation is that, in the length-$n$ game, two points that are more than $2^n$(ish) apart "might as well" be infinitely far apart; play with the game a bit and you'll see what I mean.

Incidentally, this argument will show that any formula is equivalent, over this theory, to a Boolean conjunction of $\Sigma_2$ formulas (amongst these are those sentences of the form "The distance between $a$ and $b$ is exactly $n$" for $n\in\mathbb{N}$. So there is a weak form of quantifier elimination here, it's just more complicated than those we usually deal with (quantifier-free and $\Sigma_1$).

This does, however, give a quantifier-elimination route towards solving the problem: adding predicates saying "are exactly $n$ distance apart" to the language, the resulting theory eliminates quantifiers. (Another place where we use this trick is in showing the decidability of Presburger arithmetic.)

• Although the theory itself doesn't admit quantifier elimination, I think an extension by definitions does: Introduce new predicates $P_n$ where $P_n(x,y)$ means "$x<y$ with exactly $n$ other elements between them." Jun 20 '17 at 21:09
• @AndreasBlass Yup, just made an equivalent edit. But I love EF-games so much! Jun 20 '17 at 21:09
• How do you order the products ? I assume it's the same as for ordinals (that is the product such that $\omega = 2\cdot \omega \neq \omega\cdot 2$). If so, how do you show that the orders you mention aren't isomorphic ? As for the Ehrenfeucht-Fraïssé game, thank you for mentioning that other technique, I'll have a look at it (I think I understand what you mean by "they might as well be infinitely far apart") Jun 20 '17 at 21:11
• @Max Same as linear orders - "$A\cdot B$" means "replace each element of $B$ with a copy of $A$." To see that they're not isomorphic, note that the former has no descending transfinite sequences of length $\omega^2$ (since otherwise taking the element of $\kappa$ corresponding to the $(\omega\cdot n)$th element of the sequence yields a descending sequence in $\kappa$) while the latter does (since it contains a copy of $\mathbb{Z}\cdot \mathbb{N}^*$ by embedding $\mathbb{N}^*$ in $\mathbb{Q}$). Jun 20 '17 at 21:12
• @DanielWainfleet True, but what does that have to do with anything here? Jun 20 '17 at 23:03