FOM: ``Reduction'' of Second-Order Logic to First-Order Logic ... Re: Fri Aug 25 10:09:25 2000 ... R.B. Jones

[Matt Insall]

Roger Bishop Jones Stated:
the true
sentences of first order logic are recursively enumerable


Matt Insall Responds:
I think this is misleading.  It is the case that the Gödel-Henkin
completeness theorem shows that the universally valid sentences of
first-order logic are provable, using a (reasonable) specific deductive
system (or more completely, a specific collection of deduction systems).  It
is also the case that at least one such deduction system includes only
computable rules of inference, and that is enough to show that the set of
universally valid first-order sentences is recursively enumerable.  However,
in both first-order logic and standard second-order logic, what one is
typically interested in is satisfaction, not universal validity.  Now I am
not familiar with Manzano's book in particular, but I am aware that standard
second-order logic does not satisfy the compactness theorem, and hence it is
either inconsistent or incomplete.  If it is inconsistent, then every
statement is provable, and the question of which system is ``better'' is
then answered.  If it is incomplete, which I believe to be the case, for I
am convinced that second-order logic is consistent, then it is in a similar
situation to the first-order theory of arithmetic, which is, of course,
consistent (my Platonism is showing again, I guess), but incomplete.  Thus,
the only conclusion you should reach by your, shall I say ``cryptic'',
comparison between first-order logic and second-order logic should be that
at best, any such reduction that Manzano performs cannot make second-order
logic ``equivalent'' in any reasonable sense to first-order logic.  In fact,
on an intuitive level, I expected a proof that second-order logic could be
reduced to some part of first-order logic from the following observation:
Any model of second-order logic is an element of the class of all sets,
which is a model of the first-order theory ZF, and using the superstructure
approach that is available in nonstandard analysis, one may convert any
second order problem into a first-order problem.  This is in fact a major
part of what makes nonstandard analysis ``tick''.  Now, I am not yet sure
how to see that a reduction of all second-order problems can be in some
sense ``simultaneously'' converted into first-order problems, much less
``effectively'' as they say (or more precisely, using a Turing-computable
function), but if she (Manzano) claims to have performed this task, I do not
see that your argument is a clear reason to reject her claim without reading
the book.

I see that in the end of your response to Professor Simpson's remarks, you
have (perhaps a bit obliquely) objected to non-standard models, to which I
have essentially referred by mentioning non-standard analysis.  Let us
consider that objection.  It is well-known that the existence of
non-standard models of analysis is guaranteed by the axiom of choice (in
fact, only the boolean prime filter theorem is needed), so your objection
amounts to an objection to AC.  This is fine, I guess, even though much of
mathematics now accepts the axiom of choice and ``lives with'' the
consequences, such as the existence of nonmeasurable sets.  But recall that
as long as ZF is consistent (i.e. if there is a ``standard'' model of
analysis), so is ZFC, and it follows that there are non-standard models of
analysis (contingent as this may be on the consistency of ZF).  Thus, your
objection to non-standard models for the purpose of such a reduction appears
to me to reduce to an objection to ZF.

I guess that I should admit that I have not written out detailed arguments
that the relative consistency of ZFC implies that second-order logic is, in
a reasonable sense, ``reducible'' to (perhaps only a fragment of)
first-order logic, but I guess I am conjecturing (a bit late, perhaps) that
that is the case, based upon some intuitive observations (above) about the
relationships between ``standard'' and ``non-standard'' analysis.  I suggest
that the existence of the desired ``reduction'' is at least analogous to the
existence of non-standard models within any standard universe.





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