School of Mathematics and Statistics

Faculty of Engineering, Computing and Mathematics | University of Western Australia

The following is a list of some common proof techniques that are often extremely useful. I received the original list long time ago via e-mail. Recently, or rather over time, Michael Ashley, Deepak Azad, Roman Beslik, Atanas Boev, John Chase, Maxwell Davenport, Christophe de Dinechin, Hedi Driss, Dan Echlin, Ron Garret, Manuel Hoffmann, Arthur Keller, Vivek Joy Kozhikkottu, John McGoff, Scott A. McIntyre, John Norberg, Alex Papanicolao, József Pék, Arnold G. Reinhold, Noemi Reynolds, Greg Rose, Lucas Scharenbroich, John Snider, Ki Song, Moritz Voss, David N. Werner and Thomas Zaslavsky suggested some additions. I also added my own experiences from teaching techniques of proofs in a first year mathematics units for several years.

Unfortunately all these proof techniques are invalid and, hence, one should not use them in assignments, workshops, exams, papers, etc.

## 1.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.

“Trivial.”

## 1.3 Proof by vigorous handwaving

Works well in a classroom or seminar setting.

## 1.4 Proof by cumbersome notation

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

## 1.5 Proof by exhaustion

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

## 1.6 Proof by omission

“The reader may easily supply the details.”
“The other 253 cases are analogous.”
“...”

## 1.7 Proof by obfuscation

A long plotless sequence of true and/or meaningless syntactically related statements.

## 1.8 Proof by wishful citation

The author cites the negation, converse, or generalization of a theorem from literature to support his claims.

## 1.9 Proof by funding

How could three different government agencies be wrong?

## 1.10 Proof by eminent authority

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

## 1.11 Proof by personal communication

“Eight-dimensional colored cycle stripping is NP-complete [Karp, personal communication].”

## 1.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.”

## 1.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.

## 1.14 Proof by importance

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

## 1.15 Proof by accumulated evidence

Long and diligent search has not revealed a counterexample.

## 1.16 Proof by cosmology

The negation of the proposition is unimaginable or meaningless. Popular for proofs of the existence of God.

## 1.17 Proof by mutual reference

In reference A, Theorem 5 is said to follow from Theorem 3 in reference B, which is shown from Corollary 6.2 in reference C, which is an easy consequence of Theorem 5 in reference A.

## 1.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.

## 1.19 Proof by picture

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

## 1.20 Proof by vehement assertion

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

## 1.21 Proof by ghost reference

Nothing even remotely resembling the cited theorem appears in the reference given.

## 1.22 Proof by forward reference

Reference is usually to a forthcoming paper of the author, which is often not as forthcoming as at first.

## 1.23 Proof by semantic shift

Some standard but inconvenient definitions are changed for the statement of the result.

## 1.24 Proof by appeal to intuition

Cloud-shaped drawings frequently help here.

## 2.1 Proof by acceptance

We were asked in an exercise to proof this theorem. Hence, it must be true.

## 3.1 Proof by erasure

This works best with chalk on a blackboard. E.g., if at some stage in the proof you have "(x^4)/x", erase the first parenthesis and "4)/x" and replace the latter with "3", yielding "x^3". After no more than a few moments of writing and erasing, the final result will appear on the blackboard, with no extraneous working.

