Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 120 / 1

Expand $L$ to $L(M)$ by a constant $c_m$ for each $m\in M$. The diagram of a structure $\mathrm{Diag}(M)$ contains all atomic and negated atomic $L(M)$-sentences true in $M$. The elementary diagram $\mathrm{ElDiag}(M)$ contains every $L(M)$-sentence true in $M$.

The method of diagrams combines one of these sets with another theory and applies the compactness theorem. A model of $\mathrm{Diag}(M)$ yields an embedding of $M$ by $m\mapsto c_m$, while a model of $\mathrm{ElDiag}(M)$ yields an elementary embedding.

On $A={\bigcup }_i{A}_i$, interpret a constant at its common value, a function on a tuple by choosing one $A_i$ containing the tuple, and a relation similarly. Total ordering of the indices and compatibility of substructures make these definitions independent of the chosen stage. Every $A_i$ is then a substructure of $A$.

For an elementary chain, induction on formulas provesThe atomic step follows from the induced structure, Boolean steps are immediate, and for an existential formula any witness in the union lies in a later $A_j$ containing the parameters; elementarity between $A_i$ and $A_j$ moves existence back to $A_i$. This is the elementary chain theorem.

A sentence $\forall \bar{x}\exists \bar{y}\phi (\bar{x},\bar{y})$ with quantifier-free $\phi$ is preserved by a union of an embedding chain: a tuple $\bar{a}$ occurs at some stage, a witness $\bar{b}$ exists at that stage, and quantifier-free formulas are preserved in the union. Thus every forall-exists axiomatized theory is inductive.

Conversely, let $T_0$ contain all forall-exists consequences of $T$ and suppose $M\models T_0$. The diagram-and-compactness sandwich lemma says that one can constructwhere every $N_i\models T$ and every $M_i\preccurlyeq M_{i+1}$. For completeness, the first extension is obtained by adding to $T$ the diagram of $M_i$ together with all universal formulas over $M_i$ true there. A finite inconsistency would give a forall-exists consequence of $T$ false in $M_i$. The resulting extension embeds into an elementary extension $M_{i+1}$ by the method of diagrams.

The $N_i$ form an embedding chain and have the same union $N$ as the $M_i$. By the assumed preservation, $N\models T$; by the elementary chain theorem, $M\preccurlyeq N$. Hence $M\models T$, so $T_0\models T$. The two theories are equivalent, proving the characterization.

A model-complete theory is one for which every embedding between models is elementary. If $(M_i)$ is an embedding chain of models, all transition embeddings are therefore elementary. The elementary chain theorem shows that the union is a model elementarily extending every $M_i$, so the theory is preserved under unions of embedding chains. Part (c) then gives an axiomatization by forall-exists sentences.