com Henry Cate How to prove

Found at: 0x1bi.net:70/textfiles/file?humor/proof.met

From cate3.osbunorth@xerox.com Fri Aug 31 19:33:53 1990
From: cate3.osbunorth@xerox.com (Henry Cate III)
Subject: How to prove something


Survey of proof techniques

This survey was written by Dana Angluin.  Not really sure where it came from.

  The author gives only the case n=2 and suggests that it contains most
  of the ideas of the general proof.


  Works well in a classroom or seminar setting.

  Best done with access to at least four alphabets and special symbols.

  An issue or two of a journal devoted to your proof is useful.

  'The reader may easily supply the details.'
  'The other 253 cases are analogous.'

  A long plotless sequence of true and\or meaningless syntactically related

  The author cites the negation, converse, or generalization of a theorem
  from the literature to support his claims.

  How could three different government agencies be wrong?

  'I saw Karp in the elevator and he said it was probably NP-complete.'

  'Eight-dimensional colored cycle stripping is NP-complete [Karp, personal
  'To see that infinite-dimensional colored cycle stripping is decidable,
  we reduce it to the halting problem.'

  The author cites a simple corollary of a theorem to be found in a privately
  circulated memoir of the Slovenian Philological Society, 1883.

  A large body of useful consequences all follow from the proposition in

  Long and diligent search has not revealed a counterexample.

  The negation of the proposition is unimaginable or meaningless.  Popular
  for proofs of the existence of God.

  In reference A, Theorem 5 is said to follow from Theorem 3 in reference B,
  which is shown to follow from Corollary 6.2 in reference C, which is an
  easy consequence of Theorem 5 in reference A.

  A method is given to construct the desired proof.  The correctness of the
  method is proved by any of these techniques.

  A more convincing form of proof by example.  Combines well with proof by

  It is useful to have some kind of authority relation to the audience.

  Nothing even remotely resembling the cited theorem appears in the reference

  Reference is usually to a forthcoming paper of the author, which is often 
  not as forthcoming as at first.

  Some standard but inconvenient definitions are changed for the statement
  of the result.

  Cloud-shaped drawings frequently help here.


Henry Cate III
  (ucbvax!xerox.com!cate3.osbunorth)  OR  (cate3.osbunorth@Xerox.Com)
Everyone complains of his memory, no one of his judgment.