117b – Undecidability and incompleteness – Lecture 10

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 PAS0ntruth 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|-PrT(j)®j, then T|- j. This gives another proof of the second incompleteness theorem.

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

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s


%d bloggers like this: