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.


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.


I am afraid, I can not give you a satisfying answer on your first question, but I can try clear up the confusion expressed in your second question.

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)$.)

Secondly, Tennenbaum's theorem is not talking about the 'recursivity' of statements, but it talks about recursive (or to be more precise non recursive) models. This is, a priori, a different question. There is, however a deep connection between the two statements, as described, for example, in Kayes book (p.189) or in his article 'Tennenbaum’s Theorem for Models of Arithmetic' (2006).

| cite | improve this answer | |
  • $\begingroup$ Thanks Jan. So maybe I have misunderstood Tennenbaum entirely ! Looking over Kaye definition of a recursive model, its one that is isomorphic, via any isomorphism function, to a model with domain N and recursive functions of +,* (not necessarily the real +,*). So its talking about whats possible in the Metatheory, in terms of the Metatheory recursive, and so finitely defined, functions ? $\endgroup$ – Little Cheese Sep 28 '16 at 11:41
  • $\begingroup$ Jan, also I note Kaye says (p154) that every non-standard M : M |=PA codes some non-recursive set. The justification for this is reference to Theorem 3.9 (simplified Godel Rosser) p38, that a recursive set of godel Numbers T is incomplete. The implication therefore is incomplete implies non-recursive. Presumably this is because PA can derive all recursive functions, so anything it can't derive (ie the missing incomplete statements) must be non-recursive ? $\endgroup$ – Little Cheese Sep 28 '16 at 12:00
  • $\begingroup$ Jan, So I've been wondering given the above two comments what the purpose of Tennenbaum is. As non-standard structures can be shown to exist by compactness (add a new element "c" and say its different from all elements "n" of N) - which is via an infinite number of expressions. So maybe Tennenbaum is saying there aren't any ways of creating a non-standard structure "roughly" in a finite number of steps (i.e. via some finite algorithm) ? $\endgroup$ – Little Cheese Sep 28 '16 at 12:06
  • $\begingroup$ 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. $\endgroup$ – Athar Abdul-Quader Sep 28 '16 at 12:50
  • $\begingroup$ Just noticed in Kaye - p189 the link between Godel-Rosser and Tennenbaum is formalised. It looks like using information related to Scott sets/Konigs Lemma + Tennenbaum implies Godel Rosser incompleteness (though I cant say I understand it yet). $\endgroup$ – Little Cheese Sep 28 '16 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.