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

[Roger Bishop Jones]

Responding to Matt Insall's message dated Tuesday, August 29, 2000 5:57 AM

>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.

I have no idea why you think that "satisfiable" is a more appropriate
interpretation of the word "true" than "valid".
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.
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.

>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.

My observation still seems to me both crystal clear and true.
By constrast '"equivalent" in any reasonable sense' is as clear as mud, and
has little relevance to the point which I was making.

>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 have not rejected any claim by Manzano.
I have simply made a true observation about the non-existence of a certain
kind of reduction from second order logic to first.
Your observations above cast no doubt upon that observation.
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.
If you were successful in disproving my claim after those two admissions you
could then prove "false".

>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.

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

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.

Incidentally, I am not aware that there is any useful connection here with
non-standard analysis.
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", 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.

<snip> closing:
>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 have no objection to AC or to ZF and nothing I have said implies or is
predicated on such an objection.

Roger Jones