# A Question About Tennebaum's Theorem?

Tennenbaum's theorem proves there are no countable recursive nonstandard models of Peano arithmetic. It is a proof by contradiction. If our countable, nonstandard model is recursive, then, given a pair of recursively inseparable sets, $A$, $B$, we can construct a separating set, $C$, such that $A \subset C$ and $C \cap B = \emptyset$. This would mean $A$ and $B$ are recursively separable contradicting our assumptions.

The separating set, $C$, can be a nonstandard finite set. For example, $C$ could the the exponents of the binary expansion of some non-standard natural number. Because we are assuming the non-standard model is countable, there are only a countable number of definable (in the model) nonstandard finite sets.

We didn't make any assumptions about the recursively inseparable sets so I can choose any such pair. If there are an uncountable number of pairs of recursively inseparable sets how can a countable non-standard model only have a countable number of separating sets? If the separating set, $C$, is not definable in the non-standard model then how does Tennenbaum derive a contradiction?

Another way to state my question is: are there sets of standard natural numbers such that these sets are not a subset of any definable nonstandard set in a countable non-standard model of PA?

• I told you before about humility in your titles. You should always start with the working assumption that there is nothing wrong in the established knowledge, and that you are wrong. If you dare make such claim that there is a flaw then you shouldn't pose it as a question. You should pose it as a proof, and even then if you want it to be treated seriously by mathematicians it is better to suggest the possibility of mistake, not to make it as a bold claim like you post here. Apr 8, 2014 at 23:07
• And as the previous questions that you posted showed, it is the usual case that you didn't understand very delicate points (which are difficult to understand, that is true). So please. Each time you give such silly titles to your question you erode a little more whatever patience people will have for you. And that's a shame, because I truly admire the fact that you try to prove the inconsistency of arithmetic while playing by the rules, and not by claiming that it has to be the case for whatever reason. Apr 8, 2014 at 23:10

To the question at the end of your post, no. There are no such sets. Every set of standard integers is a subset of $\{x\mid x=x\}$ of every model of $\sf PA$.
• I suppose that you mean recursive set? I don't know. In any case, note that if $C$ separates $A$ and $B$ then it separates every subset of $A$ from every subset of $B$. So every separating set is separating uncountably many pairs of sets on its own. Apr 8, 2014 at 23:19
• All finite sets are recursive in the model. The separating set can always be reduced to a non-standard finite set. I think we can show there must be an uncountable number of separating sets. There are an uncountable number of nonrecursive standard sets that are not subsets of $A$. Apr 8, 2014 at 23:59