How To Prove a Theorem ..!

This list has been compiled by Dana Angluin and was originally published in SIGACT News, Winter-Spring, 1983, Volume 15 #1.

The following methods have been used successfully and have been consequently submitted by fellow readers and members.

1. Proof by example
   The author gives only the case n=2 and suggests that it contains most of the ideas of the general proof.
2. Proof by intimidation
   "Trivial"
3. Proof by vigorous handwaving
   Works well in a classroom or seminar setting.
4. Proof by cumbersome notation
   Best done with access to at least four alphabets and special symbols.
5. Proof by exhaustion
   An issue or two of a journal devoted to your proof is useful.
6. Proof by omission
   "The reader may easily supply the details."
   "The other 253 cases are analogous."
   "..."
7. Proof by obfuscation
   A long plotless sequence of true and/or meaningless syntactically related statements.
8. Proof by wishful citation
   The author cites the negation, converse, or generalization of a theorem from the literature to support his claim.
9. Proof by funding
   How could three different government agencies be wrong?
10. Proof by eminent authority
    "I saw Karp in the elevator and he said it was probably NP-complete."
11. Proof by personal communication
    "Eight-dimensional coloured cycle stripping is NP-complete (Karp, personal communication)."
12. Proof by reduction to the wrong problem
    "To see that infinite-dimensional coloured cycle stripping is decidable, we reduce it to the halting problem."
13. 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.
14. Proof by importance
    A large body of useful consequences all follow from the proposition in question.
15. Proof by accumulation of evidence
    Long and diligent search has not revealed a counterexample.
16. Proof by cosmology
    The negation of the proposition is unimaginable or meaningless. Popular for proofs of the existence of God.
17. 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.
18. Proof by metaproof
    A method is given to construct the desired proof. The correctness of the method is proved by any of these techniques.
19. Proof by picture
    A more convincing form of proof by example. Combines well with proof by omission.
20. Proof by vehement assertion
    It is useful to have some kind of authority relation to the audience.
21. Proof by ghost reference
    Nothing even remotely resembling the cited theorem appears in the reference given.
22. Proof by forward reference
    Reference is usually to a forthcoming paper by the author.
23. Proof by semantic shift
    Some of the standard but inconvenient definitions are changed for the statement of the result.
24. Proof by appeal to intuition
    Cloud-shaped drawings frequently help here.
25. Proof by lack of imagination
    How could a life form not be carbon based?

Definitions of Terms Commonly Used in Lectures at IITs !!

CLEARLY: I don't want to write down all the in-between steps.

TRIVIAL: If I have to show you how to do this, you're in the wrong class.

OBVIOUSLY: I hope you weren't sleeping when we discussed this earlier, because I refuse to repeat it.

RECALL: I shouldn't have to tell you this, but for those of you who erase your memory tapes after every quiz, here it is again.

WITHOUT LOSS OF GENERALITY: I'm not about to do all the possible cases, so I'll do one and let you figure out the rest.

SIMILARLY: At least one line of the proof of this case is the same as before.

TWO LINE PROOF: I'll leave out everything but the conclusion.

ONE MAY SHOW: One did, his name was Gauss.

IT IS WELL KNOWN: See "Mathematische Zeitschrift'', vol XXXVI, 1892.

CHECK FOR YOURSELF: This is the boring part of the proof, so you can do it on your own time.

SKETCH OF A PROOF: I couldn't verify the details, so I'll break it down into parts I couldn't prove.

HINT: The hardest of several possible ways to do a proof.

BRUTE FORCE: Four special cases, three counting arguments, two long inductions, and a partridge in a pair tree.

SOFT PROOF: One third less filling (of the page) than your regular proof, but it requires two extra years of course work just to understand the terms.

ELEGANT PROOF: Requires no previous knowledge of the subject, and is less than ten lines long.

CANONICAL FORM: 4 out of 5 mathematicians surveyed recommended this as the final form for the answer.

THE FOLLOWING ARE EQUIVALENT: If I say this it means that, and if I say that it means the other thing, and if I say the other thing...

BY A PREVIOUS THEOREM: I don't remember how it goes (come to think of it, I'm not really sure we did this at all), but if I stated it right, then the rest of this follows.

BRIEFLY: I'm running out of time, so I'll just write and talk faster.

LET'S TALK THROUGH IT: I don't want to write it on the board because I'll make a mistake.

PROCEED FORMALLY: Manipulate symbols by the rules without any hint of their true meaning.

QUANTIFY: I can't find anything wrong with your proof except that it won't work if x is 0.

FINALLY: Only ten more steps to go...

Q.E.D. : Thank God !

PROOF OMITTED: Trust me, it's true.