117b – Undecidability and incompleteness – Lecture 10

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).

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: