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?

  • $\begingroup$ Are you both in the same class: math.stackexchange.com/questions/686126/… ? $\endgroup$ – Metin Y. Feb 22 '14 at 19:27
  • 1
    $\begingroup$ @Metin Y. haha, probably! I don't see how Ehrenfeucht Fraisse games would solve anything for this question though. $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.