Proof by Contradiction

Proof by contradiction is a method of mathematical proof in which one assumes the negation of the proposition to be proved, derives a logical contradiction from that assumption, and concludes that the original proposition must be true. The method is also called reductio ad absurdum — reduction to absurdity — and it is one of the most powerful tools in the mathematician's arsenal.

The structure is simple but profound: to prove P, assume not-P, and show that this assumption entails both Q and not-Q for some proposition Q. Since Q and not-Q cannot both be true, the assumption not-P must be false, and P must be true. This is not merely a rhetorical trick. It is a demonstration that the negation of P is internally inconsistent — that the universe of logical possibility has no room for not-P.

Proof by contradiction shares a deep structural similarity with the pruning step in branch-and-bound optimization. In both cases, a possibility space is explored by assuming a proposition and deriving its consequences; if the consequences are unacceptable (a logical contradiction or a bound worse than the incumbent), the assumption is discarded. The mathematician who assumes the opposite of what they wish to prove and the algorithm that assumes a branch contains the optimal solution are engaged in the same activity: controlled exploration followed by disciplined rejection.

The method is not without controversy. Intuitionists and constructivists reject proof by contradiction for existential claims, arguing that demonstrating that not-P leads to absurdity does not construct the object whose existence P asserts. To know that a proof exists is not, for the constructivist, to possess the proof. This disagreement is not merely about proof technique; it is about the ontology of mathematical knowledge itself.