February 10, 2006
Stanford mathematician Keith Devlin, a.k.a. National Public Radio's 'Math Guy,' explains the changing nature of mathematical proof
By Dawn Levy
Keith Devlin is a consulting professor in Stanford's Mathematics Department and a fellow of the American Association for the Advancement of Science. Some biologists recognize his name because there's an extinct possum named after him, but most people know him as "the Math Guy" on National Public Radio's Weekend Edition, where he explains the math behindamong other thingswhy giving an extravagant gift of no lasting value, such as an expensive meal, will maximize the success of a budding romance.
So now you know a bit about a mathematician. But on Feb. 18, at the annual meeting of the American Association for the Advancement of Science (AAAS) in St. Louis, Devlin will reveal how mathematicians know what they know. He begins his talktitled "What Do Mathematicians (Usually) Mean by Proof?"with a clip from the movie Proof, about a brilliant but mentally ill mathematician, played by Anthony Hopkins. Devlin's talk is part of a symposium, "Paradise Lost? The Changing Nature of Mathematical Proof," that includes Michael Aschbacher of the California Institute of Technology, Thomas Hales of the University of Pittsburgh and Steven Krantz of Washington University.
"Mathematics was built on this comforting idea, of truth being established by proof, that was around for 2,000 years," Devlin said during a recent interview. "Then, in the second half of the 20th century, several major results were proved by methods that challenge that, and as a result we've had to reassess what we mean by proof."
The old way of proving mathematical truths
"Intuitively, the idea of a proof is it's just a verification of something," Devlin explained. "In experimental science, you verify truth by performing an experiment. In mathematics, you sort of perform a thought experiment. You actually come up with a logical argument that establishes a truth. So it's a little bit like establishing guilt in a court of law, except that the rules are a little bit different and the degree of accuracy is incredibly higher in mathematics."
The first known mathematical proofof the Pythagorean theoremgoes back to about 1,000 B.C.E. Today, evidence of it can be seen in diagrams and symbols etched on a Babylonian tablet.
Proofs begin with axiomsan initial collection of facts or assumptions that are taken as "given." Axioms are often assumed without mention, but mathematicians have learned over the centuries that it is important at some point to make them explicit. For example, in his textbook Elements, written around 350 B.C.E., Greek mathematician Euclid wrote down five axioms for plane geometry. People used Euclid's axioms for 2,000 years before German mathematician David Hilbert noticed that many of Euclid's proofs assumed other axioms he had not written down. In the late 19th century, Hilbert supplied the missing axioms.
"Euclid's arguments were correct, but they weren't logically complete because there were assumptions he was using, but he didn't realize he was using them," Devlin said. "He just thought these things are obvious that actually aren't obvious."
Proofs also require specified rules for making single-step deductions. Aristotle developed a form of deductive reasoning called syllogism that allows a conclusion to be deduced from two given statements. For example, "All men are mortal" and "Socrates is a man" yield "Socrates is mortal."
In his talk, Devlin will demonstrate Euclid's formal proof showing the existence of an infinite number of prime numbers. In the demonstration, Devlin reveals what mathematicians always do in practicefor all but the simplest proofs, they omit the steps that they regard as obvious to the intended audience. "If we did not do that, most proofs would become too long and detailed to read," Devlin said. In principle, mathematicians can fill in all the missing steps.
In essence, a proof is a challenge to the audience to try to show that an argument is wrong. Explained Devlin: "I'm saying, 'If you don't believe this, it's up to you to challenge it.' And then I'll have come to your challenge and we'll have this duel, and eventually you will give in and say, 'OK, I accept it.'"
The nature of proofs makes mathematics by far the most reliable kind of knowledge we have, Devlin said. "In mathematical proof, if you can find one errorjust one errorthat I can't correct, then the whole proof falls down. If a bridge falls down or a satellite fails to go into proper orbit, it won't be because mathematical knowledge is insecure; the physics and engineering rest on far less certain knowledge."
Nonetheless, mathematical truth is no longer a "100 percent pure product," Devlin said. The idea of a proof as being an argument that convinces another person took a major hit in 1976, when Kenneth Appel and Wolfgang Haken of the University of Illinois solved a famous problem asking the minimum number of colors required to color a map so that no two regions that share a border have the same color. The proof of the solutionfourused a long computer analysis of configurations of map regions. There were so many analyses and calculations that no one person could check them all in a single lifetime. Therefore, the validity of the proof depended on believing that the computer program did what its authors claimed and that the answer it obtained was correct. Because computers were relatively new at the time, mathematicians debated the acceptability of the new proof. Today, the Appel-Haken Four Color Theorem is fully accepted.
The idea of a proof as an argument that will convince another mathematician suffered another blow with the completion, around 1980, of the purported proof of the Classification Theorem for Finite Simple Groups. This theorem is at the heart of group theory, a subject that has important applications in physics, chemistry and cryptography, as well as in mathematics itself.
"The problem with the proof was, and remains, its length," Devlin said. "No one has ever written it down in one place, but it is estimated that it would be around 10,000 pages long. The result was the result of hundreds of contributors, working over many years, many of them who never met each other. The experts working in that area finally agreed that the result had been proved when they judged that spread out over hundreds of different published papers was, in essence, a complete proof. If they are correct, then there does exist in the world a proof, and different humans have readand agreed to the correctness ofdifferent parts of the proof, so we are not relying on computers. But no one has written down, much less read, the entire proof."
Devlin said that raises an interesting question: "Would we say that something was a novel if no person could ever read it?"
It also causes problems for peer-reviewed journals, whose editors end up publishing what Devlin calls "proof by hearsay." When AAAS speaker Hales wanted colleagues to check his posited proof that the most efficient configuration for packing oranges was the pyramid, he put it up on the web for scrutiny. His argument, which addresses a problem first posed by Kepler and so is known as the Kepler conjecture, consists of hundreds of pages of standard mathematics and massive computer calculations. The editor of Annals of Mathematics, the most prestigious journal in the field, invited Hales to submit the paper and assembled a dozen of the world's experts to check the work. They labored four years but didn't find any uncorrectable errors. They were 99 percent sure Hale's sphere-packing theorem was correct, they told the editor. But they couldn't be 100 percent certain.
Recalled Devlin: "They did publish it, and the editor wrote [a preface] saying, 'This is something new. We've put it through the refereeing process. This has probably been subjected to more refereeing scrutiny than almost anything else, and they can't find anything wrong with it. But on the other hand, no one can say it's for sure correct.'"
While the definition of a proof hasn't changed, Devlin said, what has changed is the basis for determining a claimed proof is correct. "At the end of the day, in practice what's going on is a community that's certifying. To anyone in any other profession, this would be taken for granted. But for mathematicians, it has been a hard pill to swallow."
Devlin is speaking in two sessions. On Feb. 18 from 9:45 to 11:15 a.m. Central Time, he is moderator and a speaker in the symposium "Paradise Lost? The Changing Nature of the Mathematical Proof." His talk is titled "What Do Mathematicians (Usually) Mean by Proof?" Also on Feb. 18, at 1:00 p.m. Central Time, he is a participant in the press briefing "Mathematics in Fact and Fiction," held in Room 274, second floor, of American's Center. A photo of Devlin is available on the web at http://newsphotos.stanford.edu.