SOME NOTES ON QUANTIFIER ELIMINATION AND MODEL COMPLETENESS

These notes are intended to clarify some remarks I made during the model theory classes. Definition 0.1. A theory T, which needn’t be complete, in a language with at least one constant symbol, has quantifier elimination if;

For all ϕ(x̄) ∈ L, there exists a quantifier free ψ(x̄) ∈ L, such that; T ⊢ ∀x(ϕ(x̄) ↔ ψ(x̄))

Lemma 0.2. Let ϕ(x̄) ∈ L, then the following are equivalent;

(i). There exists a quantifier free formula ψ(x̄) such that T ⊢ ∀x̄(ϕ(x̄) ↔ ψ(x̄))

(ii). For M, N ⊧ T M_{0} ⊆ M and M_{0} ⊆ N, ∀c̄ ∈ M_{0}; M ⊧ ϕ(c̄) iff N ⊧ ϕ(c̄)

Proof. Suppose (i) holds, then M ⊧ ϕ(c̄) ⇔ M ⊧ ψ(c̄)

⇔ M_{0} ⊧ ψ(c̄), M_{0} ⊆ M

⇔ N ⊧ ψ(c̄), M_{0} ⊆ N
⇔ N ⊧ ϕ(c̄)

so (ii) holds. Suppose (ii) holds, let Σ(x̄) be the set of all quantifier free formulae ψ(x̄) such that;

T ⊢ ∀x̄(ϕ(x̄) → ψ(x̄)) It is sufficient to prove that; T ∪ Σ(x̄) ⊢ ϕ(x̄)

2SOME NOTES ON QUANTIFIER ELIMINATION AND MODEL COMPLETENESS

Suppose not, then there exists M ⊧ T, ā ∈ M, M ⊧ Σ(ā) and M ⊧ ¬ϕ(ā). Let Γ(x̄) = qftp_{M}(ā), then T ∪ Γ(x̄) ∪ ϕ(x̄) is consistent. Otherwise, T ∪ {ϕ(x̄)} ⊢ ¬γ(x̄), for some γ ∈ Γ, whereby ¬γ ∈ Σ. Hence, there exists a model N ⊧ T, and b̄ from N, with qftp_{N}(b̄) = qftp_{M}(ā), such that N ⊧ ϕ(b̄). Let < ā > and < b̄ > be the structures generated by the tuples ā and b̄. As qftp_{M}(ā) = qftp_{N}(b̄), we have that there exists an isomorphism < ā >≅< b̄ >. It follows that there exists M_{0} ⊆ M, M_{0} ⊆ N, containing ā, with M ⊧ ¬ϕ(ā) and N ⊧ ϕ(ā), this contradicts (ii), hence, (i) holds.

□

Remarks 0.3. For the lemma, T need not be complete. Also observe that quantifier elimination requires that T can eliminate quantifiers from sentences of the language, so we need at least one constant symbol. As explained by Franziska, the lemma shows that the incomplete theory DT F AG does not have quantifier elimination. However, the completion obtained by adding ∃v(v ≠ 0) does, you can use the theorem below.

We observe that;

Lemma 0.4. T has quantifier elimination if all formulae of the form ∃yϕ(y, x̄) where, ϕ(y, x̄) is quantifier free, are equivalent to quantifier free formulae.

Proof. By routine induction. □

Then,

Theorem 0.5. Suppose that T is complete. T has quantifier elimination, iff for all M, N ⊧ T, where N is |T |^{+} saturated, finitely generated M_{0} ⊆ M, N, and b ∈ M \ M_{0}, there exists b′ ∈ N, and an isomorphism;

f :< M_{0}, b >→< M_{0}, b′ >

with f|M_{0} = id and f(b) = b′. (∗)

Proof. Suppose T has quantifier elimination, then there exists b′ ∈ N, with tp_{N}(b′/M_{0}) = tp_{M}(b/M_{0}). To see this, let ϕ(x, ā) ∈ tp_{M}(b/M_{0}), ā ∈ M_{0}, then;

