Past exam of the mathematics course of the University of Cambridge 2008 ii Paper 2 16G iii Solution Created 2026-09-24 Updated 2026-10-14
The intended closed-term witness property for quantifier-free existential sentences needs at least one closed term. Under this hypothesis, suppose the set were consistent. By the Godel completeness theorem, it has a model . Take the substructure 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 as in , and induction extends this to every quantifier-free formula.
The provable sentence is true in by soundness. Its witness is for some closed term , so , contradicting . Hence 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 is provable. Then 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.