sacook@cs.toronto.edu (Stephen Cook) (12/16/89)
For question 8 for CSC 2414, I gave the definition of (M sub Q) incorrectly.
The correct definition is that (M sub Q) consists of all polynomials
in Q[x] whose leading coefficient is non negative and whose constant
term is an integer.
The motivation is this. The set of all polynomials with rational
coefficients and integer constant term forms an ordered domain whose
set of positive elements is the set (M sub Q) defined above. (See for
example Lipson's book, p 138, for the definition and properties of an
ordered domain.) This ordered domain is discretely ordered, since there
is no element between 0 and 1. Hence its positive elements "look like"
the natural numbers. In fact, every countable nonstandard model of
N will have the same order type (i.e. is isomorphic wrt <) as (M sub Q).
Furthermore, I think that (M sub Q) is a model for the first order theory
of (+,<,+,0,1), so your sentence which distinguishes (M sub Q) and N
will have to involve multiplication. Also, I think that every universal
first order sentence true in N is also true in (M sub Q), so your sentence
will have to involve existential quantifiers.
Steve