# $\Sigma_{(\mathbb{N},<)}$ does not admit elimination of quantifiers

I'm beginning to study mathematical logic from a sort of book my professor wrote for his classes, and when talking about the theory of natural numbers with the ordering, i.e. the structure $$(\mathbb{N},<)$$, it says that the theory $$\Sigma_{(\mathbb{N},<)}$$ admits elimination of quantifiers. But I think that this is not true.

Later it says that actually the theory that admits elimination of quantifiers is the theory $$\Sigma_{(\mathbb{N},0,<)}$$, so I'm prone to think that the first statement is just a misprint. So I was wondering how to prove formally that the theory $$\Sigma_{(\mathbb{N},<)}$$ does not admit elimination of quantifiers, and I came up with this kind of reasoning:

Consider the standard model $$(\mathbb{N},<)$$ and the formula: $$\phi(x) = \lnot\exists z(z < x)$$. Its truth set is $$T^\mathbb{N}_{\phi(x)} = \{0\}$$ If the theory $$\Sigma_{(\mathbb{N},<)}$$ were to admit elimination of quantifiers then every formula, including $$\phi$$, should be preserved under embeddings. But if we consider the embedding $$f: x \mapsto x+1$$, it is evident that $$T^\mathbb{N}_{\phi(x)}$$ is not closed under $$f$$, hence the contradiction. Am I wrong?

Your argument is correct. More directly, you can just observe that any quantifier-free formula is a Boolean combination of atomic formulas, and the only atomic formulas in one variable are $$x and $$x=x$$. Both of these are either true for all $$x$$ or false for all $$x$$, and so every quantifier-free formula in one variable is either true or false for all $$x$$.
Also, it is not correct that $$\Sigma_{(\mathbb{N},0,<)}$$ has quantifier elimination either. For instance, the set $$\{1\}$$ can be defined by $$x>0\wedge\neg\exists z(z but cannot be defined by any quantifier-free formula. To get quantifier elimination you need to also add a function symbol $$s$$ which takes each element to its successor.
• An alternative to adding the successor function $s$ is to add a family of "distance predicates" $(D_n)_{n>0}$, where the interpretation of $D_n(x,y)$ is "$x<y$ and there are exactly $(n-1)$ elements between $x$ and $y$ in the order". For example, $\{1\}$ is now definable by $D_1(0,x)$. – Alex Kruckman Sep 17 '19 at 16:27