117b- Homework 6

February 15, 2007

Due Thursday, February 22 at 1pm.

Homework 6


117b – Undecidability and incompleteness – Lecture 8

February 15, 2007

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.

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.