A theory *T* (r.e., extending *Q*) is *reflexive* iff it proves the consistency of all its finite subtheories. It is *essentially reflexive* iff each r.e. extension is reflexive.

Then *PA* is essentially reflexive and therefore no consistent extension of *PA* is finitely axiomatizable. This is obtained by showing that, in spite of Tarski’s undefinability of truth theorem, there are (provably in *PA*) *S*^{0}_{n}–*truth predicates* for all *n*.

We define Rosser sentences and show their undecidability. We also show Löb’s theorem that if *T|-PA* is an r.e. theory and* T*|-Pr_{T}(j)®j, then *T*|- j. This gives another proof of the second incompleteness theorem.

Finally, we show that the length of proofs of P^{0}_{1}-sentences is not bounded by any recursive function: For any *T|-Q* r.e. and consistent, and any recursive function *f*, there is a P^{0}_{1}-sentence j provable in *T* but such that any proof of j in *T* has length > *f(*j*).*

### Like this:

Like Loading...

*Related*

This entry was posted on February 22, 2007 at 3:49 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