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?
