# Why is the Ehrenfeucht theory complete?

I am looking at the theory T of Dense linear orders without endpoints, extended with the set $\{c_i<c_j|i\in\omega\}$ and am asked to prove that this theory is complete.

I know that it has three non-isomorphic countable models (depending on what $\lim_{n\to\infty}c_n$ is if you identify the $c_i$ with the elements of $\mathbb{Q}$), so I cannot use Tarski-Vaught.

What I think I should do is identify the sequence with $\mathbb{Q}$ regardless, since there is clearly a map from the set $\{c_i<c_j|i\in\omega\}$ into $\mathbb{Q}$ and then I can use the completeness of $\mathbb{Q}$ to show that for any $\phi$ we have $T\vDash\phi$ or $T\nvDash\phi$, by identifying the $c_i$ with $\mathbb{Q}$ but I cannot make my argument precise.

Any ideas?

• Are you both in the same class: math.stackexchange.com/questions/686126/… ? – Metin Y. Feb 22 '14 at 19:27
• @Metin Y. haha, probably! I don't see how Ehrenfeucht Fraisse games would solve anything for this question though. – user106421 Feb 22 '14 at 19:29

Use quantifier elimination in $T$. Since the language $\{<\} \cup \{c_i:i<\omega\}$ contains constants, it will follow that $T$ is complete.

To show that $T$ actually has quantifier elimination, use the following theorem (Theorem 3.2.5 in Tent-Ziegler): $T$ has quantifier elimination if and only if for all models $\mathcal M$ and $\mathcal N$ of $T$ with a common substructure $\mathcal A$ and for all primitive existential formulas $\varphi(x_1,\ldots,x_n)$ and parameters $a_1,\ldots,a_n$ from $\mathcal A$ we have $\mathcal M \models \varphi(a_1,\ldots,a_n) \Rightarrow \mathcal N \models \varphi(a_1,\ldots,a_n)$.

A primitive existential formula takes the form $\exists v \psi(v,w_1,\ldots,w_n)$ where $\psi$ is a conjunction of atomic formulas and negated atomic formulas.

If $\psi(v,w_1,\ldots,w_n) \rightarrow v=w_i$ or $\psi(v,w_1,\ldots,w_n) \rightarrow v = c_i$ for some $i$, then you can argue directly that the condition from the theorem holds. Without loss of generality, every other kind of satisfiable primitive existential formula $\exists v \psi(v,w_1,\ldots,w_n)$ takes the form

$$\exists v \bigwedge_{f(i)=0} v<w_i \wedge \bigwedge_{f(i)=1} w_i<v \wedge \bigwedge_{j \le k} c_j<w \wedge \bigwedge_{j>k} w<c_j$$

where $f$ is a convenient partition of $\{1,\ldots,n\}$. Using the fact that $T$ is the theory of dense linear orders, you can now argue that $\mathcal M \models \exists v \psi(v,a_1,\ldots,a_n) \Rightarrow \mathcal N \models \exists v \psi(v,a_1,\ldots,a_n)$.

I've elided over some details, but this should be a workable outline of an argument.