Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 23 / 1

The compactness theorem for first-order logic says that a set $\Sigma$ of first-order sentences has a model if and only if every finite subset of $\Sigma$ has a model. It applies to arbitrary languages, including expansions by arbitrarily many new constants. Equivalently, if $\Sigma$ entails a sentence, some finite subset already entails it. We will use both formulations with the diagram of a structure.

Name every element $a\in A$ by a new constant $c_a$, distinct from the symbols already in $L^{\prime }$. Let $\mathrm{Diag}(A)$ be its full atomic and negated atomic diagram of a structure. A model of this diagram contains an isomorphic copy of $A$ as an $L$-substructure. We claimis satisfiable.

Otherwise compactness theorem gives a finite diagram conjunction $\delta (c_{a_1},\dots ,c_{a_m})$ inconsistent with $T^{\prime }$. Replace these new constants by variables. Since $T^{\prime }$ says nothing about the new names, it then entails the universal sentenceThe conjunction $\delta$ uses only symbols of $L$, so this is one of the universal $L$-consequences assumed true in $A$. But $A$ satisfies $\delta (a_1,\dots ,a_m)$, a contradiction. A model of the consistent enlarged theory gives an embedding of $A$ into the $L$-reduct of a model of $T^{\prime }$. Negated atomic facts and disequalities in the diagram ensure that this is a structure embedding, not merely a homomorphism.

Let $U$ be all universal sentences true in $C$. The theory $T\cup U$ is consistent. Indeed, if a finite conjunction $u$ of sentences from $U$ were inconsistent with $T$, then $T\models \neg u$. A finite conjunction of universal sentences is universal, so its negation is equivalent to an existential sentence. By the hypothesis $C$ would satisfy $\neg u$, whereas it satisfies $u$.

Choose $A\models T\cup U$. Now expand the language by names for every element of $C$ and consider its elementary diagram $\mathrm{ElDiag}(C)$. Its universal consequences in the original language are exactly $U$: any such consequence is true in the named copy of $C$, while any original-language sentence true in $C$ already belongs to its elementary diagram. Part (b), applied to $A$ and this expanded theory, gives a structure embedding of $A$ into a model $D$ of $\mathrm{ElDiag}(C)$. The named copy of $C$ is an elementary substructure of $D$. Identifying that copy with $C$, we obtainThus the required target is an elementary extension of $C$, although $C$ itself need not be a model of $T$.

Let $S$ be the set of all existential sentences entailed by $T$. Certainly every model of $T$ satisfies $S$. Conversely, take $C\models S$. Part (c) gives $A\models T$ embedded in an elementary extension $D$ of $C$. After identifying $A$ with its image, $D$ is a superstructure of a model of $T$. The assumed closure under superstructures implies $D\models T$. Since $C\preccurlyeq D$, it follows that $C\models T$ as well. HenceThis supplies an existential axiomatization. Conversely, an existential sentence is preserved under embeddings because its finite tuple of witnesses and the quantifier-free facts about them persist, explaining why this is the appropriate syntactic class.