## 117b – Undecidability and incompleteness – Lecture 8

We introduced Robinson’s arithmetic ${\sf Q}$. It is a weak (and sound) theory that proves all true $\Sigma^0_1$ sentences. We also introduced Peano Arithmetic ${\sf PA}$. ${\sf PA}$ is sound and designed to “capture” all true first order statements about ${\mathbb N}$. (The incompleteness theorems will show that it does not suceed: There are true statements that ${\sf PA}$ does not prove.)

We showed that ${\sf Q}$ represents all c.e. sets and binumerates all recursive sets, in particular all primitive recursive functions. ${\sf PA}$ actually proves that the representations of primitive recursive functions define functions, so in any (maybe non-standard) model of ${\sf PA}$ it makes sense to talk, for example, of the exponential function, or the function enumerating the primes.

We proved the fixed point lemma and deduced from it Tarski’s theorem on the undefinability of truth, thus formally solving the liar’s paradox.