6
$\begingroup$

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 ?

$\endgroup$
6
$\begingroup$

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.)

$\endgroup$
11
  • 4
    $\begingroup$ 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." $\endgroup$ Jun 20 '17 at 21:09
  • $\begingroup$ @AndreasBlass Yup, just made an equivalent edit. But I love EF-games so much! $\endgroup$ Jun 20 '17 at 21:09
  • $\begingroup$ 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") $\endgroup$ Jun 20 '17 at 21:11
  • $\begingroup$ @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}$). $\endgroup$ Jun 20 '17 at 21:12
  • 1
    $\begingroup$ @DanielWainfleet True, but what does that have to do with anything here? $\endgroup$ Jun 20 '17 at 23:03

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.