Can every theory $T$ be expanded to a theory with quantifier elimination in the same language?

114 Views Asked by At

Consider a theory $T$ in a language $L$. there are several examples of theories which expand to theories in the same language which admit quantifier elimination: ring theory to $ACF_0$, Boolean algebras to Boolean algebras without atoms, etc. .

Now is this true in general? I know that this is true if we expand the language, but what if we want to fix $L$?

Up to now I have found no counter-examples to this.

Thank you in advance for any help.

2

There are 2 best solutions below

2
On

No - there are theories $T$ with a formula $\varphi(x)$ such that for every quantifier-free $\psi(x)$, $T$ proves $$\exists x(\neg(\varphi(x)\iff\psi(x)).$$ For a natural example, PA does this: take $\varphi(x)$ to be the sentence saying that $x$ is in the Halting Problem. (PA knows that each quantifier-free formula defines a computable set, and that the Halting Problem isn't computable.)

0
On

Well, if $T$ is complete, then there's no nontrivial way to expand it, so any complete theory without quantifier elimination is a counterexample. Complete theories which have quantifier elimination are quite rare, so almost any complete theory will do. For a very simple example, the complete theory of $(\mathbb{Z},+)$ does not have quantifier elimination (for instance, $\exists y(y+y=x)$ is not equivalent to any quantifier-free formula).