FOM: Re: Nonstandard models of N

Marcin Mostowski marcinmo at
Wed Mar 14 14:03:41 EST 2001

No, no, no, take the following standard models:
N1 = (omega, s),
N2 = (omega, +),
N3 = (omega, *),
N4 = (omega,+, *).
Theories of N1, N2, N3 are decidable, but of N4 is not decidable. Other sets
of natural numbers are definable in N1, N2, N3 - for first two see e.g.
Chang-Kiesler "Model theory", for N3 see e.g. Smorynski "Logical number
theory, vol. 1".

In each model of any reasonable set theory you will have continuum
nonisomorphic countable models elementary equivalent to N4 - as I remember
it is an exercise in Chang-Kiesler book. So a lot of nonstandard models.

Marcin Mostowski

----- Original Message -----
From: "Todd Wilson" <twilson at>
To: <fom at>
Sent: Saturday, March 10, 2001 2:45 AM
Subject: FOM: Nonstandard models of N

> Dear FOMers:
> 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,
> --
> Todd Wilson                               A smile is not an individual
> Computer Science Department               product; it is a co-product.
> California State University, Fresno                 -- Thich Nhat Hanh

More information about the FOM mailing list