Independent tagged axiomatization 2026-09-28
In a conservative language extension, attach a fresh nullary predicate to the th axiom and use a self-indexing copy of . The fresh tag makes each new axiom independent of all the others, while forgetting the tags recovers exactly the original-language consequences. The Craig trick makes the resulting axiom set decidable.
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.