Past exam of the model theory and Gödel's incompleteness theorems course of the University of Oxford / 2010 / B / 6 / b / Solution

For a structure in a countable language and any subset $C$ of its domain, there is an elementary substructure containing $C$ of cardinality at most $\max (|C|,{\aleph }_0)$. In particular a finite or countable $C$ lies in a countable elementary substructure. This is the downward Löwenheim-Skolem theorem.

Construct it directly inside the given structure $A$. Start with $C_0$ containing $C$, the interpretations of the constants, and one element if needed to ensure a nonempty domain. Given $C_n$, for every formula $\exists x\phi (x,a)$ with its finite parameter tuple from $C_n$ that is true in $A$, choose one actual witness in $A$ and place it in $C_{n+1}$. Retain $C_n$ as well. There are at most $\max (|C|,{\aleph }_0)$ choices at each stage. Let $B={\bigcup }_{n<\omega }{C}_n$.

The construction closes $B$ under every function of the language: for a tuple in $C_n$, the formula $x=f(a)$ forces its unique value into the next stage. Thus $B$ carries the induced substructure, and it has the asserted cardinal bound.

Prove elementarity by structural induction. Atomic formulas agree by the induced-substructure construction; logical connectives preserve agreement. For an existential formula with parameters in $B$, if it is true in $A$, all its parameters occur in some $C_n$, so the chosen witness lies in $C_{n+1}\subseteq B$. The induction hypothesis makes its matrix true in $B$. In the other direction a witness in $B$ is also a witness in $A$, again by induction. This is the Tarski-Vaught test, with its witness argument proved explicitly. No completeness or compactness theorem theorem enters the construction.