Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 1 down vote accepted

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).

share|improve this answer
    
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 –  Alex Kruckman Apr 21 at 17:43
    
...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!). –  Alex Kruckman Apr 21 at 17:51
    
@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)$. –  tomasz Apr 21 at 22:44
    
@AlexKruckman: not admitting empty structures has the added benefit of having "true" equivalent to the (quantifier-free) formula $x=x$. –  tomasz Apr 21 at 22:54
    
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. –  Alex Kruckman Apr 22 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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.