Past exam of the mathematics course of the University of Cambridge / 2008 / ii / Paper 2 / 16G (Logic and Set Theory)

The Godel completeness theorem for first-order logic states that $\Gamma \models \varphi$ implies $\Gamma ⊢\varphi$; together with soundness, semantic consequence and derivability coincide. Equivalently, every syntactically consistent first-order theory has a model. The compactness theorem states that a set of first-order sentences has a model if and only if every finite subset has a model. These statements use nonempty first-order structures.

For each $n$, let ${\sigma }_n$ assert the existence of $n$ distinct elements. If a theory $T$ has arbitrarily large finite models, every finite subset of $T\cup \{{\sigma }_n:n\ge 1\}$ has a model. By the compactness theorem, this extended theory has a model, necessarily infinite. Since fields of size $2^j$ are arbitrarily large, no first-order theory can have exactly the finite fields of characteristic two as its models.

Suppose instead a finite conjunction $\chi$ axiomatized exactly the infinite fields of characteristic two. Let $T_2$ be the field axioms with $1+1=0$. Then $T_2\cup \{\neg \chi \}$ would have exactly the finite characteristic-two fields as models, contradicting the preceding conclusion. Equivalently, compactness of $T_2\cup \{{\sigma }_n\}\models \chi$ would force some finite size threshold, but arbitrarily large finite fields still fail $\chi$. The infinite characteristic-two fields are not finitely axiomatizable.

The intended closed-term witness property for quantifier-free existential sentences needs at least one closed term. Under this hypothesis, suppose the set $\Gamma =\{\neg \varphi (t):t\text{ a closed term}\}$ were consistent. By the Godel completeness theorem, it has a model $M$. Take the substructure $M_0$ whose elements are the interpretations of closed terms. It is nonempty and closed under every function symbol. Atomic formulas and their negations have the same truth values in $M_0$ as in $M$, and induction extends this to every quantifier-free formula.

The provable sentence $\exists x\varphi (x)$ is true in $M_0$ by soundness. Its witness is $t^{M_0}$ for some closed term $t$, so $M\models \varphi (t)$, contradicting $M\models \Gamma$. Hence $\Gamma$ is inconsistent. The compactness theorem gives a finite inconsistent subset, so completeness and classical propositional reasoning yieldWithout a constant or nullary function, the printed assertion is false as written: in the equality-only language there are no closed terms, but $\exists x(x=x)$ is provable. Then $\Gamma$ is empty and consistent. One may repair the usual theorem by assuming a nonempty set of closed terms or adjoining a fresh constant; the latter proves a witness disjunction in the enlarged language, not the missing closed terms in the original one.