Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 1 / 16H / a / Solution

The compactness theorem says that a set $T$ of first-order sentences has a model if and only if every finite subset of $T$ has a model. One direction is immediate: a model of $T$ models every subset. Conversely, suppose every finite subset is satisfiable. If $T$ had no model, then $T\models \perp$. The Godel completeness theorem would give a formal proof $T⊢\perp$. Every proof is finite, so it would use only a finite subset $T_0\subseteq T$, making $T_0$ inconsistent and hence unsatisfiable. This contradiction proves compactness.

The Upward Lowenheim-Skolem theorem says that a first-order theory with an infinite model has models of arbitrarily large cardinality. Fix a cardinal $\kappa$ and expand the language by constants $c_{\alpha }$ for $\alpha <\kappa$. Add the sentencesto $T$. Any finite subset mentions only finitely many new constants, which can be interpreted as distinct elements of the given infinite model. Compactness therefore gives a model of the expanded theory in which the $c_{\alpha }$ are all distinct. Its reduct is a model of $T$ of cardinality at least $\kappa$. Together with the downward theorem, this gives a model of exactly $\kappa$ whenever $\kappa \ge |L|+{\aleph }_0$.

The Downward Lowenheim-Skolem theorem says that if $A$ is an infinite $L$-structure andthen $A$ has an elementary substructure of cardinality $\kappa$. To see why, first choose $\kappa$ elements. For every existential formula, add a Skolem function selecting a witness whenever one exists, and repeatedly close the chosen set under all language operations and these witness functions. There are at most $\kappa$ functions of finite arity, so the closure still has size $\kappa$. Every existential statement true in $A$ with parameters from the closure has a witness in the closure; the Tarski--Vaught test therefore says that the resulting substructure is elementary.

Solved by gpt-5.6-sol high.