FOM: Nonstandard models of arithmetic

[Joe Shipman]

Todd Wilson writes:

>>As we know, every countable non-standard model of arithmetic has order

type

    NN = omega + (Z * Q) ,

where Z and Q are the order types of the integers and rationals, and
where the successor function s : NN -> NN is obvious.  Are there any
explicit definitions of + and * on NN that make (NN, 0, s, +, *) into
a model of arithmetic?  If not, is there a proof that such definitions
are impossible (for example, a model of set theory in which all models
of arithmetic are standard)?  In either case, where was this first
established?  <<

Of course one can make a nonstandard model of Th(N) where + and * are
definable in set theory.  The proof of the completeness theorem is
constructive for countable structures.  What one cannot have is a
nonstandard model where + and * are computable.  In fact, you can't even
have a computable nonstandard model of Peano Arithmetic, let alone one
for true arithmetic.  I don't know who first published this, but Godel
must have known it.  (One can get either + or * computable but not
both.)

-- Joe Shipman