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
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 proof in more detail, feel free to use the talk page.
If you are able to fix this page, then when you have done so you can remove this instance of {{Questionable}} from the code.
If you would welcome a second opinion as to whether your correction is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
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).
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 proof in more detail, feel free to use the talk page.
If you are able to fix this page, then when you have done so you can remove this instance of {{Questionable}} from the code.
If you would welcome a second opinion as to whether your correction is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
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$
