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

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

Burak suggests: The validity of the material on this page is questionable. In particular: Not only the proof is faulty, this theorem is wrong. If we have a recursively enumerable set A of axioms, then the set of theorems (and hence, the Gödel numbers of those) proven by A is recursively enumerable. Minimal arithmetic and PA are both recursively enumerable, and hence their theorems have a recursively enumerable set of Gödel numbers. Any recursively enumerable set is arithmetical with degree Sigma^0_1 in the arithmetical hierarchy. Moreover, there is already a well known provability predicate Pr(x) in the language of Peano arithmetic. Indeed, if we use the diagonal lemma on ~Pr(x) to get a sentence with T proves G iff ~Pr(G), then we will have an unprovable sentence. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by resolving the issues. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Questionable}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

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).

Burak suggests: The validity of the material on this page is questionable. In particular: The below argument is not correct. $T$ does not necessarily prove that $\neg \map \theta {\hat G}$ just because it does not prove $G$. PA has a provability predicate $\map \Pr x$ which satisfies the property that if PA proves G, then PA proves $\map \Pr {\hat G}$). The step used here assumes a somewhat similar property in the opposite direction that our provability predicate satisfies if T does not prove G, then T proves $\neg \map \theta {\hat G}$, which we did not have as an assumption on $\map \Theta x$. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by resolving the issues. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Questionable}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

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

• 2007: George S. Boolos, John P. Burgess and Richard C. Jeffrey: Computability and Logic (5th ed.)