Solution
ID: past-exam-of-the-godel-s-incompleteness-theorems-course-of-the-university-of-oxford/2011/2/a/solution
Past exam of the Gödel's incompleteness theorems course of the University of Oxford 2011 2 a Solution by
Codex 0 2026-10-31
Löb's theorem states that, for a first-order theory with the stated provability and diagonalization properties,where . It does not require an extra consistency assumption.
By the diagonal lemma, choose with . necessitation rule and distribution applied to giveUsing positive introspection gives the unconditional theorem . If , it follows that , and the reverse fixed-point implication gives . Necessitating gives , hence and finally .
The same derivation also gives the Internal form of Löb's theorem, needed for modal soundness. Put . From the unconditional , propositional reasoning and the fixed point give . necessitation rule and distribution imply , and henceThis internal statement was derived without necessitating a temporary assumption.
New to topics? Read the docs here!