FOM: Nonstandard models of N

[William Tait]

Tod Wilson wrote (3/9/01)

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

By arithmetizing Goedel's completeness theorem, we obtain a  model 
with domain N in which the distinguished functions and relations are 
expressed by  formulas that are Delta^0_2 in PA, Peano arithmetic. 
This is so for any consistent c.e. axiomatized theory. (A proof is 
given in the case of a single axiom in Kleene's *Introduction to 
Metamathematics*---It is Theorem 35, p. 394.) This is optimal, as  I 
recall, in the general case [of a consistent c.e. set of axioms]. (My 
feeble memory associates this fact with Andrzej Mostowski.)

In the case of non-standard models of PA, as Jaap van Oosten (today) 
points out, Stanley Tennenbaum's result shows that the arithmetic 
operations, +1, + and x, cannot be Sigma^0_1. Can they be Pi^0_1?

Of course, none of this fully answers Tod Wilson's question: in the 
Delta^0_2 model, the domain is N, not NN. To obtain the definitions 
of + and * in the model with domain NN, we must use the proof that 
the order type of N in a nonstandard model of PA with domain N is the 
natural order typeof  NN to construct the relevant isomorphism 
between the nonstandard ordering of N and the natural ordering of NN.

Before Tennenbaum's result, it was known that there is no nonstandard 
arithmetical model of T(N), the set of true sentences of PA---was 
this Ehrenfeucht? As Joe Shipman (today) points out, arithmetizing 
the completeness theorem yields an explicit definition in this case, 
too, of nonstandard model.

But, with all due respect, Joe, you shouldn't call the proof of the 
completeness theorem, even for countable languages, `counstructive'. 
The constructive part of the proof was given by Herbrand.

 From Chicago, where the sun always shines and the people always smile,

Bill Tait