117b – Undecidability and incompleteness – Lecture 8

We introduce Robinson’s arithmetic Q. It is a weak (and sound) theory that proves all true S01 sentences. We also introduce Peano Arithmetic PA. PA is sound and designed to “capture” all true first order statements about N. (The incompleteness theorems will show that it does not suceed: There are true statements that PA does not prove.)

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

We prove the fixed point lemma and deduce 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 )

Google photo

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

Twitter picture

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

Facebook photo

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

Connecting to %s

%d bloggers like this: