FOM: Nonstandard models of N

[Alasdair Urquhart]

Stanley Tennenbaum proved in 1959 that there are no
nonstandard models of arithmetic in which the universe
is {0,1,2, ...} and both * and + are computable.
He published it as an abstract only, but it is 
quite easily established from the existence of two
recursively enumerable sets that are not recursively 
separable.  This seems to rule out "explicit definitions"
of + and *.  

There is a proof of Tennenbaum's result in, for example,
Paul Cohen's monograph on the continuum hypothesis (p. 48),
and no doubt elsewhere.  It extends to quite weak subsystems
of first-order PA.