Karsten Self wrote: > On Wed, May 31, 2000 at 09:26:40AM -0700, Crispin Cowan wrote: > > "Kevin S. Van Horn" wrote: > > > > > The purpose of doing a correctness proof generally isn't so that you can have > > > a nice stamp of approval on your code. Correctness proofs are most useful > > > when your code is, in fact, not correct... > > > > One of the better one-liners from presentations at this year's Oakland > > IEEE Symposium on Security and Privacy: > > > > "it is easier to prove a statement when it is true :-)" -- Jonathan > > Shapiro > > Good quote, but not strictly accurate. Proof by contradiction is a very > popular and powerful method. Certain statements (Fermat's Hypothesis > comes to mind) which may be true (and Fermat was eventually borne out) > are much more readilly proven if a counterexample can be shown. The > proof in the case of Fermat was decidedly non-trivial, and is far to > small to be included in the space remaining in this message <g>. Actually the original statement is reasonably accurate, and proof by contradiction is not a contradiction. It is generally much harder to prove false statements than it is true ones - whatever proof technique you use. The only common exception is when one so strongly expects the answer to be one thing that you are willing to accept a "proof" that actually isn't. Most proof's of God's existence are in this category. So likewise are many demonstrations that one's preferred style of politics/government/economics/etc is really The Right Way. On a more obscure note, remember the 2 envelope problem? (I have 2 envelopes with different numbers. I randomly hand you one, you open and look at it, then you hand it back. Do you have enough information to - with guaranteed better than even odds, correctly tell me whether I handed you the larger?) It is so obvious that the answer is "No" that people typically find it ridiculously easy to prove that. But the answer is "Yes" and most demonstrations to the contrary reveal interesting and non-obvious mathematical points. So the quote is sometimes wrong. But in general it is accurate. BTW haven't I mentioned to you that proof by contradiction hides more than it reveals? Use the contrapositive instead. (To show A => B, prove not B => not A. Both statements are equivalent to saying, "It is impossible for A and not B to both be true." so this is true.) If you cannot find a direct proof with that method, then you very likely should not have been using proof by contradiction! (It is amazing how much clearer student's proofs become if they are taught to avoid proof by contradiction! Frequently students manage to take direct proofs, wrap it up in a proof by contradiction, and the only thing they accomplish in so doing is creating confusion for themselves.) Cheers, Ben