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?
Best Answer
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<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<x\wedge \neg z=0)$ 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.