Logic: quantifier-elimination and completeness

537 Views Asked by At

Suppose $T$ is an $L$-theory that has quantifier-elimination. Let $M$ be a $T$-model and $\Delta$ the set of all quantifier-free $L$-sentences that are true in $M$. Define $T'$:=$T$$\cup$$\Delta$. Now prove that $T'$ is a complete theory.

Is the following arguing correct?

Any two models $M,N$ ($M$ $\subset$ $N$) of $T'$ satisfy the same sentences ($T$ admits quantifier elimination and every sentence in $\Delta$ is a quantifier free sentence) and in this way $T'$ is a complete theory?

1

There are 1 best solutions below

2
On BEST ANSWER

I think you have the right idea, but let's try to fill in the details a bit: Let $\phi$ be an $L$-sentence, we will prove that $T'\vdash \phi$ or $T'\vdash \neg \phi$. Since $T$ has quantifier elimination, there is a quantifier free sentence $\psi$ such that $T\vdash (\psi \leftrightarrow \phi)$. Since $T\subseteq T'$ it follows that $T'\vdash (\psi \leftrightarrow \phi)$. Now $M$ is a model, so either $M\models \psi$ or $M\models \neg \psi$. WLOG assume the former, then $\psi \in \Delta \subseteq T'$ and hence $T'\vdash \psi$. From $T'\vdash (\psi \leftrightarrow \phi)$ and $T'\vdash \psi$ we may conclude $T'\vdash \phi$.
Depending on your definition of "complete theory" you may also need to prove that $T'$ is consistent.

Hint: If $T'$ is inconsistent, then by compactness there is a sentence $\psi \in \Delta$ ($\Delta$ is closed under taking conjunctions) such that $T\vdash \neg \psi$.