Conference turris::womannotes-v2

241.0. "Proof Techniques" by WMOIS::B_REINKE (As true as water, as true as light) Tue Oct 11 1988 23:43

This list of 'proof techniques was entered first in Human_Relations.
    I'm copying it here with permission of the previous enterer..
    
    This reminded me so much of when I was taking in Biology and
    Chemistry courses in college and grad school...I swear we
    all used every one of these techniques in writing papers,
    lab reports and exams.
    
    
    Bonnie
   --------------------------------------------------------------------    
    The list is credited to a "Dana Angluin".
    
    
    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 communication]
    
    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 convncing 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."
    
    
    I'd like to add my own favorites:
    
    Proof by repitition
    	Just reply to counter-arguments with a repeat, word-for-word, of
    	your original assertion.  Works well with proof by exhaustion
    	(substitute 200-line reply for "issue or two of a journal".)
    
    Proof by personal experience
    	"This happened to me, thus it must happen to everyone."

    And then there's:
    
    Proof by majority opinion
       "It must be true; everybody knows it."
    
    Proof by citing practical purposes
       "Since we can only see a limited distance from the Earth in any
        one direction, and we can see the same distance in any direction,
        for all practical purposes, the Earth is at the center of
        the universe."
    
    Proof by superior example
       "The Boss said it was so in his memo."
    
    Proof by nit-picking
       (Popular in Notes!)  Jump on small errors of dissenters, thereby
       casting a negative pall over their entire negative reply, and
       claim victory, since "They are mistaken, as you can all see."

    Dana Angluin  is  a  (associate?) professor of Computer Science at
    Yale.  She's  one of the warmest most helpful people I've run into
    as  well  as one of the smartest.

    To explain  some  of  the jokes, Richard Karp is one of two people
    who  really  defined the idea of NP-completeness (along with Steve
    Cook.)

    I believe  this  was  first  published in the SIGACT (Automata and
    Computability Theory) newsletter.


--David

    
    And proof by supposition
        Usually stated as "you probably think"......

    Proof by fantasy
    	This is where you invent a situation, state how you think your
    	opponent would act in the mythical sytuation, and then use
    	your conclusion to show how your opponent is wrong about
    	everything.

    
    When my younger brother, the economist, was in graduate school, he
    was great for using statistics to prove his points - no matter the
    subject.  It took quite awhile before I caught on to the fact that
    he was making them up.  When I called him on it, he laughed and
    said that virtually no one qestions statistics.  I suspect he's
    right.
    
    Polly  

But, didn't you already know that 67.87% of all statistics are made
up on the spot?

M.

    And then there's proof by triviality.  My ex had a way of
    absorbing a tiny trivial fact about almost any subject.
    Then he'd throw one of these into the appropriate discussion
    thereby overwhelming his opponent with the depth of his
    knowledge of the subject.  Of course only I knew that this one
    fact was the _only_ thing he knew about the subject.
    
    Nanci

    Wrong.  86% of all statistics are made up.
    
    							Ann B.
    
    :-)

    I just  ran  into the original article. The title is "How to Prove
    It (with apologies to George Polya)".

    George Polya  is  the  author  of a book called "How to Solve It",
    which  is  about  finding  solutions to tricky problems. Sort of a
    precursor to Martin Gardner's "Aha" books.

--David (Enjoying his newly cleaned room in which process he found
		the article.)

    	I take it that means the large mobile in the basement is now
    serving its true calling in life as a bed...
    
    				--Doug	;-)

    Yup. Time to start the next project.