[I learnt this from an applied maths lecturer at ANU in the late 1970's; and he actually used it! He would write using chalk with one hand, and an eraser in the other.]

## 4.1 Proof by placing a bet

"I bet a \$1000 that this is true, are you willing to take this bet?" Proof is complete if no one takes the bet.

## 5.1 Proof by indeterminate literature

"The proof easily can be found in the literature." "The literature" is so vast that someone easily can spend a year looking for just one proof.

## 6.1 Proof by overwhelming size

The equation holds true for values of much larger than x.

## 7.1 Proof by beautiful typesetting

Because the proof looks good and is typed in LaTeX, it must be right.

## 8.1 Proof by group complaint

Often employed in classes of few students when they decide the question is too hard.

## 8.2 Proof by convincing knowledge of related facts

Where a student does a lot of handwaving, but uses their in-depth knowledge of things closely related to the proof to convince the marker they know what they are talking about. The details are left as an exercise for the marker who knew 'what they meant'.

## 9.1 Proof by voting

The majority of [proper authority] believes that...

## 9.2 Proof by prohibitive cost

The cost would be prohibitive if X was proven false...

## 9.3 Proof by religious belief

God told us that X is true (frequent among creationists)

## 9.4 Proof by astonishment

“Surely, you are not implying that X is false.”

## 9.5 Proof by invalid negation

Y implies not X, therefore not Y implies X.

## 9.6 Proof by reverse recurrence

The theorem is true for N = 0, and if the theorem is true for N+1, then it is true for N.

## 9.7 Proof by computer

The computer told us that X is true.

## 9.8 Proof by partial enumeration

There are two kinds of animals: mammals and birds. Mammals are homeotherm. Birds are homeotherm. Therefore, all animals are homeotherm.

## 10.1 Proof by Hot Air

Needs a loud assertive voice, muscled jaws can increase its efficiency.

## 11.1 Proof by Selective Hearing

The professor simply and conveniently writes down a variation on quadratic reciprocity, despite the fact that the student pointed out that 87 is actually not a prime modulus.

## 11.2 Proof by Accelerated Course

We don't have time to prove this...

## 12.1 Proof by horror story

This is a refinement of "proof by anecdote" where the data point cited has a strong negative emotional impact. This is a popular technique in politics and product liability lawsuits.

## 12.2 Proof by rhyming

Most prominently used to help acquit O.J. Simpson of murder. "If it doesn't fit you must acquit."

## 13.1 Proof by sketch/illustration

I often get from first semester students:
They draw a little figure of how they think, e.g. a graph looks like, and deduce facts by this illustration. This way often special cases (like empty graph, isolated nodes, ...) are ignored.

## 14.1 Proof by use of puns and homonyms

Best used when giving the proof verbally. cf http://en.wikipedia.org/wiki/Wikipedia:How_many_legs_does_a_horse_have%3F
and
A cow have four more legs than no cow. No cow has five legs.
Therefore, a cow has nine legs.

## 14.2 Proof by invalid induction

Show it's true for n=1 and for n+1 assuming n. But the induction step works only for n>1. cf. Proof that all horses are the same color.

## 14.3 Proof by assuming a contradiction

Slip by the reader that you have assumed both P and not P. Then you can deduce any Q.

## 14.4 Proof by introduction of useful statement

X is true because of Y, but you haven't proven Y yet and the proof is so long it's hard to notice.

## 14.5 Proof by parent

"Because I said so."

## 14.6 Proof by repetition

Have many people claim it's true to the media, and the media will start believing it.

## 14.7.1 Proof denial by continually sowing doubt

Used to deny the hazards of cigarette smoke for many years, and now climate change deniers. Made easier with media being complicit by always needing to present contrary points of view to nearly any issue.

## 14.7.2 Proof denial by citing vested interest

Don't trust it because the one who gave the proof will benefit financially from its acceptance.

## 15.1 Proof by “Its too good to be true”

Used often in cases of free energy claims or most quantum mechanical possibilities. Closely related to proof by common sense and proof by popularity

## 15.2 Proof by lack of space

This applies when the author cites lack of pages in a journal or students in an exam.

## 15.3 Proof by pity

Used by a student who really needs to pass a course.

## 16.1 Proof by page turning

Work forward from what you know on one page. Then work backwards from the answer on the other side. Nobody notices.

## 17.1 Proof by legislation

An entire body of (sort-of) elected officials is more correct than all of the known laws of physics, math and science as a whole.

## 18.1 Proof by Elephant

I thought I would share a comment regarding something one of my professors would say a lot. He never used it as a proof, but rather an introduction of a fact:
"If it walks like an elephant, talks like an elephant, it must be an elephant."

## 19.1 Proof by exercise

The reader is left to do the proof as an exercise. Most commonly found in textbooks.

## 20.1 Proof by condescence and reassurance

Theorem 12.3's proof is beyond the scope of your course, however, it is possible to prove it using more advanced Mathematics.

## 21.1 Proof by ethical exclusion

Any experiment that could collect confounding data would violate accepted ethical guidelines.

## 21.2 Proof by legal intimidation

Schedule a talk to present results refuting our claims and we get an injunction under the Digital Millennium Copyright Act or local equivalent.

## 21.3 Proof by demonstrating equivalence to a problem thought to be hard

Typically factoring integers or finding logarithms in finite groups. This method of proof is one of the two pillars of modern cryptography.

## 21.4 Proof by unclaimed reward

We offered a \$10,000 prize for anyone who could solve this puzzle and no one has come forward with a correct answer. The other pillar.

## 21.5 Proof by Never-Ending Revision

If you point out an error in my lengthy and incoherent proof, I will send you an even longer, more impenetrable manuscript that purports to correct the mistake.

## 22.1 Proof by being a nice person

Using an appeal based on one's ‘nice’ personality. “You HAVE to believe me because I am awfully sweet. I don't say things that are not true — that would not be nice.”

## 22.2 Proof by appeal to humanity

Claiming that if a statement is not true then terrible things would happen to the world and/or humanity. “If it isn't true then humanity is so much the poorer for it. People are better off believing it.”

## 22.3 Proof by establishing and then tearing down a straw man

Misrepresenting an opposing argument and then pointing out what is wrong with that argument based on that representation. For example,
Person A: “The vast majority of primes are odd.”
Person B: “Person A says all primes are odd. But 2 is prime and not odd so A's statement is wrong.”

## 22.4 Proof by circular argument

Stating an assumption and using deductive reasoning based on that assumption to prove that it is true. Basically a ‘If it is true then it is true’ type of argument. A gross distortion of proof by contradiction. For example: “Assume all primes are odd numbers. If all primes are odd numbers then no prime can be even. Therefore there are no even primes.”

## 23.1 Proof by Sketch or Outline

“The paper contains an outline of the proof; an extended version of the paper will contain the full proof once it is finished.”

## 24.1 Proof by haste

“In the interest of time, I will skip the details...”

## 24.2 Proof by mercy

“I will spare you the details and move on to the main result.”

## 25.1 Proof by Lack of Counter Example

The premise of this proof technique is essentially “Nobody has ever seen one, so they don't exist.” Alternatively, “All of the items I tried worked, so this must be right.”

## 26.1 Proof by Exhaustion of Grader

I was surfing the web for a list of invalid proofs and I ran into your website. It's pretty neat, and it reminded me of a student who tried to solve the following problem: “Find all isomorphism classes of groups of order 28.”

The student basically tried to enumerate every single group of that order, and he/she basically went through each group to show that the property holds for them.

## 27.1 Proof by Recess

“... will present the theorem's proof after recess...”
-between 10 and 15 minutes pass-
“...as proven before recess, we can now ...”

## 28.1 Proof by lyricism

If it sounds right, it is right.

## 28.2 Interdisciplinary proof

In which a special form of an equation, definition, or technique used by one science is applied in a completely unrelated field. Best used by engineering undergraduates in pure mathematical courses, where the assignments will be graded by computer science undergraduates.

## 28.3 Proof by word order

In which a phrase of the form “the x of y” becomes “the y of x” three paragraphs later.

## 28.4 Proof by sneak preview

“Your question is beyond the scope of this course. However, next semester, if you want to explore this more thoroughly...”

## 29.1 Proof by semantic shift

There are two variants that I can think of. (a) As you have it; that is, you use different definitions from the normal ones (preferably, not obviously inequivalent) and prove a theorem that appears to be, but isn't, interesting. (b) Change the meanings of the terms in the course of the proof. This variant is best used in combination with the following method of proof.

## 29.2 Proof by slippery definitions

The definitions are not so well-defined that the reader can tell exactly what they mean.

## 29.3 Proof by countervailing errors

There are so many errors that they cancel each other out. (Students often do this.)

## 29.4 Proof by overwhelming errors

There are so many errors that the reader can't tell whether the conclusion is proved or not, so is forced to accept the claims of the writer.

Author: Berwin A Turlach