# com Henry Cate How to prove

## Found at: 0x1bi.net:70/textfiles/file?humor/proof.met

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.

The author gives only the case n=2 and suggests that it contains most

of the ideas of the general proof.

'Trivial.'

Works well in a classroom or seminar setting.

Best done with access to at least four alphabets and special symbols.

An issue or two of a journal devoted to your proof is useful.

'The reader may easily supply the details.'

'The other 253 cases are analogous.'

'...'

A long plotless sequence of true and\or meaningless syntactically related

statements.

The author cites the negation, converse, or generalization of a theorem

from the literature to support his claims.

How could three different government agencies be wrong?

'I saw Karp in the elevator and he said it was probably NP-complete.'

'Eight-dimensional colored cycle stripping is NP-complete [Karp, personal

commmunication].

'To see that infinite-dimensional colored cycle stripping is decidable,

we reduce it to the halting problem.'

The author cites a simple corollary of a theorem to be found in a privately

circulated memoir of the Slovenian Philological Society, 1883.

A large body of useful consequences all follow from the proposition in

question.

Long and diligent search has not revealed a counterexample.

The negation of the proposition is unimaginable or meaningless. Popular

for proofs of the existence of God.

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.

A method is given to construct the desired proof. The correctness of the

method is proved by any of these techniques.

A more convincing form of proof by example. Combines well with proof by

omission.

It is useful to have some kind of authority relation to the audience.

Nothing even remotely resembling the cited theorem appears in the reference

given.

Reference is usually to a forthcoming paper of the author, which is often

not as forthcoming as at first.

Some standard but inconvenient definitions are changed for the statement

of the result.

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.