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*|- Pr_{T}(j).
*S*|- For any j, y ( Pr_{T}(j®y) Ù Pr_{T}(j) ® Pr_{T}(y) ).
*S*|-For any j ( Pr_{T}(j)®Pr_{T}(Pr_{T}(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: **

- 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* P^{0}_{1} sentence j such that *T* does not prove j. If *T* is S^{0}_{1}-sound, then *T* does not prove ¬j either.
- 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 S^{0}_{1}-soundness with the stronger assumption of w–*consistency*.

### Like this:

Like Loading...

*Related*

This entry was posted on February 20, 2007 at 4:53 pm and is filed under 117b, Undecidability and incompleteness. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply