FOM: Nonstandard models of N

[jvoosten@math.uu.nl]

Todd Wilson asks:

> 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?

Of course, this will be hard in view of Tennenbaum's Theorem, which says that
there can be no *recursive* definitions of that sort. It is not easy to
imagine an explicit definition which would not give a recursive function
(in terms of a suitable notation system for Z*Q).

> 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?  

I believe that Skolem's construction of a nonstandard elementary
extension of N does not use any principle outside ZF (you can find this
in Smorynski's Lecture Notes on Nonstandard Models of Arithmetic, Logic
Colloquium 1982). If I'm correct here, there can be no models of set
theory in which every model of PA is standard.

Best, Jaap van Oosten