Solution

ID: past-exam-of-the-godel-s-incompleteness-theorems-course-of-the-university-of-oxford/2011/1/a/solution

Write , with the corner notation understood as the numeral for the Gödel number. An arithmetical provability predicate numerates the theorems of in the standard natural numbers and satisfies the Hilbert-Bernays-Löb derivability conditions:
The last two conditions are internal theorems, not rules authorizing reflection from to .
Here numerates the theorem set by the given assumption. If , its proof supplies a genuine natural-number witness, making a true Sigma-1 formula. Sigma-1 completeness gives , proving the first condition. The second condition is supplied explicitly. Since is itself a Sigma-1 formula, the given formalized Sigma-1 completeness yields , the third condition. Thus the specified existential proof predicate is an arithmetical provability predicate.

New to topics? Read the docs here!