FOM: Re: ``Reduction'' of Second-Order Logic to First-Order Logic

[Matt Insall]

Roger:
> I have no idea why you think that "satisfiable" is a more appropriate
> interpretation of the word "true" than "valid".

Matt:
I don't.  I said, ``what one is typically interested in is satisfaction, not
universal validity''.
Where did you get the idea that I was interested in ``interpreting'' the
word ``true'' as
``satisfiable''?


Roger:
> If others had thought so presumably the rules of inference for first order
> logic would have been engineered to demonstrate all satisfiable sentences
> and Godel's completeness result would then have been quite a different
> theorem.


Matt:
If others had thought what you claim I think, then you may be right.  The
completeness results show that not only are all valid sentences
demonstrable,
but also that for any theory T (recursively enumerable or not), any
consequence
of T is provable from T.  But I did not say what you claim I said.  What I
said
had to do with satisfaction, which in turn is related naturally to the
notion of a
consequence, which is not exactly captured by any currrently accepted notion
of ``effectiveness'' that I can recall.


Roger:.
> I don't myself think this would have been an improvement, but I suspect it
> would have in any case have made no difference to my point, since I would
> guess that the satisfiable sentences are also recursively enumerable.


Matt:
The point is that not all consistent sets of first-order sentences are
recursively enumerable.
Thus some consistent set of first-order sentences may very well be a
reasonable replacement
for the set of all universally valid second-order sentences.  (As I intended
to indicate before,
it remains to make clear what is meant by ``be a reasonable replacement''.
This remains to you,
I guess, as clear as mud.  I will not disagree.)


Roger:
> My observation still seems to me both crystal clear and true.


Matt:
Your objection to Professor Simpson's comment was based upon a distinction
between
reductions and ``effective'' reductions.  However clear it may be, and
however true it may
be, it seems not to address the situation reasonably.  What I suggest is
that we do not
only concern ourselves with recursive sets of formulas in first-order logic,
so the suggestion
that a ``reduction'' of second-order logic to first-order logic is not
(insert your own synonym
for ``valuable'' here) unless it is ``effective'' is, IMO, misleading.  That
there is a reduction
is not as great a surprise as some may think, and that it cannot be
``effective'' (assuming
Church's Thesis) is, as you pointed out, no greater surprise.  (Of course,
those who do
not hold to Church's Thesis would probably not be convinced there is no
effective reduction.)


Roger:.
> By constrast '"equivalent" in any reasonable sense' is as clear as mud,
and
> has little relevance to the point which I was making.



