117b – Homework 7

February 22, 2007

Due Thursday, March 1 at 1pm.

Homework 7


117b – Undecidability and incompleteness – Lecture 10

February 22, 2007

A theory T (r.e., extending \mathsf{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 \mathsf{PA} is essentially reflexive and therefore no consistent extension of \mathsf{PA} is finitely axiomatizable. This is obtained by showing that, in spite of Tarski’s undefinability of truth theorem, there are (provably in \mathsf{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 T\vdash\mathsf{PA} is an r.e. theory and T\vdash{\rm Pr}_T(\varphi)\to\varphi, then T\vdash\varphi. 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 T\vdash \mathsf{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).