112 lines
3.4 KiB
Plaintext
112 lines
3.4 KiB
Plaintext
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.
|
||
|
||
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.
|
||
|
||
----------------------------------------------------
|
||
|
||
|
||
|
||
|
||
Henry Cate III
|
||
--------------
|
||
(ucbvax!xerox.com!cate3.osbunorth) OR (cate3.osbunorth@Xerox.Com)
|
||
Everyone complains of his memory, no one of his judgment.
|
||
|
||
|