Prove completeness from elimination of quantifiers

Question

I have been asked to prove that DAG,the theory of non-trivial torsion-free divisible abelian groups, has quantifier elimination and deduce from that that it is complete.

What are the conditions to conclude completeness from quantifier elimination?

Also, I have been looking at different sources for the proof of quantifier elimination and they always take L={0,+,-} for the language of groups. Does it make a big difference if I only take L={0,+}?

Thanks!

Answer 1

Let me add a bit to Primo Petri's answer.

Let $T$ be a consistent theory with quantifier elimination. The following are equivalent:

1. $T$ is complete.
2. For every quantifier-free sentence $\varphi$, $T\models \varphi$ or $T\models \lnot \varphi$.
3. For any models $M\models T$ and $N\models T$, the substructures generated by the empty set in $M$ and $N$ are isomorphic.
4. There is a structure $A$ such that for any model $M\models T$, $A$ embeds in $M$.

Let's prove this.

$(1)\implies(2)$: Since $T$ is complete, it decides the truth of every sentence, and in particular every quantifier-free sentence.

$(2)\implies (3)$: For any model $M\models T$, the elements of the substructure generated by the empty set, $\langle \varnothing\rangle_M$, are exactly the evaluations of terms with no free variables. Then the isomorphism type of this structure is entirely described by quantifier-free sentences of the form $f(t_1,\dots,t_n) = t_{n+1}$ and $(\lnot) R(t_1,\dots,t_n)$, where $t_1,\dots,t_{n+1}$ are terms with no free variables, $R$ is an $n$-ary relation symbol, and $f$ is an $n$-ary function symbol. Since $T$ decides the truth value of every quantifier-free sentence, it completely describes the isomorphism type of $\langle \varnothing \rangle_M$. Thus $\langle\varnothing\rangle_M\cong \langle \varnothing \rangle_N$ for any model $N\models T$.

$(3)\implies (4)$: Let $N\models T$, and let $A = \langle \varnothing\rangle_N$. Then for any $M\models T$, $A\cong \langle \varnothing\rangle_M$, so $A$ embeds in $M$.

$(4)\implies (1)$: Let $M$ and $N$ be models of $T$. It suffices to show that if $\varphi$ is a sentence such that $M\models \varphi$, then also $N\models \varphi$. By quantifier elimination, $\varphi$ is equivalent in models of $T$ to a quantifier-free sentence $\psi$. So $M\models \psi$. Since $A$ embeds in $M$ and $\psi$ is quantifier-free, $A\models \psi$. Similiarly, $N\models \psi$. Since $N\models T$, $N\models \varphi$, as desired.

---

We can apply criterion 4 to show that DAG is complete: the trivial group embeds in every model.

---

Let me note that there's a subtlety involving languages with no constant symbols. To make the equivalent statements above make sense in this case, we have to use the correct conventions for first-order logic. Namely, we have to allow empty structures, and we have to include the symbols $\top$ (true) and $\bot$ (false) in our logic. This fixes two issues:

1. If our language $L$ has no constant symbols, and we don't include $\top$ and $\bot$, then there are no quantifier-free $L$-sentences at all. If $T$ has quantifier elimination, every sentence should be equivalent to a quantifier-free sentence, but this is impossible if there are no quantifier-free sentences!
2. If our language $L$ has no constant symbols, then the substructure $\langle \varnothing\rangle_M$ generated by the empty set is empty, and hence not a substructure (if we use the convention that structures must be non-empty).

Answer 2

A theory with QE is complete iff it decides all sentences in $L_{\rm qf}$.

Examples:

• the theory of dense linear orders and the theory of the random graph are complete because $L_{\rm qf}$ is empty (the language has no constants).

• the theory of divisible abelian groups (DAG) is complete because all sentences in $L_{\rm qf}$ are equivalent, modulo the theory of groups, to $n0=m0$

• the theory of algebraically closed fields is not complete because it does not decide the caracteristic of the field.

‐‐---------

As for the second question:

The natural language to formalize groups is $\{0,+,-\}$. For example, in this language the model theoretic notions of homomorphism and substructure coincide with the algebraic notions of group homomorphism and subgroup.

However, after a quick check it seems that the proof of QE for DAG goes through also when the language is $\{0,+\}$. You might have checked it already.