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

Expand the language by constants for every element of $M$ and a new tuple $c$. Let $\mathrm{ElDiag}(M)$ be the elementary diagram of a structure associated with $M$. Every finite subset ofis realized in the expansion of $M$, because the finitely many formulas from $p$ are simultaneously satisfiable in $M$. The compactness theorem gives a model $N^{\prime }$ of the whole set. The interpretations of the named constants give an elementary embedding $M\to N^{\prime }$, and the interpretation of $c$ realizes $p$. Identifying $M$ with its image produces an elementary extension $M⪯N$ realizing $p$. This is the finitely satisfiable type is realized in an elementary extension argument.

Write $\kappa =|\mathcal{U}|$ and define on tuples realizing $\mathrm{tp}(\bar{b}/\varnothing )$ the definable equivalence relationThe $E$-classes correspond exactly to the members of $O(\mathcal{D})$, because automorphisms of the monster model carry $\bar{b}$ through all realizations of its type.

There are at most $\kappa$ such tuples, so $|O(\mathcal{D})|\le \kappa$. If the orbit is infinite, recursively choose ${\bar{b}}_{\alpha }$ for $\alpha <\kappa$ in pairwise different $E$-classes. At stage $\alpha$, the typeis finitely satisfiable because there are infinitely many classes, and its parameter set has size less than $\kappa$. Saturation realizes it in $\mathcal{U}$. Thus there are at least $\kappa$ classes, proving the orbit of a definable set in a monster model identity

Let $p:A\to \mathcal{U}$ be a small partial embedding. To add a vertex $c$, prescribe for its image adjacency to $p(a)$ exactly when $c$ is adjacent to $a$, together with inequalities excluding the existing image. Every finite part of this prescription is realized by the extension axioms of the theory of the random graph, and saturation realizes the whole type. The same argument applies in the reverse direction. A transfinite back-and-forth method therefore extends $p$ to an automorphism of $\mathcal{U}$. Automorphisms preserve every first-order formula, so $p$ is elementary.

Part (a) says that every partial embedding preserves every formula. By the characterization supplied in the question, each formula is therefore equivalent modulo $T_{\mathrm{rg}}$ to a quantifier-free formula. Hence the quantifier elimination for the random graph holds.

The model-theoretic algebraic closure isEquivalently, it consists of elements with finite orbit under $\mathrm{Aut}(\mathcal{U}/A)$. The model-theoretic definable closure isequivalently the set fixed pointwise by every automorphism fixing $A$. Consequently $\mathrm{dcl}(A)\subseteq \mathrm{acl}(A)$.

Certainly $A\subseteq \mathrm{dcl}(A)$. If $c\notin A$, its quantifier-free type over $A$ records only its adjacency or nonadjacency to each element of $A$. The random-graph extension axioms make every finite part of this type realizable away from any prescribed finite set; saturation therefore gives infinitely many distinct realizations. By part (a), maps fixing $A$ and moving $c$ among these realizations are elementary and extend to automorphisms. Thus $c$ has an infinite orbit over $A$ and does not belong to $\mathrm{acl}(A)$. Hence the stronger algebraic and definable closure in the random graph identity holds:

For $\kappa =|N|$, saturation means that every complete type over a subset of $N$ of cardinality less than $\kappa$ is realized in $N$. The model $N$ is a universal model when every model of $T$ of cardinality less than $\kappa$ elementarily embeds into $N$, and it is a homogeneous model when every partial elementary map between subsets of $N$ of cardinality less than $\kappa$ extends to an automorphism of $N$.

Let $p(x)\in S(A)$ with $A\subseteq N$ and $|A|<\kappa$. Realize $p$ by $c$ in some elementary extension, and use the Downward Lowenheim-Skolem theorem to choose a model $M_0$ containing $A\cup \{c\}$ with $|M_0|<\kappa$. Universality gives an elementary embedding $e:M_0\to N$. Its restriction sends $A$ elementarily to $e(A)$. Homogeneity extends the inverse partial elementary map $e(A)\to A$ to an automorphism $\sigma$ of $N$. Then $\sigma (e(c))$ realizes $p$ over $A$. Thus the universal homogeneous model is saturated.

Use the Downward Lowenheim-Skolem theorem to choose a small elementary submodel $M⪯N$. By hypothesis, $M$ meets every $E$-class. If there were infinitely many classes, the typewould be finitely satisfiable: finitely many parameters meet only finitely many classes, so choose $x$ from another class. Its parameter set is small, so saturation would realize $q$ in $N$. That realization would lie in an $E$-class disjoint from $M$, contradicting the hypothesis. This proves the small elementary submodel meeting every definable equivalence class criterion: $E$ has only finitely many classes.

In a strongly minimal theory, model-theoretic algebraic closure is a pregeometry. If $C$ is algebraically closed, every element outside $C$ realizes the generic type in a strongly minimal theory: every one-variable definable set is finite or cofinite, and a point outside $C$ belongs to none of the finite ones.

Enumerate a finite tuple $a_1,\dots ,a_n$ of distinct elements of the independent set $A$. Independence saysIts image tuple under the bijection has the same property. Inductively, $a_i$ and $f(a_i)$ realize the same generic type over the algebraic closures of the preceding tuples, so every finite restriction of $f$ is elementary. First-order formulas involve only finitely many parameters, hence the entire bijection is an elementary map. This is the independent set in a strongly minimal theory principle.

Let $g:A\to B$ be a finite partial elementary map in $M$. In a countable language, the algebraic closures of finite sets are countable. An alternating back-and-forth construction extends $g$ to an isomorphismAt each step, an element algebraic over the current domain has a finite algebraic type, and elementarity provides a matching realization on the other side.

Choose a basis of a pregeometry $C$ over the first closed set and a basis of a pregeometry $D$ over the second. The dimension of a pregeometry is the same for the two extensions: the isomorphism preserves the finite ranks already contributed by $A$ and $B$, while both sides have the same ambient dimension. Choose a bijection $C\to D$. Part (a) and uniqueness of the generic type in a strongly minimal theory make the enlarged map elementary. Since an elementary submodel is algebraically closed in the monster,and the map extends over algebraic closure to an automorphism of $M$. Thus every finite partial elementary map extends to an automorphism: every model is homogeneous, as stated in homogeneity of models of a countable strongly minimal theory.