Matt:
Let us take ```equivalent'' in any reasonable sense' to have your apparently
intended meaning,
namely, let us say that logic systems S1 and S2 are ``equivalent in a
reasonable sense'' if there
is an effective reduction of S1 to a subsystem of S2 and there is an
effective reduction of S2
to a subsystem of S1.  It seems to me that there is an effective reduction
of first-order logic to a
subsystem of second-order logic (the identity mapping?).  I am not sure if
there is an effective
reduction of second-order logic to a subsystem of first-order logic.
Apparently, though, there is a
reduction of second-order logic to a subsystem of first-order logic.


Roger:
> Your observations above cast no doubt upon that observation.



Matt:
Why should I cast doubt on a trivial observation?  Notice that since, as I
observed,
second-order logic fails to satisfy the compactness theorem, whereas
first-order
satisfies the compactness theorem, the kind of reduction you expect is not
to be had,
merely on the grounds that it (and its inverse) would necessarily preserve
compactness.  Why
invoke
``recursive set of formulas'' or validity at all?  Clearly no one would
claim to have the
kind of reduction you are describing from second-order logic to first-order
logic,
or the other way round, for that matter.



Roger:.
> That you doubt my claim is deeply puzzling to me since you seem to have
> accepted that the valid sentences of first order logic are indeed
> recursively enumerable and that those of second order logic are not.



Matt:
It is not your claim that I doubt, by any means.  It is your use of it to
(apparently)
cast doubt on the value of a result because it does not satisfy your
overstringent
criteria for a ``reduction''.  As far as I can tell, the ``reduced'' version
of second-order
logic obtained by Manzano need not even be a ``standard'' subsystem of
first-order
logic, but who cares?



Roger:
> I offered and have no objection to "non-standard models".




Matt:
I will quote from your earlier post, to which I referred when I said you
``perhaps obliquely'' objected to non-standard models:

``I guess from your comment that (you or) Manzano considers non-standard
models "appropriate", but this is a significant variation in the semantics
of second order logic.''

Why is it a ``significant variation in the semantics of second order logic''
to
``consider non-standard models ``appropriate'' ''?  (BTW, Does not the way
you stated this at least suggest that you do not consider non-standard
models
appropriate?)  What does the opinion of either Professor Simpson or
Professor
Manzano have to do with the semantics of second-order logic?  If the non-
standard models exist, then they are ``appropriate''.



Roger:
> My point was simply that second order logic, when its semantics is defined
> allowing non-standard models, is a different language to second order
logic
> when its semantics is defined allowing only standard models, and that a
> meaning preserving reduction of the one language to first order logic will
> not serve to reduce the other.


Matt:
Is your concept of ``semantics'' for ``standard'' second-order logic
essentially the same as can be found on page 269 of Enderton's ``A
Mathematical Introduction to Logic''?  The resulting second-order logic
system is referred to, on page 286 of the same text, as ``absolute''
second-order logic.  Thus, it pre-supposes a *given* model (X,E) of
(first-order) set theory in which the symbols of your second-order language
are elements, as are all the structures you desire to study with your
second-order logic.  Your notion of satisfaction is a relation on X, and
your notion of effectiveness is (according to Church's Thesis) an analogue
of ``recursive function in the first-order universe (X,E)''.

Roger:
> In particular the use of the term "non-standard model" in that context
means
> something like "non-standard model of the first order theory of real
> numbers"


Matt:
Not when you do analysis on superstructures.  (See either Hurd and Loeb's
book or Albeverio, et. al.)  In this case, let A be any set of urelements.
The superstructure (X,E) on A is constructed as follows:
A_0=A,
A_1 is the union of P(A_0) with A_0,
...,
A_{n+1} is the union of P(A_n) with A_n,
...

(Here, P(x) denotes the power set of the set x.)  The set X is the union of
all the A_n, and E is the membership relation on X.  In particular, if A is
the set R of real numbers, then every finitary relation on R is a member of
X, and the first-order language of set theory ``sees'' (X,E) as a model
which satisfies certain first-order axioms.  Included in these axioms is
enough information to do all of second-order analysis on R.  This is what
makes non-standard analysis ``tick''.  Of course, one can do what you speak
of, namely non-standard first-order analysis on R, but that is not the only
power of non-standard analysis.




Roger:
, whereas my use of the term "non-standard model" was intended to
be
> understood as "non-standard model of second order logic", which is
something
> else altogether.


Matt:
Now, I get the impression you are referring to what Enderton calls ``general
second-order logic'' which satisfies the compactness principle.  This is, in
an abstract sense, the same thing needed for the existence of first-order
nonstandard models of second-order analysis on the reals.  In fact, on page
287 of Enderton is a discussion of the use of the compactness principle to
construct nonstandard general models of second-order analysis.  This is a
form of nonstandard real analysis in which the basic language is a general
second-order language.  I realize now that this is what you were referring
to when you said the semantics is ``different'' when non-standard models are
``allowed'', but do you see now at least some of my point?  Basically,
``standard (absolute) second-order analysis can be accomplished within
first-order set theory''.  This should really be no surprise, for many
mathematicians have long treated all of mathematics as first-order set
theory.

Roger:
> I have no objection to AC or to ZF and nothing I have said implies or is
> predicated on such an objection.
>


Matt:
Okay.  I guess that we are closer to the same page on some topics, but we
remain a bit distant from one another on others.  There are other reasons I
consider second-order logic to gain essentially nothing over first-order
logic.  (But I do not, by any means, intend to imply that second-order logic
is useless.  En contraire, quite a bit of mathematics is just easier to
understand if we do not reformulate it in first-order terms.)  Let (X,E) be
the model of set theory in which you live.  In my model of class-set theory,
X is a set.  Your ``standard'' (or, as Enderton says, ``absolute'')
second-order logic has models which are elements of X.  In my universe, I
construct a superstructure using a set of urelements which is in one-to-one
correspondence with your entire universe as the initial set of urelements.
I then have a first-order model which can do all of your second-order model
theory without a second-order language.  This is what I meant when I said it
was no surprise that there is a ``reduction'' of second-order logic to
first-order logic.  Of course, since I do not care much about
``effectiveness'' once we start talking about an entire logic system that is
either inconsistent or incomplete, I said in my previous post on this
subject that your reply about how the lack of an ``effective'' reduction of
second-order logic to first-order logic followed from the fact that the
universally valid sentences of one system were recursively enumerable but
those of the other system were not recursively enumerable was misleading.
The point was that you were denying the very existence, IMO, of the
intricacies of the semantics of first-order logic by ignoring all
non-recursively axiomatizable theories, including those which can encode all
of second-order logic, both its syntax and its semantics.






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