Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 27 / 4

The Godel completeness theorem is strong completeness: for any first-order theory $T$ and sentence $\sigma$,Equivalently every syntactically consistent theory has a model. Work in the ordinary classical metatheory with choice; the language need not be countable. Soundness is induction on a derivation: logical axioms hold under every assignment, modus ponens preserves truth, and the quantifier rule preserves truth when its variable is not free in the assumptions. We prove the nontrivial converse by a Henkin construction.

Start with a consistent $T$ and add a constant if the language has no closed term. Let $L_0$ be this language. At stage $n$, for every existential sentence $\exists x\phi (x)$ of $L_n$, add a fresh constant $c_{\phi }$ and the witness axiomAn axiom of this form is conservative for consistency: if a contradiction followed after adding it, the old theory would prove its negation, hence both $\exists x\phi (x)$ and $\neg \phi (c_{\phi })$. Since the constant is fresh, replace it by a fresh variable and generalize, obtaining $\forall x\neg \phi (x)$, a contradiction. Every finite set of new witness axioms can be handled one at a time, so each stage remains consistent. Their union $T_H$ is consistent because a finite proof uses only finitely many stages.

Well-order the sentences of $L_H={\bigcup }_n{L}_n$. Successively add a sentence if doing so is consistent, and otherwise add its negation. At least one of those two choices preserves consistency: otherwise the deduction theorem would give both its negation and its double negation in the previous theory. At limits take unions. The deductive closure $\Gamma$ of the resulting union is complete and consistent and retains all witness axioms. Every sentence of $L_H$ uses finitely many symbols and belongs to some $L_n$, so its existential witness was added at the next stage. Thus $\Gamma$ has the Henkin witness property even for formulas using the new constants.

Build its term model. The domain consists of closed terms modulo $s\sim t$ iff $\Gamma ⊢s=t$. Equality axioms make this an equivalence relation and a congruence. Interpret functions by forming their corresponding terms, and interpret a relation $R$ by $R([t_1],\dots ,[t_r])$ iff $R(t_1,\dots ,t_r)\in \Gamma$. Congruence makes this independent of representatives.

The truth lemma for a Henkin term model is proved by induction on formulas after substituting closed terms for their free variables. Atomic formulas are the definition. Completeness and consistency of $\Gamma$ give the Boolean steps. For existence, if $\exists x\phi (x,\bar{t})\in \Gamma$, a witness axiom yields a constant $c$ with $\phi (c,\bar{t})\in \Gamma$, and induction supplies a model witness. Conversely every domain element is a term class, so a model witness gives an instance in $\Gamma$, and existential introduction gives the existential sentence. Universality follows by negation and existence. The model therefore satisfies $\Gamma$, hence $T$.

Finally, if $T⊬\sigma$, then $T\cup \{\neg \sigma \}$ is consistent by the deduction theorem and classical logic. Its constructed model is a countermodel to $T\models \sigma$. This proves completeness, with an actual witness model rather than merely a finite-satisfiability assertion.

For nonempty first-order structures $(M_i{)}_{i\in I}$ and an ultrafilter $\mathcal{U}$ on $I$, define the ultraproduct by quotienting the product domain byFunctions are interpreted coordinatewise; a relation holds when its coordinate truth set belongs to the ultrafilter. Closure under finite intersections makes these interpretations independent of representatives. The Łoś theorem asserts, for every formula $\phi$,

Prove it by structural induction. A term evaluates coordinatewise, by induction on its construction, so atomic equality and relations are exactly their defining truth sets. Conjunction uses intersection; negation uses the ultrafilter property that exactly one of a set and its complement belongs to $\mathcal{U}$. These establish all Boolean connectives.

For the existential step put $A=\{i:M_i\models \exists x\psi (x,{\bar{a}}_i)\}$. If an ultraproduct witness $[b]$ exists, induction says $\{i:M_i\models \psi (b_i,{\bar{a}}_i)\}\in \mathcal{U}$, and this set is contained in $A$, so $A\in \mathcal{U}$. Conversely if $A\in \mathcal{U}$, choose a witness $b_i$ at every $i\in A$ and any domain element at the other coordinates. Induction makes $[b]$ a witness. This coordinatewise selection uses choice in the metatheory; nonemptiness of the factors is essential. Universal quantification follows from negation and existence, completing the proof.

For the requested compactness theorem, let $I=[T{]}^{<\omega }$. For each finite $F\subseteq T$, choose $M_F\models F$. For each sentence $\sigma \in T$, its cone $C_{\sigma }=\{F:\sigma \in F\}$ is nonempty, and intersections of finitely many cones contain the finite union of their requirements. These cones generate a proper filter. The ultrafilter lemma extends it to $\mathcal{U}$. The coordinate models satisfying $\sigma$ include $C_{\sigma }$, so the Łoś theorem makes their ultraproduct satisfy $\sigma$. Since this holds for each $\sigma \in T$, the ultraproduct is a model of $T$. No completeness theorem is needed in this second compactness proof.