Subject: Found! list of proof methodologies

         [Forwarded from the Stanford bboard by Laws@SRI-AI.]


I have received several responses to my request for proof techniques,
some with pointers, and some with actual "proofs."  But credit goes to
Greg Satz, who dug out of his jokes archive the list that I had in
mind.  The original author is someone named Dana Angluin, for whom no
professional association was given.

  [John McCarthy reports that Dana Angluin is now in the Computer Science
  Department at Yale, but probably compiled this list while a graduate
  student at UCB.  -- KIL]

There were a couple of references to the following work:

    Dunmore, Paul V., "The Uses of Fallacy", in R. L. Weber,
    @i{A Random Walk in Science}.  New York: Crane, Russak, & Co. Inc.,
    1973, p. 29.

The list of proof methodologies also appeared in SIGACT News, v15 #1
(Spring '83).

This contains a similar list of proof techniques.  I haven't looked it
up yet, but I'll report if I find anything of interest.

Here is [the conglomeration of what I've received so far]:
=======================================================================
Proof by example:
  The author gives only the case n=2 and suggests that it contains most
  of the ideas of the general proof.

Proof by intimidation:
  'Trivial.'

Proof by vigorous handwaving:
  Works well in a classroom or seminar setting.

Proof by cumbersome notation:
  Best done with access to at least four alphabets and special symbols.

Proof by exhaustion:
  An issue or two of a journal devoted to your proof is useful.

Proof by omission:
  'The reader may easily supply the details.'
  'The other 253 cases are analogous.'
  '...'

Proof by obfuscation:
  A long plotless sequence of true and/or meaningless syntactically related
  statements.

Proof by wishful citation:
  The author cites the negation, converse, or generalization of a theorem
  from the literature to support his claims.

Proof by funding:
  How could three different government agencies be wrong?

Proof by eminent authority:
  'I saw Karp in the elevator and he said it was probably NP-complete.'

Proof by personal communication:
  'Eight-dimensional colored cycle stripping is NP-complete' [Karp, personal
  commmunication].

Proof by reduction to the wrong problem:
  'To see that infinite-dimensional colored cycle stripping is decidable,
  we reduce it to the halting problem.'

Proof by reference to inaccessible literature:
  The author cites a simple corollary of a theorem to be found in a privately
  circulated memoir of the Slovenian Philological Society, 1883.

Proof by importance:
  A large body of useful consequences all follow from the proposition in
  question.

Proof by accumulated evidence:
  Long and diligent search has not revealed a counterexample.

Proof by cosmology:
  The negation of the proposition is unimaginable or meaningless.  Popular
  for proofs of the existence of God.

Proof by mutual reference:
  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.

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

Proof by picture:
  A more convincing form of proof by example.  Combines well with proof by
  omission.

Proof by vehement assertion:
  It is useful to have some kind of authority relation to the audience.

Proof by ghost reference:
  Nothing even remotely resembling the cited theorem appears in the reference
  given.

Proof by forward reference:
  Reference is usually to a forthcoming paper of the author, which is often
  not as forthcoming as at first.

Proof by semantic shift:
  Some standard but inconvenient definitions are changed for the statement
  of the result.

Proof by appeal to intuition:
  Cloud-shaped drawings frequently help here.

Proof by elimination of the counterexample:
  'Assume for the moment that the hypothesis is true.  Now, let's suppose
  we find a counterexample.  So what?  QED.' Used in theological arguments.

Proof by assumption:
  "For the last century no one acquainted with the facts has disputed ...
or:
  "I didn't look up the actual facts but since most people I know think
   this way, it follows that everyone else does too".

-------------------------------------------------

AP Calculus revisted (stolen from 1981 & 1982 Tep rush book)

(or Everything You Always Wanted To Know About Calculus,
but were afraid to pass)

Part one: Proof techinques

Proof by induction (used on equations with n in them.
Induction techniques are very popular, even the Army 
uses them.)

SAMPLE:  Proof of induction without proof of induction.

  We know it's true for n equal to 1.  Now assume that it's
true for every natural number less than n.  N is arbitrary,
so we can take n as large as we want.  
  If n is sufficiently large, the case of n+1 is trivially
equivalent, so the only important n are n less than n.
  We can take n=n (from above), so it's true for n+1 becuase it's
just about n.
        QED  (QED translated from the Latin as "So what?")

Proof by oddity
  SAMPLE: To prove that horses have an infinite number of legs.

Horses have an even number of legs.
They have two legs in back and fore legs in front.
This makes a total of six legs, which certainly is an odd number
of legs for a horse.  But the only number that is both odd and
even is infinity.  Therefore, horses must have an infinite number
of legs.

Topics is be covered in future issues include:
 
Proof by intimidation
	 gesticulation (handwaving)
	 overwhelming evidence
	 blatant assertion
	 definition
	 constipation (I was just sitting there and...)
	 mutual consent
	 changing all the 2's to n's
	 lack of a counterexample
	 elliptical reasoning
   bullet proof
   86 proof
   it stands to reason
   try it; it works
   proof by linear combination of the abve
      .... and many, many more


-----------------------------------------------------------------------

This is from _A Random Walk in Science_ (by Joel E. Cohen?):

  To illustrate the various methods of proof we give an example of a
logical system.

THE PEJORATIVE CALCULUS

Lemma 1.  All horses are the same colour (by induction).

Proof.  It is obvious that one horse is the same colour.  Let us assume
the proposition P(k) that k horses are the same colour and use this to
imply that k+1 horses are the same colour.  Given the set of k+1 horses,
we remove one horse; then the remaining k horses are the same colour,
by hypothesis.  We remove another horse and replace the first; the k
horses, by hypothesis, are again the same colour.  We repeat this until
by exhaustion the k+1 sets of k horses have been shown to be the same
colour.  It follows that since every horse is the same colour as every
other horse, P(k) entails P(k+1).  But since we have shown P(1) to be
true, P is true for all succeeding values of k, that is, all horses are
the same colour.

Theorem 1.  Every horse has an infinite number of legs.  (Proof by in-
timidation.)

Proof.  Horses have an even number of legs.  Behind they have two legs
and in front they have fore legs.  This makes six legs, which is cer-
tainly an odd number of legs for a horse.  But the only number that is
both odd and even is infinity.  Therefore horses have an infinite num-
ber of legs.  Now to show that this is general, suppose that somewhere
there is a horse with a finite number of legs.  But that is a horse of
another colour, and by the lemma that does not exist.

Corollary 1.  Everything is the same colour.

Proof.  The proof of lemma 1 does not depend at all on the nature of the
object under consideration.  The predicate of the antecedent of the uni-
versally-quantified conditional 'For all x, if x is a horse, then x is
the same colour,' namely 'is a horse' may be generalized to 'is anything'
without affecting the validity of the proof; hence, 'for all x, if x is
anything, x is the same colour.'

Corollary 2.  Everything is white.

Proof.  If a sentential formula in x is logically true, then any parti-
cular substitution instance of it is a true sentence.  In particular
then:  'for all x, if x is an elephant, then x is the same colour' is
true.  Now it is manifestly axiomatic that white elephants exist (for
proof by blatant assertion consult Mark Twain 'The Stolen White Ele-
phant').  Therefore all elephants are white.  By corollary 1 everything
is white.

Theorem 2.  Alexander the Great did not exist and he had an infinite
number of limbs.

Proof.  We prove this theorem in two parts.  First we note the obvious
fact that historians always tell the truth (for historians always take
a stand, and therefore they cannot lie).  Hence we have the historically
true sentence, 'If Alexander the Great existed, then he rode a black
horse Bucephalus.'  But we know by corollary 2 everything is white;
hence Alexander could not have ridden a black horse.  Since the conse-
quent of the conditional is false, in order for the whole statement to
be true the antecedent must be false.  Hence Alexander the Great did not
exist.
  We have also the historically true statement that Alexander was warned
by an oracle that he would meet death if he crossed a certain river.  He
had two legs; and 'forewarned is four-armed.'  This gives him six limbs,
an even number, which is certainly an odd number of limbs for a man.
Now the only number which is even and odd is infinity; hence Alexander
had an infinite number of limbs.  We have thus proved that Alexander the
Great did not exist and that he had an infinite number of limbs.

---------------------------------------------------------------------