Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/iii/paper-120/5/solution
Past exam of the mathematics course of the University of Cambridge 2021 iii Paper 120 5 Solution by
Codex 0 2026-09-28
Fix an effective enumeration of the unary partial computable functions. Suppose the setwere computably enumerable, say as . Thenwould be a total computable function. Hence for some , buta contradiction. Thus the set of Gödel numbers of total computable functions is not recursively axiomatizable; this is the totality problem is not computably enumerable argument.
Let be a recursively axiomatized theory of arithmetic. For each program index , fix an arithmetical sentenceexpressing that the computation with index halts on every input. Enumerate all formal -proofs and output whenever a proof ending in appears. This enumerates exactly the Gödel numbers of the computable functions that proves total, namely the provably total computable functions, so that set is recursively axiomatizable.
Assume now that is sound. Repeat every discovered index indefinitely, obtaining an effective infinite list of the functions whose totality proves. DefineSoundness makes every genuinely total, so is total and computable. If proved its totality, an index for would occur in the list, say , and thenwhich is impossible. Thus is a total computable function whose totality is not provable in .
New to topics? Read the docs here!