## 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_n$truth 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)$.