Proof by contradiction
In logic, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction. Although it is quite freely used in mathematical proofs, not every school of mathematical thought accepts this kind of nonconstructive proof as universally valid.[1]
More broadly, proof by contradiction is any form of argument that establishes a statement by arriving at a contradiction, even when the initial assumption is not the negation of the statement to be proved. In this general sense, proof by contradiction is also known as indirect proof, proof by assuming the opposite,[2] and reductio ad impossibile.[3]
A mathematical proof employing proof by contradiction usually proceeds as follows:
An important special case is the existence proof by contradiction: in order to demonstrate that an object with a given property exists, we derive a contradiction from the assumption that all objects satisfy the negation of the property.
Relationship with other proof techniques[edit]
Refutation by contradiction[edit]
Proof by contradiction is similar to refutation by contradiction,[4][5] also known as proof of negation, which states that ¬P is proved as follows:
Examples of proofs by contradiction[edit]
Euclid's Elements[edit]
An early occurrence of proof by contradiction can be found in Euclid's Elements, Book 1, Proposition 6:[7]
Notation[edit]
Proofs by contradiction sometimes end with the word "Contradiction!". Isaac Barrow and Baermann used the notation Q.E.A., for "quod est absurdum" ("which is absurd"), along the lines of Q.E.D., but this notation is rarely used today.[13] A graphical symbol sometimes used for contradictions is a downwards zigzag arrow "lightning" symbol (U+21AF: ↯), for example in Davey and Priestley.[14] Others sometimes used include a pair of opposing arrows (as or ), struck-out arrows (), a stylized form of hash (such as U+2A33: ⨳), or the "reference mark" (U+203B: ※), or .[15][16]
Hardy's view[edit]
G. H. Hardy described proof by contradiction as "one of a mathematician's finest weapons", saying "It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game."[17]
Automated theorem proving[edit]
In automated theorem proving the method of resolution is based on proof by contradiction. That is, in order to show that a given statement is entailed by given hypotheses, the automated prover assumes the hypotheses and the negation of the statement, and attempts to derive a contradiction.[18]