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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: