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