FOM: agreements and remarks

[Shipman, Joe x2845]

We've had a lot of excellent postings in the last couple of days!
I want to respond to them all in one place, before getting to two 
positive postings of my own (a short one on CH and a long one on 
"F.O.C.S. and F.O.M. are the same subject" [the title is provocative 
but I will argue that if they are not the same they are much closer 
than many of us expect]).

To Detlefsen, Machover, and Davies:  I don't mind witnessing boxing 
matches, even if they are terrible mismatches, since there is no real 
blood in cyberspace.  But I respect the feelings of those who are 
offended by insulting vituperation and worry that they may be turned 
off, and don't think that stomping on those who say silly things is as 
necessary to police the quality of the postings as Harvey does, so I 
agree that the level of invective should be a couple of notches 
milder.

To Machover and Feferman: Yes, the key attribute of mathematics is 
that it is objective without being about (physically existing) 
"objects".  I'm not so sure I would like to exclude games like Chess 
from "mathematics", because I'd like to preserve the above 
characterization of mathematics which does include chess, go, etc.
There is an extremely interesting distinction here, though.  In 
chess, there are some assertions such as "If you remove Black's 
Queen, the initial position is a forced win for White" which are held 
with a degree of certainty comparable to the certainty we have about 
very straightforward mathematical theorems [if not Euclid's theorem 
then, say, the Prime Number Theorem], but nothing approaching a 
mathematical proof even though the assertion is obviously equivalent 
to a mathematical one of a low type.  Whence this certainty, and is 
there any hope of transforming it into a real mathematical proof?

To Cook:  Thank you for reminding us that we KNOW at least one of the 
inclusions LOGSPACE <= P <= NP <= PSPACE is proper but are at an 
impasse in showing any of them are.  I also agree that the informal 
identification of "feasible" with P is justified by the nonexistence 
of "natural" P-problems with high exponents.

To Davis: Yes, majority rule is a very poor proxy for proof!  And I 
agree with you (contra Cook) that non-NP-complete problems have 
limited analogical value for NP-problems.  The key feature of 
NP-complete problems is their lack of structure, factoring 
polynomials over the rationals on the other hand has lots of 
structure.  This doesn't contradict my previous paragraph accepting 
"feasible = P" because this is a PROVISIONAL identification; it 
should not be used to discourage trying to prove P = NP! If 3-SAT
(to fix a favorite NP-complete problem) has an O(n^1000) algorithm 
then we can reject the identification.  I disagree with you here that 
such a situation would not be philosophically important -- even if
NP-complete problems were INfeasibly in P, this would establish the 
fundamental truth "Brute force is *essentially* inefficient", because 
of the huge gulf between O(n^1000) and O(2^n).  And while I like the 
Hartmanis quote that "God would not be so cruel" as to allow this, I 
don't see why requiring 2^n steps to solve 3-SAT in general is any 
less cruel!

To Harvey: Yes, establishing SAT not in O(n^2) is an essential 
prerequisite for further progress.  Interestingly, this was the way 
Godel formulated the P-NP question in a 1956 letter to Von Neumann 
(see Dawson's book "Logical Dilemmas")--if satisfiability were 
recognizable by a Turing Machine in n^2 operations, all practical 
mathematical reasoning could be mechanized despite the incompleteness 
theorems.  (I imagine Godel had in mind that you could effectively 
tell whether axioms X gave a proof of theorem Y of length Z within 
Z^2 steps and find the proof--of course the constants might be so 
horrible that even an O(n^2) algorithm was impractical).

To Franzen: No, Leibniz'z dream (as ably propounded by Detlefsen) is 
of extreme "G.I.I.".  Among other things, it provides a compelling 
positive political role for FOM (as opposed to the negative PoMo 
attitude--I agree with Barwise and others that the less of that 
post-modernism on FOM, the better).  And by the way, thanks to Harvey 
for the posting putting GII in perspective--the Leibnizian 
"foundational studies project" is very exciting.

To Tait and Barwise: Yes, the "unreasonable effectiveness" of 
mathematics is somehow linked to its 
objectivity-in-spite-of-being-socially-constructed.  And the concept 
of "pattern" links mathematics, the physical world, and society 
(needed to recognize patterns) very nicely.

To Tragesser: Thanks for raising the issue of "geometric reasoning".  
This is a deep and important question.  What *IS* geometric 
reasoning, and why does it seem necessary (in the sense that we need 
to use it to arrive at results, not the logical sense)? It still 
seems fair to require arithmetizability before a piece of geometric 
reasoning is officially accepted (and this is notoriously difficult 
to do--examples which come to mind include the work of Thurston in 
3-manifold theory, if I understand the situation correctly, and on 
the negative side the withdrawn "proof" of the optimality of the 
standard 3-D sphere packing), but what's going on before that stage?

To everyone discussing "independence and uniqueness of 
axiomatizations":  I find it hard to get excited about this.  Why 
should we care if axioms are independent of each other?  The "walled 
cities" vision of mathematics seems untenable anyway, we already know 
that it turns out differently, with the connections between different 
mathematical cities being absolutely essential for progress in the 
long run.  What area of mathematics has not benefited from 
connections with other areas over and over again?

To Tennant and Kanovei:  No, the genetic propensities for various 
types of craziness has not been bred out because prophets are sexy or 
societies need to break up.  They are there because you can't (in the 
crude process of evolution by random mutation and natural selection) 
get geniuses without getting crazies as well.  The autistic savants 
show us this.  I know children whose development followed a path that 
could have ended in either autism or genius, and for a while npbody 
knew which.  The childhood and adult personality traits of figures like 
Einstein (who didn't talk until age 3), Godel, Wiener, Bill Gates (who I 
hasten to add I do not regard as a SCIENTIFIC genius but who 
unquestionably has a very extraordinary mind), Bobby Fischer, and so on 
also show us this.  And I am not even mentioning all the brilliant thinkers
of great accomplishment who actually did go crazy (I should mention that 
according to Dawson Godel had several psychotic episodes of 
significant duration). 

-- Joe Shipman