T ⊢ ∃xϕ(x, ȳ) ↔ ψ(ȳ), with ψ(ȳ) quantifier free.

M ⊧ ∃xϕ(x, ā) ⇔ M ⊧ ψ(ā)

⇔ M_{0} ⊧ ψ(ā), as M_{0} ⊆ M
⇔ N ⊧ ψ(ā), as M_{0} ⊆ N
⇔ N ⊧ ∃xϕ(x, ā).

By compactness and |T |^{+} saturation of N, there exists b′ with the required properties. It is straightforward to see that < M_{0}, b >≅< M_{0}, b′ >; we have that, for ā ∈ M_{0}, ψ(x, ȳ) quantifier free;

< M_{0}, b >⊧ ψ(ā, b) ⇔ M ⊧ ψ(ā, b)

⇔ N ⊧ ψ(ā, b′)
⇔< M_{0}, b′ >⊧ ψ(ā, b′)

Conversely, suppose that (∗) holds. In order to prove quantifier elimination, we use Lemma 0.4. to show (ii) of Lemma 0.2. Suppose that M_{0} ⊆ M, N with M, N ⊧ T. We may assume that N ≺ N′, for N′, |T |^{+}-saturated. Let c̄ ∈ M_{0}. By Lemma 0.4, it is enough to check (ii) of Lemma 0.2, for ∃yϕ(y, x̄), with ϕ(y, x̄) quantifier free. We have that;

M ⊧ ∃yϕ(y, c̄) ⇒ M ⊧ ϕ(b, c̄)

⇒ N′ ⊧ ϕ(b′, c̄)
⇒ N′ ⊧ ∃yϕ(y, c̄)
⇒ N ⊧ ∃yϕ(y, c̄) as N ≺ N′

The converse is similar. □

Definition 0.6. A theory T, which need not be complete, is model complete if M, N ⊧ T and M ⊆ N implies that M ≺ N,

Lemma 0.7. The following are equivalent;

(i). T is model complete.

(ii). Every ϕ(x̄) ∈ L is equivalent to an existential formula, mod T.

(iii). Every ϕ(x̄) ∈ L is equivalent to a universal formula, mod T.

4SOME NOTES ON QUANTIFIER ELIMINATION AND MODEL COMPLETENESS

Proof. (ii) ⇒ (iii). We have that; T ⊢ ϕ(x̄) ↔ ∃ȳψ(ȳ, x̄) ∴ T ⊢ ϕ(x̄) ↔ ¬∀ȳ¬ψ(ȳ, x̄) ∴ T ⊢ ϕ(x̄) ↔ ¬∃z̄σ(z̄, x̄) ∴ T ⊢ ϕ(x̄) ↔ ∀z̄¬σ(z̄, x̄) (iii) ⇒ (ii) is similar. (ii), (iii) ⇒ (i) M, N ⊧ T and M ⊆ N, ϕ(x̄) ∈ L, ā ∈ M; T ⊢ ϕ(x̄) ↔ ∃ȳψ(ȳ, x̄) ↔ ∀z̄σ(z̄, x̄) M ⊧ ϕ(ā) ⇒ M ⊧ ∃ȳψ(ȳ, ā)

⇒ M ⊧ ψ(b̄, ā)

⇒ N ⊧ ψ(b̄, ā), as b̄ ∈ M and M ⊆ N
⇒ N ⊧ ∃ȳ(ȳ, ā)
⇒ N ⊧ ϕ(ā)

N ⊧ ϕ(ā) ⇒ N ⊧ ∀z̄σ(z̄, ā)

⇒ N ⊧ σ(b̄, ā) for all b̄ ∈ M

⇒ M ⊧ σ(b̄, ā), for all b̄ ∈ M
⇒ M ⊧ ∀z̄σ(z̄, ā)
⇒ M ⊧ ϕ(ā) again

(i) ⇒ (iii). Suppose that ϕ(x̄) ∈ L and let; Γ(x̄) = {ψ(x̄) ∈ L : ψ(x̄) universal in L, T ⊢ ∀x̄(ϕ(x̄) → ψ(x̄))}

