## 117b- Homework 6

February 15, 2007

Due Thursday, February 22 at 1pm.

We introduced Robinson’s arithmetic $\mathsf{Q}$. It is a weak (and sound) theory that proves all true $\Sigma^0_1$ sentences. We also introduced Peano Arithmetic $\mathsf{PA}$. $\mathsf{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 $\mathsf{PA}$ does not prove.)
We showed that $\mathsf{Q}$ represents all c.e. sets and binumerates all recursive sets, in particular all primitive recursive functions. $\mathsf{PA}$ actually proves that the representations of primitive recursive functions define functions, so in any (maybe non-standard) model of $\mathsf{PA}$ it makes sense to talk, for example, of the exponential function, or the function enumerating the primes.