Gödel's first incompleteness theorem

We have in the previous web pages set up the basic machinery of Gödel-numbering, representability of computable operations, the definition of $\omega$-consistency and so on to be able to prove the first incompleteness theorem.

The idea of the first incompleteness theorem is that, using the diagonalisation lemma, for any recursive theory $T$ extending $\text{DOR}$ in the langauge $L_A$ there should be a $L_A$ sentence which says I am not provable in $T$ . Now without the diagonalisation lemma this seems a very difficult thing to write down, but the trick of substitutions in the lemma makes this possible. So we turn next to the theory $T$ and the idea of provable.

Sentences and formulas of $L_A$ can be given Gödel-numbering as we have seen. But proofs in a recursive language $L$ extending $L_A$ are finite strings of symbols and so there is a Gödel-numbering of proofs too. Therefore, given $T$ we can consider the binary relation ${\mathrm{Proof}}_T(x,y)$ saying $x$ is the Gödel-number of a proof from $T$ that establishes the sentence with Gödel-number $y$ . This is just a binary relation on natural numbers and it is therefore a sensible question to ask how complicated it is. The key observation is that the rule of first order logic are all computable, i.e. programmable on a computer, and therefore there is a computer program that take a Gödel-number of a proof and checks it follows the proof rules of first order logic. If the set of axioms of $T$ is computable this program can be modified to check that all the assumptions are axioms of $T$, and thus we conclude that ${\mathrm{Proof}}_T(x,y)$ is a recursive relation on the natural numbers.

Since it is a recursive relation on the natural numbers, there is a ${\Sigma }_1$ formula that represents it in $\text{DOR}$. To simplify notation we shall write this ${\Sigma }_1$ formula also as ${\mathrm{Proof}}_T(x,y)$. Now by diagonalisation there is a sentence $G$ of $L_A$ such that

This sentence $G$ can be thought of as asserting its own unprovability in $T$.

Let us first check that $G$ really is unprovable in $T$, provided $T$ is consistent and extends $\text{DOR}$. Suppose that $T⊢G$. Then there is a proof of $G$ in $T$ and hence a Gödel-number $x\in \mathbb{N}$ of this proof. Therefore the ${\Sigma }_1$ sentence ${\mathrm{Proof}}_T(x,⌜G⌝)$ is true and hence provable in $\text{DOR}$. But then $\text{DOR}$ proves $\neg \forall x \neg {\mathrm{Proof}}_T(x,⌜G⌝)$ and hence $\text{DOR}$ proves $\neg G$. Since $T$ extends $\text{DOR}$, $T⊢\neg G$, which contradicts the consistency of $T$. Hence $T⊬G$.

Now suppose $\neg G$ is provable in $T$, where $T$ is consistent and extends $\text{DOR}$. Then by the equivalence of $G$ and $\forall x \neg {\mathrm{Proof}}_T(x,⌜G⌝)$ in $\text{DOR}$, $T$ proves $\neg \forall x \neg {\mathrm{Proof}}_T(x,⌜G⌝)$ which is to say that $T$ proves $\exists x {\mathrm{Proof}}_T(x,⌜G⌝)$. But we also know from the previous paragraph that $G$ is not provable in $T$, which is to say that $\neg {\mathrm{Proof}}_T(n,⌜G⌝)$ is provable in $\text{DOR}$ and hence $T$ for each $n\in \mathbb{N}$. This is not a contradiction in itself, but does say that $T$ is $\omega$-inconsistent, i.e. for some $\theta \left(x\right)$, $T$ proves all of $\neg \theta \left(n\right)$ for all $n\in \mathbb{N}$ and also proves $\exists x \theta \left(x\right)$. This establishes the first incompleteness theorem.

We present two useful observations, which can both be verified by looking carefully at the proof just presented.

The importance of the second of these is that we have shown that $\text{DOR}$ proves all true ${\Sigma }_1$ sentences. It shows that no recursive theory can prove all true ${\Pi }_1$ sentences.