Diagonal Lemma

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $T$ be the set of theorems of some theory in the language of arithmetic which contains minimal arithmetic.


For any formula $\map B y$ in the language of arithmetic, there is a sentence $G$ such that

$T \vdash G \leftrightarrow \map B {\hat G}$

where $\hat G$ is the Gödel number of $G$ (more accurately, it is the term in the language of arithmetic obtained by applying the function symbol $s$ to $0$ this many times).




Proof

There is a primitive recursive function $\mathrm {diag}$ which is defined by:

$\map {\mathrm {diag} } n = \widehat {\map A {\hat A} }$

where:

$\map A x$ is the formula such that $\hat A = n$.
the $\hat {}$ sign denotes the Gödel number of the contained formula (and we are not being formal about distinguishing between integers and symbols in the language).

Informally, $\mathrm {diag}$ takes a Gödel number, decodes it to a formula, plugs in the Gödel number for that formula in place of a free variable, and encodes this new formula back to a new Gödel number.


Since $T$ contains $Q$, by Recursive Sets are Definable in Arithmetic applied to the graph of $\mathrm {diag}$, we have that there is some formula $\map {\mathrm {Diag} } {x, y}$ which defines the graph of $\mathrm {diag}$ in $T$.

That is:

$\map {\mathrm {diag} } n = m$ if and only if $T \vdash \map {\mathrm {Diag} } {n, m}$


Let $\map A x$ be the formula:

$\exists y \paren {\map {\mathrm {Diag} } {x, y} \land \map B y}$

Let $G$ be $\map A {\hat A}$.


We then have $T \vdash \map {\mathrm {Diag} } {\hat A, \hat G}$, by checking the definitions.


Let $T' = T \cup \set G$.

Then:

$T' \vdash \map A {\hat A}$

Hence:

$T' \vdash \exists y \paren {\map {\mathrm {Diag} } {\hat A, y} \land \map B y}$

But since $\hat G$ is the only number such that $T \vdash \map {\mathrm {Diag} } {\hat A, \hat G}$, this gives us:

$T' \vdash \map B {\hat G}$

Thus:

$T \vdash G \rightarrow \map B {\hat G}$


Let $T' = T \cup \set {\map B {\hat G} }$.

Again, we have:

$T \vdash \map {\mathrm {Diag} } {\hat A, \hat G}$

so this gives us:

$T' \vdash \map {\mathrm {Diag} } {\hat A, \hat G} \land \map B {\hat G}$

and hence:

$T' \vdash \exists y \paren {\map {\mathrm {Diag} } {\hat A, y} \land \map B y}$

But this is the same thing as:

$T' \vdash G$

Thus:

$T \vdash \map B {\hat G} \rightarrow G$


Thus $G$ is as claimed.

$\blacksquare$



Sources