Tuesday, June 20, 2006

Proof

There's an amusing back and forth (complete with little fables) going on between physicist Dave Bacon and computer scientist Scott Aaronson on their respective blogs. Both work on quantum information theory, and the argument appears to be an old one about physicists' intuition versus mathematical rigor. ("By the time you can prove it, the result will have been obvious to us for a generation" vs. "You guys are just guessing! Real men prove theorems".)

I'd like to add my opinion in the form of the following two quotes from Feynman (whom Schwinger remembered in an epitaph as "the outstanding intuitionist of our age"):

"We know a lot more than we can prove."

"Mathematics is to physics as masturbation is to sex."

I really only agree with the first quote, which, if you think about it, says something quite deep.

For our proof-obsessed brethren, I recommend the book Proofs and Refutations by Lakatos. How is it, exactly, that we "know" things? Can we ever be entirely sure that a given proof is error free? If not, how is it different from having only a probabilistic (e.g., confidence level) sense of truth?

It is their attempts to deal with unwanted and unexpected refutations - to preserve a valuable theory in the face of imperfect axioms and proof methods - that teach mathematicians the true depths of their conceptions and to point the way to new and deeper ones.

Lakatos shows this by an account of the historical development of the concept of proof in mathematics and by showing in historical detail how certain valuable 'proofs' were preserved in the face of refutation. To this point Lakatos shows that the 'proofs' of the truth of Euler's number are no proofs at all. The great mathematician Euler noticed that for any regular polyhedron the formula V-E+F=2 holds where V is the number of vertices, E is the number of edges and F is the number of faces. Euler's and his successors' proofs fall before any number of counterexamples. Does this prove that the theorem is 'incorrect?' Or does it mean... that their concept of what constituted a regular polyhedron was deficient. Lakatos shows how these conceptions were modified over a couple of hundred years as counterexample after counterexample were faced.

8 comments:

  1. Anonymous6:12 PM

    Clearly that must depend on what you define as "knowledge" or "to know".

    ReplyDelete
  2. Anonymous10:06 AM

    Steve,

    I liked the following article article, , particularly Atiyah's response.

    On a slightly different note,
    I think there have been two instances in the history where physics has led to things mathematicians did not know about.

    1. Gravtiation and Calculus.

    2. Modern Quantum Field Theory, especially the path integral.

    Most of the time, mathematicians are decades ahead of physicists; often physicists rediscover old math concepts(like linear algebra and QM, Riemannian geometry and GR, spinors and the Dirac equation, etc). But lately, the path integral of QFTs(numerous examples, instantons in Y-M and Donaldson theory, works of Witten on knot theory, Seiberg-Witten invariants from 4d N=2 SUSY duality, etc...) has changed all that.

    I think 'abstract' is also a relative term: Grothendieck' approach is more abstract than Atiyah's approach to solving problems. But in the abstract approach, on has to be really, really good(like Grothendieck), or one ends up with little to show for. An algebraic geometer, Miles Reid, wrote in one of his texts that Grothendieck's overly abstract approach(category theory based) stifled French mathematics research in algebraic geometry.

    A lot of abstract stuff is not very useful nor does it lead to surprising new insights or results, but some of it does, I think.

    MFA

    ReplyDelete
  3. MFA,

    I remember reading that article years ago. It caused quite a little kerfluffle; I was at Harvard at the time, where Jaffe is a professor.

    When you say there were only two instances in which physics "led to things mathematicians did not know about", I assume you mean specifically mathematical structures. Of course the two subjects have very different goals, and physicists are constantly discovering new things about the natural world that aren't of direct impact or interest to mathematics.

    It's worth noting that no one would ever have invented quantum mechanics were it not forced on us by nature. To a lesser extent, subjects like stat mech or mechanics also motivated all sorts of novel mathematical investigations.

    But my main point is that the notion of absolute certainty that some would like to associate with "proof" is illusory. It is not really clear what humans are doing when they "prove" theorems. We certainly aren't making purely axiomatic manipulations, so how confident can you be about the outcomes? (Or even about the assumptions themselves.)

    ReplyDelete
  4. Anonymous6:47 PM

    The great mathemetician Euler noticed that for any regular polyhedron the formula V-E+F=2 holds where V is the number of vertices, E is the number of edges and F is the number of faces. Euler's and his successors' proofs fall before any number of counterexamples.

    I thought that that identity was valid if the object was (in some precise topological sense which I forget now...been too many years) similar to a sphere.

    In which case the counterexamples would be things like a torus (viz, a polyhedral torus).

    Which really aren't counterexamples because I doubt Euler had those kinds of shapes in mind. Doesn't mean the counterexamples aren't interesting, but I'm skeptical that this consitutes some kind of refutation of Euler.

    ReplyDelete
  5. You can find some examples in the paper below of "monsters" (which are not at all monstrous) which violate the original Euler theorem, as well as a nice summary of Lakatos' point of view on proof in mathematics.

    http://garnet.acns.fsu.edu/~tan02/OPC%20Week%20Three/Priest.pdf

    (If the link doesn't work just Google "lakatos polyhedron proof".)

    ReplyDelete
  6. I don't know why that URL got chopped off... try again:

    PDF

    ReplyDelete
  7. Anonymous12:43 AM

    Interesting discussion, I remember reading Lakatos as UG, liked that book a lot, I also like his views on what he calls "research programs", which I find to be a much better description of science in progress, as opposed to an after-the-fact neat package (never was too impressed by the Popperian fairy tale as it is ususally told).

    As for the math/physics issue, I think things don't really divide along those lines. There are the intuitive approaches, and the formalists. The former may well include applied mathematicians, and the later may well include algebraic field theorists. The logical sequence in my mind is for a field to proceed first along intuitive lines, formalist attacks being only possible when the field is mature enough.

    ReplyDelete
  8. Anonymous10:10 AM

    Steve,

    Ah, I now see what you mean.

    Yes, there have been many examples of "no-go theorems" that have been proven wrong. However, as implied by you, it seems to me that if the proofs by modern mathematical standards are 'wrong', they are in a very subtle way and point to deep, new mathematical insights and structures. In that case, even if the proof is wrong, it is still very valuable. This is somewhat different from "probabilistic proofs" as in subjects like probabilistic number theory(e.g., primality testing), I think.

    And of course, proofs of certain theorems beyond the ability of a single person(like complete classification of finite simple groups) are another story...

    On the other hand, the same can be said of physics as well. Newtonian mechanics -->SR, QM etc... It is all about domains of validity, I suppose.

    Subtle point indeed.

    MFA

    ReplyDelete