Inlogic,reductio ad absurdum (Latin for "reduction to absurdity"), also known asargumentum ad absurdum, (Latin for "argument to absurdity")apagogical argument, orproof by contradiction is the form of argument that attempts to establish a claim by showing that following the logic of a proposition or argument would lead to absurdity orcontradiction.[1][2][3][4] Although it is quite freely used in mathematical proofs, not everyschool of mathematical thought accepts this kind ofnonconstructive proof.[5]
This argument form traces back toAncient Greek philosophy and has been used throughout history in both formal mathematical and philosophical reasoning, as well as in debate. In mathematics, the technique is called proof by contradiction. In formal logic, this technique is captured by an axiom for "reductio ad absurdum", normally given the abbreviation RAA, which is expressible inpropositional logic. This axiom is the introduction rule for negation (seenegation introduction).
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 asindirect proof,proof by assuming the opposite,[6] andreductio ad impossibile.[7]
G. H. Hardy described proof by contradiction as "one of a mathematician's finest weapons", saying "It is a far finer gambit than anychess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game."[8]
The "absurd" conclusion of areductio ad absurdum argument can take a range of forms:
The first example argues that denial of the premise would result in a ridiculous conclusion, against the evidence of our senses (empirical evidence).[9] The second example is a mathematicalproof by contradiction (also known as an indirect proof[10]), which argues that the denial of the premise would result in alogical contradiction (there is a "smallest" number and yet there is a number smaller than it).[11]
A mathematical proof employing proof by contradiction usually proceeds as follows:
An important special case is theexistence 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.
Reductio ad absurdum was used throughoutGreek philosophy. The earliest example of areductio argument can be found in a satirical poem attributed toXenophanes of Colophon (c. 570 – c. 475BCE).[12] CriticizingHomer's attribution of human faults to the gods, Xenophanes states that humans also believe that the gods' bodies have human form. But if horses and oxen could draw, they would draw the gods with horse and ox bodies.[13] The gods cannot have both forms, so this is a contradiction. Therefore, the attribution of other human characteristics to the gods, such as human faults, is also false.
Greek mathematicians proved fundamental propositions usingreductio ad absurdum.Euclid of Alexandria (mid-4th – mid-3rd centuries BCE) andArchimedes of Syracuse (c. 287 – c. 212 BCE) are two very early examples.[14]
The earlier dialogues ofPlato (424–348 BCE), relating the discourses ofSocrates, raised the use ofreductio arguments to a formal dialectical method (elenchus), also called theSocratic method.[15] Typically, Socrates' opponent would make what would seem to be an innocuous assertion. In response, Socrates, via a step-by-step train of reasoning, bringing in other background assumptions, would make the person admit that the assertion resulted in an absurd or contradictory conclusion, forcing him to abandon his assertion and adopt a position ofaporia.[10]
Elenctic refutation depends on adichotomous thesis, one that may be divided into exactly twomutually exclusive parts, only one of which may be true. Then Socrates goes on to demonstrate the contrary of the commonly accepted part using the law of non-contradiction. According to Gregory Vlastos,[16] the method has the following steps:
The technique was also a focus of the work ofAristotle (384–322 BCE), particularly in hisPrior Analytics where he referred to it as demonstration to the impossible (Ancient Greek:ἡ εἰς τὸ ἀδύνατον ἀπόδειξις,lit. 'demonstration to the impossible', 62b).[4]
Another example of this technique is found in thesorites paradox, where it was argued that if 1,000,000 grains of sand formed a heap, and removing one grain from a heap left it a heap, then a single grain of sand (or even no grains) forms a heap.[17]
Much ofMadhyamakaBuddhist philosophy centers on showing how variousessentialist ideas have absurd conclusions throughreductio ad absurdum arguments (known asprasaṅga, "consequence" in Sanskrit). In theMūlamadhyamakakārikā,Nāgārjuna'sreductio ad absurdum arguments are used to show that any theory of substance or essence was unsustainable and therefore, phenomena (dharmas) such as change, causality, and sense perception were empty (sunya) of any essential existence. Nāgārjuna's main goal is often seen by scholars as refuting the essentialism of certain BuddhistAbhidharma schools (mainlyVaibhasika) which posited theories ofsvabhava (essential nature) and also the HinduNyāya andVaiśeṣika schools which posited a theory of ontological substances (dravyatas).[18]
In 13:5, Nagarjuna wishes to demonstrate consequences of the presumption that things essentially, or inherently, exist, pointing out that if a "young man" exists in himself then it follows he cannot grow old (because he would no longer be a "young man"). As we attempt to separate the man from his properties (youth), we find that everything is subject to momentary change, and are left with nothing beyond the merely arbitrary convention that such entities as "young man" depend upon.
Contemporary philosophers have also utilized appeals to thereductio ad absurdum argument within their respective scholarly works. Included among them are:
Aristotle clarified the connection between contradiction and falsity in hisprinciple of non-contradiction, which states that a proposition cannot be both true and false.[28][29] That is, a proposition and its negation (not-Q) cannot both be true. Therefore, if a proposition and its negation can both be derived logically from a premise, it can be concluded that the premise is false. This technique, known as indirect proof orproof by contradiction,[10] has formed the basis ofreductio ad absurdum arguments in formal fields such aslogic and mathematics.
The principle may be formally expressed as thepropositional formula ¬¬P ⇒P, equivalently (¬P ⇒ ⊥) ⇒P, which reads: "If assumingP to be false implies falsehood, thenP is true."
Innatural deduction the principle takes the form of therule of inference
which reads: "If is proved, then may be concluded."
Insequent calculus the principle is expressed by the sequent
which reads: "Hypothesesand entail the conclusionor."
Inclassical logic the principle may be justified by the examination of thetruth table of the proposition¬¬P ⇒ P, which demonstrates it to be atautology:
| P | ¬P | ¬¬P | ¬¬P ⇒ P |
|---|---|---|---|
| T | F | T | T |
| F | T | F | T |
Another way to justify the principle is to derive it from thelaw of the excluded middle, as follows. We assume¬¬P and seek to proveP. By the law of excluded middleP either holds or it does not:
In either case, we establishedP. It turns out that, conversely, proof by contradiction can be used to derive the law of excluded middle.
Inclassical sequent calculus LK proof by contradiction is derivable from theinference rules for negation:
Proof by contradiction is similar torefutation by contradiction,[30][31] also known asproof of negation, which states that¬P is proved as follows:
In contrast, proof by contradiction proceeds as follows:
Formally these are not the same, as refutation by contradiction applies only when the proposition to be proved is negated, whereas proof by contradiction may be applied to any proposition whatsoever.[32] In classical logic, where and may be freely interchanged, the distinction is largely obscured. Thus in mathematical practice, both principles are referred to as "proof by contradiction".
Inintuitionistic logic proof by contradiction is not generally valid, although some particular instances can be derived. In contrast, proof of negation and principle of noncontradiction are both intuitionistically valid.[33]
Brouwer–Heyting–Kolmogorov interpretation of proof by contradiction gives the following intuitionistic validity condition:if there is no method for establishing that a proposition is false, then there is a method for establishing that the proposition is true.[clarify]
If we take "method" to meanalgorithm, then the condition is not acceptable, as it would allow us to solve theHalting problem. To see how, consider the statementH(M) stating "Turing machineM halts or does not halt". Its negation¬H(M) states that "M neither halts nor does not halt", which is false by thelaw of noncontradiction (which is intuitionistically valid). If proof by contradiction were intuitionistically valid, we would obtain an algorithm for deciding whether an arbitrary Turing machineM halts, thereby violating the (intuitionistically valid) proof of non-solvability of theHalting problem.
A propositionP which satisfies is known as a¬¬-stable proposition. Thus in intuitionistic logic proof by contradiction is not universally valid, but can only be applied to the ¬¬-stable propositions. An instance of such a proposition is a decidable one, i.e., satisfying. Indeed, the above proof that the law of excluded middle implies proof by contradiction can be repurposed to show that a decidable proposition is ¬¬-stable. A typical example of a decidable proposition is a statement that can be checked by direct computation, such as " is prime" or " divides".
An early occurrence of proof by contradiction can be found inEuclid's Elements, Book 1, Proposition 6:[34]
The proof proceeds by assuming that the opposite sides are not equal, and derives a contradiction. Likewise, many other proofs following in Euclid's Elements also use the same proof strategy, such as in Book 7, Proposition 33:[35]
An influential proof by contradiction was given byDavid Hilbert. HisNullstellensatz states:
Hilbert proved the statement by assuming that there are no such polynomials and derived a contradiction.[36]
Euclid's theorem states that there are infinitely many primes. InEuclid's Elements the theorem is stated in Book IX, Proposition 20:[37]
Depending on how we formally write the above statement, the usual proof takes either the form of a proof by contradiction or a refutation by contradiction. We present here the former, see below how the proof is done as refutation by contradiction.
If we formally express Euclid's theorem as saying that for every natural number there is a prime bigger than it, then we employ proof by contradiction, as follows.
Given any number, we seek to prove that there is a prime larger than. Suppose to the contrary that no suchp exists (an application of proof by contradiction). Then all primes are smaller than or equal to, and we may form the list of them all. Let be the product of all primes and. Because is larger than all prime numbers it is not prime, hence it must be divisible by one of them, say. Now both and are divisible by, hence so is their difference, but this cannot be because 1 is not divisible by any primes. Hence we have a contradiction and so there is a prime number bigger than.
The following examples are commonly referred to as proofs by contradiction, but formally employ refutation by contradiction (and therefore are intuitionistically valid).[38]
Let us take a second look atEuclid's theorem – Book IX, Proposition 20:[37]
We may read the statement as saying that for every finite list of primes, there is another prime not on that list, which is arguably closer to and in the same spirit as Euclid's original formulation. In this caseEuclid's proof applies refutation by contradiction at one step, as follows.
Given any finite list of prime numbers, it will be shown that at least one additional prime number not in this list exists. Let be the product of all the listed primes and aprime factor of, possibly itself. We claim that is not in the given list of primes. Suppose to the contrary that it were (an application of refutation by contradiction). Then would divide both and, therefore also their difference, which is. This gives a contradiction, since no prime number divides 1.
The classicproof that the square root of 2 is irrational is a refutation by contradiction.[39] Indeed, we set out to prove the negation¬ ∃ a, b ∈ . a/b =√2 by assuming that there exist natural numbersa andb whose ratio is the square root of two, and derive a contradiction.
Proof by infinite descent is a method of proof whereby a smallest object with desired property is shown not to exist as follows:
Such a proof is again a refutation by contradiction. A typical example is the proof of the proposition "there is no smallest positive rational number": assume there is a smallest positive rational numberq and derive a contradiction by observing thatq/2 is even smaller thanq and still positive.
Russell's paradox, stated set-theoretically as "there is no set whose elements are precisely those sets that do not contain themselves", is a negated statement whose usual proof is a refutation by contradiction.
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 ofQ.E.D., but this notation is rarely used today.[40] A graphical symbol sometimes used for contradictions is a downwards zigzag arrow "lightning" symbol (U+21AF: ↯), for example in Davey and Priestley.[41] Others sometimes used include a pair ofopposing arrows (as[citation needed] or),[citation needed] struck-out arrows (),[citation needed] a stylized form of hash (such as U+2A33: ⨳),[citation needed] or the "reference mark" (U+203B: ※),[citation needed] or.[42][43]
Inautomated theorem proving the method ofresolution 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.[44]
The dictionary definition ofper impossibile at Wiktionary