FOM: first order and second order logic: once more

[Martin Davis]

To add to Joe Shipman's salient remarks:

1. Lost in the discussion is the original notion that logic has to do with 
inferences, that a system of logic should provide a means of proceeding 
from given premises to an appropriate conclusion. Thus, if a practitioner 
of a particular logical system claims that conclusion B follows from 
premises A1,....An the system should provide, as  the evidence (sufficient 
reason) for this claim, a proof or, one may say, a derivation. Moreover, if 
the proof is to be convincing there should, at the least,  be an algorithm 
by which a doubter can verify that the alleged proof really is one 
(according, of course, to the rules of the logic). Invoking Church's thesis 
this implies that the sets of pairs ((A1,...,An),B) for which this relation 
holds is an r.e. set.

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.

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.

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

None of this is at all novel, but in the light of ongoing discussion, I 
though these remarks worth making.

Martin




                           Martin Davis
                    Visiting Scholar UC Berkeley
                      Professor Emeritus, NYU
                          martin at eipye.com
                          (Add 1 and get 0)
                        http://www.eipye.com