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
add comment

3 Answers

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
add comment

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
add comment

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
add comment

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.