# Gödel's first incompleteness theorem

## 1. Introduction

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

## 2. The first incompleteness theorem

The idea of the first incompleteness theorem is that, using the diagonalisation lemma, for any recursive theory $T$ extending $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 $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 $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 $Σ 1$ formula that represents it in $DOR$. To simplify notation we shall write this $Σ 1$ formula also as $Proof T ( x , y )$. Now by diagonalisation there is a sentence $G$ of $L A$ such that

$DOR ⊢ G ↔ ∀ x ¬ Proof T ( x , ⌜ G ⌝ ) ⁢$

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 $DOR$. Suppose that $T ⊢ G$. Then there is a proof of $G$ in $T$ and hence a Gödel-number $x ∈ ℕ$ of this proof. Therefore the $Σ 1$ sentence $Proof T ( x , ⌜ G ⌝ )$ is true and hence provable in $DOR$. But then $DOR$ proves $¬ ∀ x ¬ Proof T ( x , ⌜ G ⌝ )$ and hence $DOR$ proves $¬ G$. Since $T$ extends $DOR$, $T ⊢ ¬ G$, which contradicts the consistency of $T$. Hence $T ⊬ G$.

Now suppose $¬ G$ is provable in $T$, where $T$ is consistent and extends $DOR$. Then by the equivalence of $G$ and $∀ x ¬ Proof T ( x , ⌜ G ⌝ )$ in $DOR$, $T$ proves $¬ ∀ x ¬ Proof T ( x , ⌜ G ⌝ )$ which is to say that $T$ proves $∃ x Proof T ( x , ⌜ G ⌝ )$. But we also know from the previous paragraph that $G$ is not provable in $T$, which is to say that $¬ Proof T ( n , ⌜ G ⌝ )$ is provable in $DOR$ and hence $T$ for each $n ∈ ℕ$. This is not a contradiction in itself, but does say that $T$ is $ω$-inconsistent, i.e. for some $θ ( x )$, $T$ proves all of $¬ θ ( n )$ for all $n ∈ ℕ$ and also proves $∃ x θ ( x )$. This establishes the first incompleteness theorem.

Theorem.

Suppose $T$ is a recursive theory extending $DOR$ in a recursive language extending $L A$. Suppose also that $T$ is $ω$-consistent. Then there is a sentence $G$ such that $T ⊬ G$ and $T ⊬ ¬ G$.

## 3. Some observations

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

Theorem.

For each $ω$-consistent recursive theory $T$ extending $DOR$ in a recursive language extending $L A$ there is a consistent $ω$-inconsistent extension of $T$.

Theorem.

For each $ω$-consistent recursive theory $T$ extending $DOR$ in a recursive language extending $L A$ there is a true $Π 1$ sentence $G$ of $L A$ such that $T$ neither proves nor refutes $G$.

The importance of the second of these is that we have shown that $DOR$ proves all true $Σ 1$ sentences. It shows that no recursive theory can prove all true $Π 1$ sentences.