13
$\begingroup$

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

3 Answers 3

1

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
    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 it2014-04-21
  • 1
    ...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!).2014-04-21
  • 0
    @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)$.2014-04-21
  • 0
    @AlexKruckman: not admitting empty structures has the added benefit of having "true" equivalent to the (quantifier-free) formula $x=x$.2014-04-21
  • 0
    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.2014-04-22
  • 0
    @AlexKruckman: Not the way I was taught, it isn't. Otherwise, no theory without constant symbols would have quantifier elimination without expressly adding the "true" dummy formula variable as a quantifier-free symbol. But I fail to see how that is at all better than just allowing dummy variables.2014-04-22
  • 0
    Anyway, this all depends on how you set up your definitions, and the "right" way to do so is a matter of opinion. I just thought if register my opinion here in case someone stumbles upon this question in the future.2014-04-22
8

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.

2

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.