FOM: Nonstandard models of N

Alasdair Urquhart urquhart at
Wed Mar 14 14:53:05 EST 2001

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.

More information about the FOM mailing list