FOM: first order and second order logic: once more

Matt Insall montez at rollanet.org
Tue Sep 5 08:37:42 EDT 2000


Comment:  I had previously sent this, thinking it went to the FOM list.  It
apparently went only to Roger Jones.



I am awaiting your definition.  In perhaps an moment of impatience, I looked
up what appears to be your web site.  I appreciate the work you have put
into it, but it appears to include very little of what you have been saying
about second order logic.  Most notably, I found no mention of your notion
of ``expressiveness''.  Perhaps I overlooked it.  If a url can answer my
question about what you mean by that word, I welcome it.

I am of a similar opinion to Professor Martin Davis, who specifically stated
in a recent post that he is of the opinion that ``every arithmetic sentence
has a determinate truth value.''  He went further, as I would, in saying ``I
even believe that CH has a determinate truth value''  (He also claimed he
could defend his position.  I would like to say the same, but am less
experienced in this particular arena, so I might hesitate to throw down that
gauntlet to this forum.  Moreover, I am not so sure that it will be either
accepted or rejected within twenty years, as he claims will occur.)

To be honest, your answer still has me puzzled, for as I understood it, you
were speaking of the same second order logic I was speaking of, namely one
in which a given language has a (possibly empty) set of relation variables
which may range over subsets of iterated cartesian powers of any given model
for the language.  I even assumed you meant that the language could have a
(possibly empty again) set of constant symbols, some of which may be symbols
to represent certain relations on the underlying universe of a given model,
so that a model may have ``distinguished subsets'' as well as the common
``distinguished members'' frequently considered in first order languages
with constant symbols.  Thus, if I consider for now that there is a standard
model (V,E,N,N) for second order set theory with the distinguished subset
and element N, consisting of the natural numbers, then I am happy to ``fix''
this second order model for the current discussion.  Upon doing so, I may
consider also the ``reduct'' (V,E,N) as a first order model of (first order)
ZF.  I have not changed the members of my model in any way.  I merely
consider now the ``distinguished subset and element'' N as only a
``distinguished member'' of my model, denoted again by N in my langauge
(which is now first order).  I no longer have a constant to represent the
predicate for the natural numbers.  Thus, the structure (representing my
semantics) has not changed significantly, and the only difference between
the languages (representing my syntax) is that my first order language has
as its symbols, formulas, etc, a proper subcollection of the second order
ones I started with.  The fact that (V,E,N) has in it some nonstandard
models of my first order number theory or set theory seems irrelevant to me,
for, insofar as the standard model (V,E,N) is concerned, first order
sentences like the one I presented express exactly the same semantic facts
about the same objects in the same universe as their second order
counterparts.  (I am using the term ``express'' here in an intuitive sense,
since I have not yet seen your definition of ``expressiveness''.  Can you
provide some references where the meaning of the word ``express'' is the
same as what you are intending?)  Of course, in this first order language,
certain second order facts may require more work to be expressed.  For
instance, Peano's second order induction axiom must be formulated using some
reference to the (first order definable) relation of ``subset of'' in the
model (V,E,N), but once it is formulated thusly, it expresses the same fact
about N in the model (V,E,N) that is expressed by the corresponding second
order formulation about N in the model (V,E,N,N).





Dr. Matt Insall
http://www.umr.edu/~insall

-----Original Message-----
From: Roger Bishop Jones [mailto:rbjones at rbjones.com]
Sent: Monday, September 04, 2000 9:26 AM
To: Matt Insall
Subject: Re: FOM: first order and second order logic: once more


Matt,

> Now, I am trying to determine your definition of ``express'', so please
bear
> with me.  How about the following first order formula of set theory?  Why
is
> it not an ``expression'' of the formula I previously proposed?
>
> (Ax)(Ay)[(x in N and y in N)implies x+y=y+x]
>
> Here, of course, N is the name for the element of the universe which is
the
> set of natural numbers.

Because in first order set theory there are non-standard models in which N
does not denote the natural numbers.
So your formula is not specifically about the real N, it is about the real N
or one of these other structures.

I have a post in the works (negotiating with the moderator!) which addresses
the question of what "expressiveness" of languages mean, and gives a fuller
story on the sense in which second order logic is more expressive than
first.

Roger

Dr. Matt Insall
http://www.umr.edu/~insall





More information about the FOM mailing list