What Is Proof by Contradiction? Assuming the Opposite and Watching It Fail

The structure is simple. Suppose the statement to be proved is false. Reason from that supposition using accepted rules until something impossible follows, meaning a statement that is both true and false or one contradicting an established result. Since valid reasoning cannot produce a contradiction from true premises, one of the premises must be false, and since everything else was established, the supposition must be. Therefore the original statement holds. The method is powerful because it supplies an extra premise to work from, namely the negation of the goal, which frequently provides exactly the foothold a direct argument lacks. It is particularly effective for proving that something does not exist or that a property is impossible, since those claims are awkward to establish directly, and it underlies a great many results about infinity and about irrationality where no constructive route is available.

Several of the best-known proofs in mathematics use the method:

• •The irrationality of the square root of two, which supposes it can be written as a fraction in lowest terms and derives that both the numerator and denominator must be even, contradicting the assumption that the fraction was reduced
• •Euclid's proof that the primes are infinite, which supposes a finite list and constructs a number that is divisible by none of them
• •Cantor's diagonal argument, which supposes a complete list of real numbers and constructs one that is not on it
• •The halting problem, which supposes a program that decides whether any program halts and constructs one that defeats it
• •Godel's incompleteness result, which uses a related self-referential construction
• •A great many impossibility proofs, including that certain classical constructions cannot be performed with compass and straightedge

A minority position in the foundations of mathematics rejects the method in its full strength. Intuitionism, associated with L. E. J. Brouwer, holds that a mathematical statement is true only if it can be constructed or demonstrated, and consequently rejects the law of excluded middle, which asserts that every statement is either true or false regardless of whether anyone can determine which. Without that law, showing that the negation leads to contradiction does not establish the original claim, since both might fail to be determinate. Constructivists accept proofs that produce the object in question and reject those that merely show non-existence is impossible, and the practical consequence is that a constructive proof supplies an algorithm while a non-constructive one supplies only knowledge that something exists. That distinction turned out to matter enormously in computer science, since constructive proofs correspond to programs, which is the content of the correspondence between proofs and programs that underlies several modern type systems.

Several proof techniques are neighbours and confusing them is common. Proof by contrapositive establishes that if the conclusion fails then a premise fails, which is logically equivalent to the original claim and is constructively acceptable, unlike full contradiction. Proof by exhaustion checks every case, which works only for finitely many and which computers have made practical for problems with very large case counts, most famously the four colour theorem. Proof by induction establishes a base case and a step showing that truth at one stage implies truth at the next, which handles infinitely many claims at once. Direct proof reasons from premises to conclusion without any supposition. Counterexample refutes a universal claim with a single instance and is the mirror image of proof. Choosing between them is a practical matter, and a claim that resists a direct approach frequently yields immediately to contradiction, which is why experienced mathematicians try the negation early rather than as a last resort.

The method appears outside mathematics as reductio ad absurdum and is frequently misapplied. In a mathematical proof the contradiction is formal and unarguable, while in ordinary argument the absurd conclusion is generally something the arguer finds unacceptable rather than something logically impossible, which makes the argument only as strong as the shared judgement that the conclusion is absurd. Opponents can and frequently do accept the supposedly absurd consequence, which defeats the argument entirely and is a recognised move. The method also depends on the intermediate reasoning being valid, and a long chain increases the chance that the contradiction came from an error rather than from the supposition. And it requires that only one premise is in doubt, since deriving a contradiction from a set of premises shows that at least one fails without indicating which, which is a limitation that applies with full force whenever background assumptions are contested.

Assuming the negation supplies an extra premise to reason from, which is why the method works so well for impossibility and non-existence claims that resist direct proof. It gave the irrationality of the square root of two, the infinity of the primes and the undecidability of halting. Constructivists reject it because showing non-existence is impossible does not produce the object, which matters because constructive proofs correspond to programs.