Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 2 / 16H / b / i / Solution

The Godel completeness theorem says that for every first-order theory $\Gamma$ and sentence $\phi$,Together with soundness, this is equivalence; it is also equivalent to saying that every syntactically consistent first-order theory has a model.

The compactness theorem states that a set $\Gamma$ of first-order sentences has a model if and only if every finite subset ${\Gamma }_0\subseteq \Gamma$ has a model. To deduce it, suppose every finite subset is satisfiable but $\Gamma$ is not. Then $\Gamma \models \perp$, so completeness gives a formal proof $\Gamma ⊢\perp$. A proof uses only finitely many assumptions, yielding some finite ${\Gamma }_0⊢\perp$, contrary to that subset's satisfiability.