117b – Undecidability and incompleteness – Lecture 9

Let S and T be r.e. theories in the language of arithmetic. Assume that S is strong enough to binumerate all primitive recursive relations. This suffices to prove the fixed point lemma:

For any formula g(x) there is a sentence j  such that S |- (j g(j)),

moreover, j can be chosen of the same complexity as g.

The (Löb) Derivability conditions  for S,T are the following three statements:

• For any j, if T|-j, then S|- PrT(j).
• S|- For any j, y ( PrT(j®y) Ù PrT(j)  ®  PrT(y) ).
• S|-For any j ( PrT(j)®PrT(PrT(j)) ).

For example, S=Q suffices for the proof of the fixed point lemma and of the first derivability condition and S=PA suffices for the other two.

Gödel incompleteness theorems:

1. Let S be r.e. and strong enough to satisfy the fixed point lemma and the first derivability condition. Let T |- S be r.e. and consistent. Then there is a true P01 sentence j such that T does not prove j. If T is S01-sound, then T does not prove ¬j either.
2. If in addition S satisfies the other two derivability conditions, then T does not prove Con(T), the statement asserting the consistency of T.

As a corollary, Q is essentially undecidable: Not only it is undecidable, but any r.e. extension is undecidable as well. Gödel’s original statement replaced S01-soundness with the stronger assumption of wconsistency.