SOME NOTES ON QUANTIFIER ELIMINATION AND MODEL COMPLETENESS5

We claim that T + Γ ⊢ ϕ(x̄), (∗). If so, then; T ⊢ (⋀ ψ_{i}(x̄)) ↔ ϕ(x̄) ∴ T ⊢ ∀z̄(ψ_{1}(x̄, z̄)) ∧ ∀ȳ(ψ_{2}(x̄, ȳ)) ∧ … ↔ ϕ(x̄) ∴ T ⊢ ∀z̄∀ȳ… (ψ_{1}(x̄, z̄) ∧ ψ_{2}(x̄, ȳ) ∧ …) ↔ ϕ(x̄) and we are done. If not, then there exists a model M of T + Γ(d̄) +

¬ϕ(d̄). It is a straightforward exercise to check that for a theory T, the models of T_{∀}, the universal consequences of T, are exactly those which have an extension that models T. Now;

Md̄ ⊧ (T + ϕ(d̄))_{∀} ≡ Γ(d̄) Hence, Md̄ ⊆ Nd̄ ⊧ T + ϕ(d̄) By (i), Md̄ ≺ Nd̄, so M ⊧ ϕ(d̄), a contradiction.

□

Definition 0.8. If M ⊆ N, we say that M is existentially closed in N, if for any existential formula ϕ(x̄) ∈ L, and ā ∈ M, if N ⊧ ϕ(ā), then M ⊧ ϕ(ā) Theorem 0.9. Robinson’s Test

T is model complete iff for M, N ⊧ T , M ⊆ N, M is existentially closed in N Proof. We first prove the following observation; If M ⊆ N, then M ⊆_{e.c} N iff there exists M ≺ M′ with N ⊆ M′ (∗)

Suppose (∗) holds, and N ⊧ ∃ȳϕ(ȳ, b̄), with ϕ(ȳ, b̄) quantifier free then M′ ⊧ ∃ȳϕ(ȳ, b̄), as N ⊆ M′ and M ⊧ ∃ȳϕ(ȳ, b̄), as M ≺ M′ so M ⊆_{e.c} N. Conversely, suppose that M ⊆_{e.c} N, then we show

that; T′ = T h(M, M) ∪ q.f.diag(N , N) in L(N) is consistent. Suppose not, then;

T h(M, M) ⊢ ¬ϕ(ā, b̄) for ϕ(x̄, ȳ) ∈ L, ā ∈ M, b̄ ∈ (N \ M)

Therefore, T h(M, M) ⊢ ∀ȳ¬ϕ(ā, ȳ)

T h(M, M) ⊢ ¬∃ȳϕ(ā, ȳ)

so M ⊭ ∃ȳϕ(ā, ȳ), a contradiction, as now M is not existentially closed in N. Robinson’s result now follows easily, one direction follows trivially from the definition of model completeness. For the other direction, suppose that;

M_{0} ⊆ N_{0} with M_{0}, N_{0} ⊧ T. By hypothesis, we have that;

M_{0} ⊆_{e.c} N_{0} ⊆_{e.c} M_{1} ⊆_{e.c} N_{1} (∗∗)

where, by the previous observation, M_{0} ≺ M_{1} ⊧ T, and N_{0} ≺ N_{1} ⊧ T.

Continuing the chain (∗∗), we have that M_{k} ≺ M_{k+1} and N_{k} ≺ N_{k+1}. Then M_{0} ≺ ⋃ M_{k} = ⋃ N_{k} ≻ N_{0}. Hence, M_{0} ≺ N_{0} as required. □

Remarks 0.10. Be careful not to confuse Robinson’s test for model completeness with the Tarski-Vaught test for elementary substructure. This says that if M ⊆ N, then M ≺ N iff for every formula ∃yϕ(x̄, y) and ā ∈ M, if N ⊧ ∃yϕ(ā, y), then there is b ∈ M with M ⊧ ϕ(ā, b). It is proved easily using induction on the complexity of formulae.