Does every complete theory admit quantifier elimination? I know that at least in some simple cases the reverse is true; such as some reducts of number theory.Thanks


In another post I've given an example of how the theory of real closed fields in the language $(0,1,+,\cdot)$ does not have q.e. (even though it is model complete).

As for the other question, using the characterization of q.e. by substructural completeness (which I have, again, explained in that post) you can see that if a theory has q.e. AND has a constant symbol AND decides all quantifier-free sentences (that is, formulas without variables), then it is complete (which probably covers your reducts of number theory, as they would likely have a symbol for $0$ or $1$).

Without constants it need not be true. Consider the language $\{P\}$ with one unary predicate, and the theory which says that the model is infinite and that all its elements agree on $P$. It clearly isn't complete, but has q.e. (which is easy to check directly, or by substructural completeness).

  • 1
    $\begingroup$ I know this is quite an old question, but I just stumbled upon it, and I have some comments on this answer. I don't think the theory in the last paragraph eliminates quantifiers: Specifically, it doesn't prove that $\exists x\, P(x)$ is equivalent to a quantifier-free sentence. Now you might argue that full quantifier elimination doesn't make sense in a language without constant symbols, since there are no quantifier-free sentences. This is one reason why we should include the symbol $\top$ (always true) in our basic logical language. But how can this theory be substructurally complete if it $\endgroup$ – Alex Kruckman Apr 21 '14 at 17:43
  • 1
    $\begingroup$ ...doesn't eliminate quantifiers? Answer: It's not substructurally complete if we admit the empty structure. These things might be a bit pedantic, but in conclusion: q.e. should be defined for all formulas, including sentences. For the definition to make sense, we must include ⊤. For the equivalence with substructural completeness to hold, we must admit empty structures (of course, there are many other good reasons to to do this!). $\endgroup$ – Alex Kruckman Apr 21 '14 at 17:51
  • $\begingroup$ @AlexKruckman: $\exists x P(x)$ is equivalent to $\forall x P(x)$ (at least according to the usual conventions I abide by, in particular, that structures are not empty ;) ), which is equivalent to just $P(x)$. $\endgroup$ – tomasz Apr 21 '14 at 22:44
  • $\begingroup$ @AlexKruckman: not admitting empty structures has the added benefit of having "true" equivalent to the (quantifier-free) formula $x=x$. $\endgroup$ – tomasz Apr 21 '14 at 22:54
  • $\begingroup$ Yes, but q.e. says that a formula $\phi(\overline{x})$ is equivalent to a quantifier-free formula $\psi(\overline{x})$ in the same variable context. So $\exists x P(x)$ should be equivalent to a quantifier-free sentence. $P(x)$ is not one. The point of having "true" is that it doesn't need a dummy variable context. $\endgroup$ – Alex Kruckman Apr 22 '14 at 0:55

No, not every complete theory has quantifier elimination.

Take $\mathcal{L} = \{U\}$ where $U$ is a unary function symbol. And take the structure $\mathbf{N} = (\mathbb{N}, S)$ where $S$ is the successor function.

Then of course $\operatorname{Th}(\mathbf{N})$ is complete. But the only atomic formulas in one variable are of the form $S^n(x) = S^m(x)$ for some $n,m \in\mathbb{N}$. And because $S$ is one to one this is the same as $S^k(x) = x$ for some $k \in\mathbb{N}$.

For $k = 0$ this defines $\mathbb{N}$ and for $k \geq 1$ this defines $\varnothing$.

Thus every quanitifer free formula in one variable defines either $\mathbb{N}$ or $\varnothing$.

However, the set $\{0\}$ is definable in one free variable by $\forall y S(y) \neq x$.

So $\operatorname{Th}(\mathbf{N})$ cannot have quantifier elimination.


Let $G=(V,E)$ be a countable graph such that there exists a point $a\in{V}$ such that for all $b\in{V}$, $(a,b)\notin{E}$ and $E\neq{\emptyset}$.

Let $L=\{R\}$, where $R$ is a binary relation. Let $\mathcal{M}$ be the model of $G$ in the language $L$. Put $T=Th(\mathcal{M}),$ we claim that $T$ has no quantifier elimination.

Suppose this is not so, then all maps $f:N\rightarrow M$ such that $N$ is a finite subset of $M$; and thus a substructure of $\mathcal M$ as $L$ is a relational language, and $f:N\rightarrow Im(f)$ is an isomorphim, are elementary embeddings into $\mathcal M$.

But as $E\neq\emptyset$, there are $b,c\in V$ such that $(b,c)\in E$, then the map $f=\{(a,b)\}$ is an isomorphism between the substructures $\{a\}$ and $\{b\}$, however $f:\{a\}\rightarrow M$ is not elementary.


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.