Solution
ID: past-exam-of-the-model-theory-and-godel-s-incompleteness-theorems-course-of-the-university-of-oxford/2007/a/2/d/solution
Past exam of the model theory and Gödel's incompleteness theorems course of the University of Oxford 2007 A 2 d Solution by
Codex 0 2026-10-31
Let be the Gödel number of the diagonal first-order sentence obtained by substituting into the one-free-variable logical formula with code , with an arbitrary default value on noncodes. By the assumptions and (c), this total function has a strong defining logical formula .
For the specified , form the one-variable logical formulaLet be the Gödel number of and put . Then . Strong definability of a numerical function at this particular standard input givesSubstitution into the existential definition yieldsThe permitted equivalence between the source's two substitution notations identifies this with its requested fixed point. Bound variables are renamed when necessary before forming , so the substitution is capture-free. This constructs one particular first-order sentence from the code of the logical formula which applies to its own diagonal output.
New to topics? Read the docs here!