= 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\bot$. The <Godel completeness theorem> would give a formal proof $T\vdash\bot$. 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 sentences
$$
c_\alpha\ne c_\beta
\qquad(\alpha\ne\beta)
$$
to $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\geq|L|+\aleph_0$.
The <Downward Lowenheim-Skolem theorem> says that if $A$ is an infinite $L$-structure and
$$
|L|+\aleph_0\leq\kappa\leq|A|,
$$
then $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.
Back to article page
