Past exam of the mathematics course of the University of Cambridge 2021 iii Paper 120 4 c Solution 2026-09-28
Let have a semidecidable axiomatization. If is inconsistent, the singleton axiom set is decidable and independent. If has no nonlogical axioms, the empty set already works. In the remaining case assume is consistent, choose a total computable enumeration of its axioms, allowing repetitions, and conservatively enlarge the language by fresh nullary predicates .
For each , let be the conjunction of copies of . The range is decidable by the Craig trick. Given a candidate formula of length , only indices are possible; compute , form the corresponding , and compare the finite list syntactically.
The new theory has exactly the same consequences in the original language. Every model of expands to a model of all by interpreting every as true, while the reduct of any model of all satisfies every . The axioms are independent: after deleting , take any model of , interpret as true for , and interpret as false. This expansion satisfies every remaining but not . Hence the form an independent tagged axiomatization that is decidable. Here equivalence means a conservative extension, or equivalently equality of all consequences in the original language.