Article View: ut.theory
Article #3522414 correction
From: Stephen Cook
Date: Fri, 15 Dec 1989 20:29
Date: Fri, 15 Dec 1989 20:29
18 lines
1558 bytes
1558 bytes
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
Technical Details
Message-ID:
<89Dec15.152941est.2260@neat.cs.toronto.edu>Path:
arc1-ca.pugleaf.net!utzoo!attcan!utgpu!jarvis.csri.toronto.edu!neat.cs.toronto.edu!sacookShow Full Headers
Complete Article Headers
Path: arc1-ca.pugleaf.net!utzoo!attcan!utgpu!jarvis.csri.toronto.edu!neat.cs.toronto.edu!sacook From: sacook@cs.toronto.edu (Stephen Cook) Newsgroups: ut.theory Subject: 2414 correction Message-ID: <89Dec15.152941est.2260@neat.cs.toronto.edu> Date: 15 Dec 89 20:29:30 GMT Sender: list-admin@cs.toronto.edu Distribution: ut Lines: 18 Approved: ut.theory@mail.ai.toronto.edu Original-To: theorynews