Proof techniques
Dunk
On Thu, 17 Oct 2002 00:48:25 +0000 (UTC), Kleuskes & Moos
<some...@over.the.rainbow> wrote:
> 1) Proof by referral to non-existent authorities
> 2) Reduction ad nauseam
> 3) Proof by assignment
> 4) Method of least astonishment
> 5) Proof by handwaving
> 6) Proof by intimidation
> 7) Method of deferral until later in the course
> 8) Proof by reduction to a sequence of unrelated lemmas
> 9) Method of convergent irrelevancies
>--
>As 'n tied komt, komt 'n ploag.
>
Thad Coons
Let's not forget:
Proof by diversionary obfuscation
Charlie-Boo
And the ultimate: Proof by Gregory Chaitin: ""
Did anybody see his latest article with the mistakes in his "proof" of
the unsolvability of the Halting Problem? It's funny. He's been
writing about Godel and Turing for 20 years (he says he 1st learned
Godel's Proof(s) when he was 12, he "out-Godeled Godel", his Omega is
more efficient than Turing's number, etc.), however ...
1. He only talks about the water downed version (based on soundness)
given by Godel in the introduction ("This is unprovable."), never
mentioning the more powerful version based on w-consistency given in
the body of Godel's 1931 paper. [Did he actually "under-Godel
Godel"?]
2. He never mentions Rosser's extension to that in 1936.
3. He can't even prove Turing's result at all.
4. His Omega "probability of a program halting" was greater than one
for years until he tried to fix it. (I understand he now has a 3rd
version that is the probability of one particular program halting.)
Speaking of which, here's a simple puzzle: Show a program that has no
"probability of halting" (Hint: it doesn't converge), thus showing
that the whole concept of Omega is not well-defined.
Have any of his definitions (much less subsequent conclusions) not
been shown to be ill-defined?
Charlie Volkstorf
Cambridge, MA
www.mathpreprints.com/math/Preprint/CharlieVolkstorf/20021008.1/1
www.arxiv.org/html/cs.lo/0003071
H. Enderton
>> 2) Reduction ad nauseam
>> 3) Proof by assignment
>> 4) Method of least astonishment
>> 5) Proof by handwaving
>> 6) Proof by intimidation
>> 7) Method of deferral until later in the course
>> 8) Proof by reduction to a sequence of unrelated lemmas
>> 9) Method of convergent irrelevancies
The following is taken from an article entitled "How To Prove It",
by Dana Angluin of the Yale Computer Science Dept., which appeared in
Vol. 15, Number 1 (1983) of the Association for Computing Machinery's
journal SIGACT News.
HOW TO PROVE IT
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 similar."
"..."
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 claims.
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 colored cycle stripping is NP-complete [Karp, personal
communication]."
12. Proof by reduction to the wrong problem:
"To see that infinite-dimensional colored 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 accumulated 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
the 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:
One proves that a proof must exist, using any of the techniques described
herein.
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 of the author, which is often
not as forthcoming as at first.
23. Proof by semantic shift:
Some standard but inconvenient definitions are changed for the statement of
the result.
24. Proof by appeal to intuition:
Cloud-shaped drawings frequently help here.
Herman Jurjus
> >> 1) Proof by referral to non-existent authorities
> >> 2) Reduction ad nauseam
> >> 3) Proof by assignment
> >> 4) Method of least astonishment
> >> 5) Proof by handwaving
> >> 6) Proof by intimidation
For what it's worth, i really think this should be
"Proof by complete intimidation"
as that reminds one more of "complete induction".
Cheers,
Herman Jurjus