# Understanding the link between Tennenbaum Theorem and Godel Rosser

In Models of Peano Arithmetic by Kaye, p153, it states : Tennenbaum's theorem may be regarded as the model-theoretic analogue of the Godel-Rosser incompleteness theorem.

Similarly

In Cohen Set Theory and the Continuum Hypothesis, p49 it states "By a similar argument using Tarski's theorem on the un-definability of truth, (and without using recursively inseparable sets) one "easily" shows "There is no non-standard model M for the integers in which + and * are given by functions definable in Z1 (i.e. PA) and such that all the true statements of Z1 (PA) hold in M (a non standard model of Z1 (PA)).

My first question is - is there a proof of Cohens "easy" proof somewhere I could read?

My second question is on Kayes p153 statement : Is it saying that models of PA exist (viewed purely from the Metatheory) which satisfy additional statements to those that are derivable from Z1 (PA) and that these models include non-isomorphic models, called "Non-standard" models, and these additional statements are "not recursive" in that they aren't made up from a finite set of expressions based upon Z1 (PA) axioms. ? Are there examples of what these "additional statements" look like, or where they sit in the arithmetical higher-archy ? I suspect its saying more than this.

First of all, the theory of a model, i.e the collection of all sentences satisfied by the model, is always complete. We know, however, by the incompleteness theorem, that $PA$ is not complete. Therefore, every model of $PA$ has to satisfy statements that are not derivable from $PA$. For example, the standard model $\mathbb{N}$ satisfies $Con(PA)$ (well, presumably it does) and there is also a non-standard model of $PA$ satisfying $\neg Con(PA)$. (This is a consequence of the second incompleteness theorem. The claim that $Con(PA)$ is independent of $PA$ is equivalent to the assertion that there are models of $PA$ satisfying $Con(PA)$ and $\neg Con(PA)$.)
• Every countable set can be thought of as having domain $\omega$, the standard natural numbers (just with a different labeling, ie $a_0, a_1, a_2, \ldots$). So if we have a countable model of any theory, we can ask whether that model's functions/relations are computable functions and relations. Tenenbaum's theorem says that if M is a countable non-standard model of PA, then there is no algorithm which can compute addition or multiplication for that model. – Athar Abdul-Quader Sep 28 '16 at 12:50