I know this is true:
If $T$ is an $\mathcal{L}$-theory and it admits quantifier elimination in $\mathcal{L}(c)=\mathcal{L}\cup\{c\}$, where $c$ is a constant symbol not in $\mathcal{L}$, then $T$ admits quantifier elimination in $\mathcal{L}$.
Is the converse true. That is if $T$ admits QE in $\mathcal{L}$, does it admit QE in $\mathcal{L}(c)$? Intuitively, I feel like the answer should be yes, but I'm not sure.
From Marker's book, we have the following proposition:
Let $T$ be a language with at least one constant symbol, then $T$ admits QE iff for any two models $\mathcal{A},\mathcal{B}$ of $T$ with a common substructure $\mathcal{C}$, we have that for all $L$-formulas $\phi$, and $x\in C^n$, where $C$ is the underlying set of $\mathcal{C}$, we have that $\mathcal{A}\vDash\phi(x)\text{ iff }\mathcal{B}\vDash\phi(x)$.
I was going to try and use this to prove the converse. That is, suppose we do not have QE. Then it is not the case that the other statement in the iff is true. However, I guessed it would be wiser to figure out if what I want to prove is true first, and also ask if this proposition is going to be useful for formulating a proof. So my two questions are really:
- Is the converse true?
- If it is true, would this proposition be helpful for formulating a proof (specifically by contradiction)?
Best Answer
Yes, the converse is true, and I think it's actually the easier direction.
Hint: If the $\mathcal{L}$-formula $\varphi(x,y)$ and $\psi(x,y)$ are equivalent modulo $T$, then the $\mathcal{L}(c)$-formulas $\varphi(x,c)$ and $\psi(x,c)$ are equivalent modulo $T$.
Alternatively, you can give a proof using the test for QE quoted in your question. Similarly to the hint above, the idea is to take an $\mathcal{L}(c)$-formula $\varphi(x,c)$ and consider the $\mathcal{L}$-formula $\varphi(x,y)$ obtained by replacing the constant $c$ by a variable $y$.