Set of Gödel Numbers of Arithmetic Theorems Not Definable in Arithmetic

From ProofWiki
Jump to navigation Jump to search

Theorem

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


The set of Gödel numbers of the theorems of $T$ is not definable in $T$.


Proof



The proof is by contradiction.


Let $\Theta$ be the set of Gödel numbers of the theorems of $T$.

Suppose it is defined in $T$ by the formula $\map \theta y$.


Since $T$ contains $Q$, we may apply the Diagonal Lemma to $\neg \map \theta y$.

This gives us a sentence $G$ such that

$T \vdash G \leftrightarrow \neg \map \theta {\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).



Suppose $G$ is not a theorem of $T$.

Then the Gödel number of $G$ is not in $\Theta$.
Since $\theta$ defines $\Theta$ in $T$, this means that:
$T \vdash \neg \map \theta {\hat G}$
But, by choice of $G$ (specifically, the bi-implication above), this gives us:
$T\vdash G$
which contradicts $G$ not being a theorem of $T$

Thus, $G$ is a theorem of $T$.

But, then the Gödel number of $G$ is in $\Theta$, and
since $\theta$ defines $\Theta$ in $T$, this means that
$T \vdash \map \theta {\hat G}$
But, then this gives us
$T \vdash \neg G$
which contradicts $G$ being a theorem of $T$, since $T$ is consistent.


Since assuming $\Theta$ was definable in $T$ necessarily leads to a contradiction, we conclude that it is impossible.

$\blacksquare$


Sources