FOM: Nonstandard models of N
William Tait
wwtx at midway.uchicago.edu
Wed Mar 14 21:54:56 EST 2001
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
More information about the FOM
mailing list