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 T\vdash{\sf 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 {\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).


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: