Past exam of the model theory course of the University of Oxford / 2011 / 2

A complete theory is a consistent first-order theory deciding every sentence in its language:Equivalently, every two first-order models of $T$ are elementarily equivalent. Consistency excludes the vacuous situation in which a first-order theory has no first-order models and entails both alternatives.

A first-order theory has quantifier elimination if every first-order formula is equivalent over the first-order theory to a quantifier-free formula with the same free variables:Logical truth and falsity may be treated as the empty Boolean combinations when considering sentences in a language without closed terms. The assertion concerns first-order formulas with free variables, not merely sentences.

A model-complete theory is a first-order theory for which every structure embedding between two of its first-order models is an elementary embedding. Thus, if $f:\mathcal{A}\hookrightarrow \mathcal{B}$ is such an embedding, then for every first-order formula $\phi (\mathbf{x})$ and tuple $\mathbf{a}$ from $A$,first-order model completeness does not assert that every two first-order models are elementarily equivalent: it constrains embeddings that exist between first-order models, whereas completeness constrains all first-order models.

If $T$ is model-complete, the inclusion of a substructure of a first-order structure $\mathcal{A}\subseteq \mathcal{B}$, both first-order models of $T$, is a structure embedding and hence elementary. Therefore $\mathcal{A}⪯\mathcal{B}$.

Conversely, assume every such inclusion is elementary, and take any structure embedding $f:\mathcal{A}\to \mathcal{B}$ between first-order models of $T$. Its image $f[A]$, with the induced first-order structure, is a substructure of $\mathcal{B}$ isomorphic to $\mathcal{A}$, so it is itself a first-order model of $T$. By hypothesis $f[A]⪯\mathcal{B}$. The isomorphism $\mathcal{A}\to f[A]$ preserves all first-order formulas, and composing it with this elementary inclusion shows that $f$ is an elementary embedding. Thus $\boxed{T\text{ is model-complete}⟺(\mathcal{A}\subseteq \mathcal{B}\models T\Rightarrow \mathcal{A}⪯\mathcal{B})}$.

A structure embedding preserves and reflects all atomic formulas, hence all quantifier-free formulas by induction on Boolean combinations. If $T$ has quantifier elimination, replace any $\phi (\mathbf{x})$ by a quantifier-free $\theta (\mathbf{x})$ equivalent over $T$. For $\mathcal{A}\subseteq \mathcal{B}\models T$ and a tuple $\mathbf{a}$ from $A$,Thus $\mathcal{A}⪯\mathcal{B}$, and the preceding criterion proves $\boxed{\text{quantifier elimination implies model completeness}.}$

WriteThese are first-order formulas in the original language, not new predicate symbols. An axiomatization consists of the equivalence relation axioms for $E$, the boundand, for every $n\ge 1$, the two sentencesThe first scheme supplies infinitely many singleton classes. The second supplies infinitely many distinct non-singleton classes; the size bound makes these doubletons.

Every countable first-order model has countably infinitely many classes of each size. A bijection between singleton classes, and another between doubleton classes followed by a bijection inside each matched pair, gives an isomorphism between any two countable first-order models. To infer completeness, suppose a sentence had different truth values in two arbitrary first-order models. The Downward Lowenheim-Skolem theorem supplies countable elementary substructures of those first-order models, which would still disagree on the sentence, contradicting the isomorphism just constructed. Thus all first-order models satisfy the same sentences. Since the original first-order structure satisfies the axioms, these axioms form a complete axiomatization of its first-order theory. This is the theory of infinitely many singleton and doubleton equivalence classes.

No. Let $S$ be the displayed infinite axiom set. Any finite subset $S_0\subseteq S$ mentions only finitely many of the two infinitude requirements. Choose $N\ge 1$ at least as large as every index mentioned. A finite equivalence relation with exactly $N$ singleton classes and $N$ doubleton classes satisfies $S_0$, but is not a first-order model of the complete theory.

If a finite axiomatization existed, let $\sigma$ be the conjunction of its axioms. Then $S\models \sigma$, so the compactness theorem gives a finite $S_0\subseteq S$ with $S_0\models \sigma$. Every first-order model of $S_0$ would then satisfy the full first-order theory, contradicting the finite first-order model above. This is the finite subaxiomatization from an equivalent finite theory argument: finite axiomatizability would force one finite fragment of the explicit axioms to suffice.

Take a countable elementary substructure ${\mathcal{B}}^{\prime }$ of ${\mathcal{A}}^{\prime }$ containing the named constant, using the Downward Lowenheim-Skolem theorem. Its reduct $\mathcal{B}$ has infinitely many singleton and doubleton classes. In particular it contains the partner of each of its non-singleton elements, and its interpretation of $P$ is exactly the singleton-class predicate.

Choose new distinct elements $u,v\notin B$. DefineIn $\mathcal{C}$, make $u$ a new singleton class. In $\mathcal{D}$, make $\{u,v\}$ a new doubleton class; keep every old class of $\mathcal{B}$ unchanged. All three reducts are first-order models of the complete theory, and $\mathcal{B}\subseteq \mathcal{C}\subseteq \mathcal{D}$.

Expand $\mathcal{C},\mathcal{D}$ by interpreting $P$ as singleton-class membership and retaining the original named constant from $B$. The resulting countable first-order structures ${\mathcal{C}}^{\prime },{\mathcal{D}}^{\prime }$ are each isomorphic to ${\mathcal{B}}^{\prime }$: all have infinitely many classes of each size, and the bijections of classes can be chosen to preserve the constant and its class. Hence they are first-order models of $\mathrm{Th}({\mathcal{A}}^{\prime })$. Both inclusions ${\mathcal{B}}^{\prime }\subseteq {\mathcal{C}}^{\prime }$ and ${\mathcal{B}}^{\prime }\subseteq {\mathcal{D}}^{\prime }$ are genuine structure embeddings, since no class meeting $B$ was changed. The given quantifier elimination, together with the preceding implication to first-order model completeness, yieldsTaking reducts gives $\boxed{\mathcal{B}⪯\mathcal{C},\mathcal{B}⪯\mathcal{D}}$. Butso $\boxed{\mathcal{C}⋠\mathcal{D}}$. There is no conflict with quantifier elimination in the expanded language: $P(u)$ changes truth value, so ${\mathcal{C}}^{\prime }$ is not a substructure of ${\mathcal{D}}^{\prime }$.

The inclusion $\mathcal{C}\subseteq \mathcal{D}$ is a structure embedding between first-order models of the same complete theory, but it is not an elementary embedding, as the existential partner first-order formula at $u$ shows. Therefore the first-order theory is not model-complete. The facts $\mathcal{B}⪯\mathcal{C}$ and $\mathcal{B}⪯\mathcal{D}$ do not make the intervening inclusion elementary.