Subject: Re: Who's running your business?
From: Ben_Tilly@trepp.com
Date: Wed, 31 May 2000 14:36:27 -0400


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