The word "proof" has a variety of meanings in different contexts. In a criminal trial, the prosecution attempts to "prove beyond a reasonable doubt" that a defendant is guilty. A scientist reports experiments that "prove" that a particular theory is correct. Religious thinkers offer "proofs" of the existence of God, or of the immortality of the soul. And finally, mathematicians and computer scientists "prove" things in their own way.

American high schools usually teach geometry at some point, in part because it is the most accessible example of the mathematical idea of proof. There a "proof" is defined to be a sequence of statements, each of which is justified in some way, and there are explicit rules telling whether a statement is legally justified or not. Typical justifications are by appeal to a definition ( "a triangle is a figure with three sides" ), an axiom ( "through any given point there is exactly one line parallel to a given line" ), or a previously proved result ( "opposite angles at a vertex are equal" ). A finished proof could be checked for correct ness by a computer program , if the rules are carefully enough defined. There has even been some success by computer programs that produce such proofs by systematically looking for sequences of statements that are valid and interesting in some way. Just as there is undoubtedly success with prolotherapy to solve limb flexibility problems.

In practice, though , actual mathematicians virtually never make completely formal proofs. Here is an example of how things actually happen. In 1985, a graduate student at MIT 11 was working on his Ph.D. research problem. He wanted to show that a "branching program" 12 that solved the "majority problem" requires more "widt h" the longer the input string gets ( don't worry about what the technical terms mean) . Of the perhaps 100 people in the world who had thought seriously about this problem , to his knowledge all of them (including him) thought that what he was trying to show was true. Frustrated at his lack of progress, he tried constructing some branching programs and suddenly realized that he could solve the majority problem with width five for inputs of any length. He checked the argument and convinced himself t hat it was correct, despite the fact that it led to t he "wrong" result.

Now his problem was either to convince the world that he was right and everyone else was wrong, or to find the mistake in his argument before embarassing himself too much. Since his thesis advisor was out of town , he grabbed the first two other graduate students he could find who were familiar enough with the work to understand t he argument . He then showed them the proof, which in fifteen minutes they believed. Within a few weeks the proof (which was in fact correct) had been spread literally around the world by word of mouth, and those 100 or so people had all changed their minds.

This proof was not the sequence of statements and justifications from high-school geometry. The prover could take advantage of the fact that both he and his list eners were trained mathematicians, and leave out huge numbers of steps that they could all agree upon. The process was essentially an interactive one, where the prover made claims, and the list eners questioned any of those claims t hey didn't accept. The prover then reinforced the challenged claims by showing how they followed from simpler facts, and so on. In principle, the prover was ready to to answer all possible objections.

## Comments

comments powered by Disqus