FOM: Re: first order and second order logic: once more

[Roger Bishop Jones]

My take on the recent contribution from Martin Davis, Thursday, August 31,
2000 5:33 AM

> The fact that the valid sentences of second order "logic" is not r.e. is
> thus not just another property that happens to fail, it is a fatal flaw in
> the use of this validity as the basis of a reasoning system. The
> second-order logic of the textbooks amounts to first-order reasoning
> coupled with a strong second order comprehension principle. And the
> derivable sentences of this system do, of course, form an r.e. set.

This is only "fatal" if for some reason you want to import into the
definition of "a logic" the requirement that the logic be complete.
This is not a good idea.
We have a concise phrase for a "complete logic", but if the word "logic" is
construed as entailing completeness then we end up with an oxymoron when we
want to talk about "incomplete logics" such as second order logic.

A more reasonable use validity in the defining criteria of "a logic" would
be in a requirement for soundness.
I have no problem with the view that and unsound logic is not really a logic
at all.

> 2. Joe Shipman has indicated some of the set-theoretic cans of worms
opened
> when one considers full validity for second-order sentences. I want to add
> the remark that many open mathematical questions are equivalent to the
> validity of corresponding sentences of second-order logic. This includes
> Goldbach's conjecture, the twin primes conjecture, and the Riemann
> Hypothesis. Likewise the various combinatorial problems that Harvey
> Friedman has been showing require large cardinal assumptions for their
> proof are each also equivalent to such a sentence. Obviously this fact
> casts no particular light on these problems, but rather shows how
> intractable second-order validity is.

This is exactly as it must be in any language capable of expressing the
propositions of mathematics, for indeed your complaint seems to be simply
that the language is capable of doing this.

We know that any language capable of expressing the propositions of
arithmetic will have no complete deductive system.
This is not a problem which can be solved, and is not mitigated (except
perhaps for some metatheoretic purposes) by using languages which are
incapable of expressing these propositions.

> 3. In this last connection, it may be worth observing that the set of
> second-order valid sentences does not merely fail to be r.e.: it has a
very
> high degree of unsolvability, that of true arithmetic. Or stated in terms
> of the halting problem, to get its degree you must iterate omega times the
> operation ("jump") of forming the halting set for a Turing machine
> provided  with a given set as "oracle".

Which speaks again to the merits of second order logic.

Roger Jones

RBJones at RBJones.com