Counter-example of o-minimal structure but do not admit elimination of quantifiers

Question

I want a counter-example of o-minimal structure but do not admit elimination of quantifiers, we know that the inverse is true as (R,<,+,×,0,1) Tarski's theorem

Answer 1

The classic example is $\mathbb{R}_{\text{exp}} = (\mathbb{R};<,+,-,\times,0,1,e^x)$. Wilkie showed that the complete theory of this structure is o-minimal and model complete, but does not admit quantifier elimination. Formulas of the form $\exists \overline{y}\,(f(\overline{x},\overline{y},e^{\overline{x}},e^{\overline{y}}) = 0)$, where $f$ is a polynomial with integer coefficients, are typically not equivalent to quantifier-free formulas. See Wilkie's Theorem on Wikipedia and the references linked there for more information.

---

This example, while natural, is not so elementary. Much more trivially, we can expand the real field by new relation symbols which are definable with parameters in $\mathbb{R}$, and hence do not break o-minimality, but which do break quantifier elimination.

For example, consider the structure $(\mathbb{R};<,+,-,\times,0,1,P)$, where $P$ is a binary relation which holds only of the single point $(\alpha,\beta)$, where $\alpha$ and $\beta$ are algebraically independent transcendental real numbers. Since $P$ is definable with parameters in the real field (by $x = \alpha\land y = \beta$), any formula with parameters in the expanded language is equivalent to a formula with parameters in the field language, so the expanded structure is o-minimal.

Now I claim that the formula $\exists y\,P(x,y)$, which defines the singleton $\{\alpha\}$, is not equivalent to any quantifier-free formula $\theta(x)$. Note that any atomic formula in a single variable $x$ which uses the relation symbol $P$ has the form $P(t(x),t'(x))$, where $t$ and $t'$ are terms in the language of fields (i.e., polynomials with integer coefficients). Since $\alpha$ and $\beta$ are algebraically independent and transcendental, there is no real number $\gamma$ and terms $t$ and $t'$ such that $t(\gamma) = \alpha$ and $t'(\gamma) = \beta$. Thus every atomic formula of the form $P(t(x),t'(x))$ defines the empty set in $\mathbb{R}$. So every quantifier-free formula in the single variable $x$ in the expanded language is equivalent to a quantifier-free formula in the language of ordered fields, by replacing instances of $P(t(x),t'(x))$ by $x\neq x$. Finally, note that since $\alpha$ is transcendental, the set $\{\alpha\}$ is not definable by a quantifier-free formula in the language of ordered fields (the definable elements in $\mathbb{R}$ are exactly the algebraic real numbers $\overline{\mathbb{Q}}\cap \mathbb{R}$).