4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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)$. $\endgroup$ – Alex Kruckman Sep 17 '19 at 16:27

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.