Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 144 / 2

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: