Promising Proofs
Many of my semantics-inclined friends have asked for this collection of useful
proof techniques to be republished - I hope to see many new papers as a result.
Most credit must go to Dana Angluin of the Computer Science Department at
Yaale. A version may also appear in SIGACT News, Vol.15 no.1, Spring 1983
(this could be an example of Proof by Ghost Reference).
Proof by Vigorous Handwaving:
Works well in a classroom or seminar situation
Proof by Cumbersome Notation:
Best achieved with at least four alphabets and special symbols.
Proof by Omission:
'The reader may easily supply the details'. 'The other 253 cases are analogous.
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 Corollaary 6.2 in
reference C, which is an easy consequence of Theorem 5 in
reference A.
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 generalisation of a
theorem from the literature to support his claim.
Proof by Funding (The ESPRIT gambit):
How could twelve different governments be wrong?
Proof by Eminent Authority:
'I saw De Bakker in the elevator and he said it was probably NP-complete'.
Proof by Personal Communication:
'Eight-dimensional coloured cycle stripping is NP-complete'
[De Bakker, personal comminucation].
Proof by Reduction to the Wrong Problem:
'To see that infinite-dimensional coloured cycle stripping is
decidable, we reduce it to the Halting problem'.
Proof by Reference to Inaccessible Literature:
The author cites a simple corallary of a theorem to be found in
a privately circulated memoir of the Slovenian Philogical Society, 1889.
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 Picture:
Combines well with Proof by Omission.
Proof by Vehement Assertion:
It is useful to have some kind of authority over tha 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 promised.
Proof by Appeal to Intuition:
Cloud-shaped drawings frequently help here.
Proof by Intimidation:
'Trivial'.
In Logic Programming Newsletter, vol. 3/3