Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 144 / 1

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})$.