117b – Undecidability and incompleteness – Lecture 8

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.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: