We introduce **Robinson’s arithmetic** *Q*. It is a weak (and *sound*) theory that proves all true S^{0}_{1} 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.

### Like this:

Like Loading...

*Related*

This entry was posted on February 15, 2007 at 2:50 pm and is filed under 117b, Undecidability and incompleteness. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply