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.
The idea of the first incompleteness theorem is that, using
the diagonalisation lemma, for any recursive theory
extending in the langauge
there should be a sentence which says
I am not
. 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 and the
Sentences and formulas of can be given
Gödel-numbering as we have seen. But proofs in a recursive language
extending are finite strings of symbols and
so there is a Gödel-numbering of proofs too. Therefore, given
we can consider the binary relation
is the Gödel-number of a proof from that
establishes the sentence with Gödel-number
. 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 is computable this program can
be modified to check that all the assumptions are axioms of ,
and thus we conclude that is a
recursive relation on the natural numbers.
Since it is a recursive relation on the natural numbers, there is a formula that represents it in . To simplify notation we shall write this formula also as . Now by diagonalisation there is a sentence of such that
This sentence can be thought of as asserting its own unprovability in .
Let us first check that really is unprovable in , provided is consistent and extends . Suppose that . Then there is a proof of in and hence a Gödel-number of this proof. Therefore the sentence is true and hence provable in . But then proves and hence proves . Since extends , , which contradicts the consistency of . Hence .
Now suppose is provable in , where is consistent and extends . Then by the equivalence of and in , proves which is to say that proves . But we also know from the previous paragraph that is not provable in , which is to say that is provable in and hence for each . This is not a contradiction in itself, but does say that is -inconsistent, i.e. for some , proves all of for all and also proves . This establishes the first incompleteness theorem.
Suppose is a recursive theory extending in a recursive language extending . Suppose also that is -consistent. Then there is a sentence such that and .
We present two useful observations, which can both be verified by looking carefully at the proof just presented.
For each -consistent recursive theory extending in a recursive language extending there is a consistent -inconsistent extension of .
For each -consistent recursive theory extending in a recursive language extending there is a true sentence of such that neither proves nor refutes .
The importance of the second of these is that we have shown that proves all true sentences. It shows that no recursive theory can prove all true sentences.