Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 144 (Model Theory)

The Tarski-Vaught test states that a substructure $M\subseteq N$ is an elementary substructure if and only if every formula $\phi (x,\bar{y})$ and tuple $\bar{a}\in M$ satisfyNecessity follows immediately from elementarity. Conversely, assume the witness condition. Induct on formulas to prove that $M\models \psi (\bar{a})$ exactly when $N\models \psi (\bar{a})$ for every $\bar{a}\in M$. Atomic formulas agree because $M$ is a substructure, and Boolean connectives follow by induction. A witness in $M$ is also one in $N$; a witness in $N$ can be replaced by one in $M$ by hypothesis, after which induction applies to the matrix. Universal formulas follow by negation. Thus the witness condition is equivalent to $M\preccurlyeq N$.

Define a parameter-free equivalence relation byIts classes correspond exactly to the distinct sets $\phi (a,\mathcal{U})$. If there are exactly $n<\infty$ classes, that fact is a first-order sentence, so the elementary substructure $M$ contains representatives $b_1,\dots ,b_n$ of all of them. Every $a\in \mathcal{U}$ is $E$-equivalent to some $b_i$, and $\phi (a,\mathcal{U})=\phi (b_i,\mathcal{U})$ is definable over $M$.

The converse also holds because $M$ is small and $\mathcal{U}$ is a monster model. If there were infinitely many $E$-classes, the partial complete typewould be finitely satisfiable. Saturation of $\mathcal{U}$ would realize $p$, producing a class with no representative in $M$, contrary to the hypothesis. Therefore there are only finitely many sets $\phi (a,\mathcal{U})$.

The theory of the random graph has the extension property: for finite disjoint vertex sets $A,B$, there is a new vertex adjacent to every point of $A$ and to no point of $B$.

Let $M,N$ be countable models and let $f_0$ be a finite partial embedding. Enumerate $M=(m_i{)}_{i<\omega }$ and $N=(n_i{)}_{i<\omega }$. At an even stage, take the first $m_i$ outside the domain. Its adjacency pattern to the finite domain prescribes finite disjoint subsets of the range; the extension property in $N$ supplies a new image with exactly that pattern. At an odd stage, apply the same argument to the inverse map and the first unused $n_i$. This back-and-forth method produces an increasing sequence of finite partial embeddings whose union is an isomorphism. Hence every finite partial embedding extends to an isomorphism $M\cong N$.

Assume no induced graph on $P_i$ has the random-graph extension property. For each $i$, choose finite disjoint $A_i,B_i\subseteq P_i$ such that no vertex of $P_i\setminus (A_i\cup B_i)$ realizes the prescribed adjacency pattern. The unions $A={\bigcup }_i{A}_i$ and $B={\bigcup }_i{B}_i$ are finite and disjoint. The extension property in $M$ supplies a new vertex $v$ adjacent to all of $A$ and none of $B$. But $v\in P_j$ for some $j$, contradicting the choice of $A_j,B_j$. Thus some $P_j$ satisfies the extension property. It is a countable model of the theory of the random graph, so part (a) gives

Suppose $a\in \mathrm{acl}(A)$ in the sense of model-theoretic algebraic closure. Some formula $\phi (x,\bar{c})$ over $A$ has exactly $n<\infty$ realizations in the monster model and includes $a$. Every model $M$ containing $A$ is an elementary substructure of the monster and therefore contains $n$ distinct realizations. Since there are only $n$ in the monster, it contains all of them, including $a$. Hence

Suppose $a\notin \mathrm{acl}(A)$. Choose a small model $M_0$ containing $A$. The complete type $\mathrm{tp}(a/A)$ is nonalgebraic, so choose a realization $a^{\prime }\notin M_0$. Strong homogeneity of the monster model gives an automorphism $\sigma$ fixing $A$ with $\sigma (a)=a^{\prime }$. Then $M={\sigma }^{-1}(M_0)$ contains $A$, but $a\in M$ would imply $a^{\prime }=\sigma (a)\in M_0$. Taking the contrapositive proves

Put $B=N\setminus \mathrm{acl}(A)$. We seek a model containing $A$ and omitting every element of $B$. Every finite set of these omission requirements is satisfiable: if a finite $C\subseteq B$ met every model containing $A$, the supplied result would imply $C\cap \mathrm{acl}(A)\ne \varnothing$, a contradiction.

Apply the compactness theorem to the elementary-diagram formulation of these requirements, using the Tarski-Vaught test to axiomatize the selected elementary submodel. It gives a model $M$ containing $A$ and omitting all of $B$. Part (a) gives $\mathrm{acl}(A)\subseteq M\cap N$, while omission of $B=N\setminus \mathrm{acl}(A)$ gives the reverse inclusion. Therefore

Let $D=\mathrm{dom}(f)$ and take a formula $\phi (x,\bar{d})$ over $D$. Since $T$ is a strongly minimal theory, the set $\phi (\mathcal{U},\bar{d})$ is finite or cofinite. If $\phi (b,\bar{d})$ holds, it cannot be finite because $b\notin \mathrm{acl}(D)$, so it is cofinite. Elementarity of $f$ makes $\phi (\mathcal{U},f\bar{d})$ cofinite. Its finite complement is algebraic over $f(D)$, so $c\notin \mathrm{acl}(\mathrm{ran}f)$ lies in the set. Applying the same argument to $\neg \phi$ gives the reverse implication. Hence $f\cup \{(b,c)\}$ is elementary: both elements realize the generic type in a strongly minimal theory over the corresponding domains.

If models $M,N$ have bases $B,C$ of the same dimension of a pregeometry, choose a bijection $B\to C$. Repeated use of the one-point result makes it elementary on every finite subset and hence on $B$. Every model is the algebraic closure of a basis. Extending the map back and forth across algebraic elements produces an isomorphism $M\to N$. Thus models of a strongly minimal theory with the same dimension are isomorphic.

Let $\kappa =|N|$. If the saturated model $N$ had a basis $B$ of cardinality below $\kappa$, then $N=\mathrm{acl}(B)$ would omit the consistent generic type in a strongly minimal theory over $B$. This contradicts $\kappa$-saturation. A basis is a subset of $N$, so its cardinality is at most $\kappa$. Therefore

Assume $\dim (N)=|N|=\kappa$, with $\kappa \ge |L|+{\aleph }_0$. Let $A\subseteq N$ have size below $\kappa$ and let $p(x)\in S_1(A)$ be a complete type. If $p$ is algebraic, its realizations lie in $\mathrm{acl}(A)\subseteq \mathrm{acl}(N)=N$. If $p$ is nonalgebraic, strong minimality makes it the unique generic type over $\mathrm{acl}(A)$. The pregeometry exchange property givesso some basis element of $N$ lies outside $\mathrm{acl}(A)$ and realizes $p$.

Thus $N$ realizes every one-type over every parameter set of size below $\kappa$. The standard one-type characterization, applied successively to tuple coordinates, makes $N$ $\kappa$-saturated. Consequently