117b – Undecidability and incompleteness – Lecture 10

A theory T (r.e., extending {sf 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 {sf PA} is essentially reflexive and therefore no consistent extension of {sf PA} is finitely axiomatizable. This is obtained by showing that, in spite of Tarski’s undefinability of truth theorem, there are (provably in {sf PA}Sigma^0_ntruth predicates for all n.

We defined Rosser sentences and showed their undecidability. We also showed Löb’s theorem that if Tvdash{sf PA} is an r.e. theory and Tvdash{rm Pr}_T(varphi)tovarphi, then Tvdashvarphi. This gives another proof of the second incompleteness theorem.

Finally, we showed that the length of proofs of Pi^0_1-sentences is not bounded by any recursive function: For any Tvdash {sf Q} r.e. and consistent, and any recursive function f, there is a Pi^0_1-sentence varphi provable in T but such that any proof of varphi in T has length > f(varphi).

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: