FOM: agreements and remarks
Shipman, Joe x2845
shipman at bny18.bloomberg.com
Mon Dec 22 15:34:34 EST 1997
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
More information about the FOM
mailing list