Solution

ID: past-exam-of-the-model-theory-and-godel-s-incompleteness-theorems-course-of-the-university-of-oxford/2008/a/2/d/i/solution

Let denote the addition-commutativity first-order sentence and put . In the ordinary checker for PA derivations, replace the axiom test by
Keep all tests for sequence formation, earlier lines, logical axiom schemes and inference rules unchanged. This gives a formal proof checker which recognizes exactly ordinary -derivations. The finite syntactic modification is arithmetizable by the same bounded coding apparatus as the original checker.
For the proof-order comparison in the next part, make the choice of coding explicit. Reserve code for the one-line derivation of the newly added axiom , and give an ordinary derivation with code the new code . A corresponding bounded relation is
Every code has a specified decoding, every genuine formal proof is represented, and no false formal proof is admitted. The reserved code duplicates one genuine derivation, which is harmless. This is one explicit arithmetized arithmetical proof relation obtainable from the PA checker by the requested axiom change and a simple renumbering. Stating the proof-order convention matters because a Rosser predicate symbol uses code order, not merely the existence of formal proofs.

New to topics? Read the docs here!