Solution
ID: past-exam-of-the-model-theory-and-godel-s-incompleteness-theorems-course-of-the-university-of-oxford/2010/a/2/c/solution
Past exam of the model theory and Gödel's incompleteness theorems course of the University of Oxford 2010 A 2 c Solution by
Codex 0 2026-10-31
The external necessitation rule assertion is valid. Suppose and fix a proof code . If is inconsistent the assertion follows by explosion. Otherwise there is no actual proof of . Each of the finitely many bounded checks up to is therefore a true bounded arithmetic fact and is provable. Together with the positive proof check at this gives
The requested internal modus-ponens assertion needs an additional coding property. Combining a proof of and a proof of produces a proof of , but its code can exceed both original codes. The two Rosser hypotheses exclude proofs of and only up to their respective witness bounds. They provide no bound excluding proofs of below the new proof code. Ordinary internal modus ponens rule for the unbounded provability predicate does not fill this gap.
Consequently the premises printed here do not, just by themselves, justifyThis property varies with the Rosser proof-order dependence: some specially chosen proof predicates satisfy it, while general Rosser proof predicates need not. [ref]
https://sartemov.ws.gc.cuny.edu/files/2012/10/Artemov-Beklemishev.-Provability-logic.pdf. Provability Logic, printed page 87: dependence of Rosser modus ponens rule on proof numbering
.The reference to a proof predicate “as given in the course” would need an explicit additional proof-order lemma to establish this part for that particular coding. Standard correctness on numeral instances and the ordinary Hilbert-Bernays-Löb derivability conditions alone are insufficient. The next solution gives the intended argument with the missing condition stated explicitly.
New to topics? Read the docs here!