Reductio ad absurdum

{{Short description|Argument that leads to a logical absurdity}} {{Italic title}} [[File:John Pettie - Reductio Ad Absurdum.jpg|thumb|upright=1.2|{{lang|la|Reductio ad absurdum}}, painting by John Pettie exhibited at the Royal Academy in 1884|alt=A bearded white Christian cleric in red argues towards an older pensive white Christian cleric in black.]]

In logic, '''{{lang|la|reductio ad absurdum}}''' (Latin for "reduction to absurdity"), also known as '''{{lang|la|argumentum ad absurdum}}''', (Latin for "argument to absurdity") '''apagogical argument''', or '''proof by contradiction''', is the form of argument that attempts to establish a claim by showing that following the logic of a contrary proposition or argument would lead to absurdity or contradiction.<ref name=":0">{{cite web|url=https://plato.stanford.edu/entries/mathematics-inconsistent/|title=Inconsistent Mathematics|author=Chris Mortensen|website=Stanford Encyclopedia of Philosophy}}</ref><ref>{{Cite web |title=Definition of REDUCTIO AD ABSURDUM |url=https://www.merriam-webster.com/dictionary/reductio+ad+absurdum |access-date=2019-11-27 |website=www.merriam-webster.com |language=en}}</ref><ref>{{citation |title=reductio ad absurdum |work=Collins English Dictionary – Complete and Unabridged |year=2014 |url=http://www.thefreedictionary.com/reductio+ad+absurdum |access-date=October 29, 2016 |edition=12th |orig-year=1991}}</ref><ref name="IEP">{{cite encyclopedia |title=Reductio ad absurdum |encyclopedia=The Internet Encyclopedia of Philosophy |url=http://www.utm.edu/research/iep/r/reductio.htm |access-date=21 July 2009 |author=Nicholas Rescher}}</ref> Although it is quite freely used in mathematical proofs, not every school of mathematical thought accepts this kind of nonconstructive proof.<ref>Bishop, Errett 1967. ''Foundations of Constructive Analysis'', New York: Academic Press. {{ISBN|4-87187-714-0}}</ref>

This argument form traces back to Ancient 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 inference rule for "'''''reductio ad absurdum'''''".

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''',<ref>{{Cite web |title=Proof By Contradiction |url=https://www2.edc.org/makingmath/mathtools/contradiction/contradiction.asp#:~:text=An%20indirect%20proof%20establishes%20that,original%20conclusion%20must%20be%20true |access-date=2023-06-12 |website=www2.edc.org |language=en}}</ref> and '''''reductio ad impossibile'''''.<ref>[https://www.oxfordreference.com/display/10.1093/acref/9780199891573.001.0001/acref-9780199891573-e-5911 The Oxford Essential Dictionary of Foreign Terms in English]</ref>

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."<ref name="Hardy">G. H. Hardy, ''A Mathematician's Apology; Cambridge University Press, 1992. {{ISBN|9780521427067}}. ''[https://www.math.ualberta.ca/mss/misc/A%20Mathematician's%20Apology.pdf PDF p.19] {{Webarchive|url=https://web.archive.org/web/20210216080630/https://www.math.ualberta.ca/mss/misc/A%20Mathematician%27s%20Apology.pdf|date=2021-02-16}}.</ref>

== Examples ==

The "absurd" conclusion of a ''reductio ad absurdum'' argument can take a range of forms, as can be seen in the following examples of refutation by contradiction:

* The Earth cannot be flat; otherwise, since the Earth is assumed to be finite in extent, we would find people falling off the edge. * There is no smallest positive rational number; if {{tmath|q}} were the smallest positive rational, then {{tmath|q/2}} would be a positive rational number that is smaller than {{tmath|q}} because it equals half of {{tmath|q}}, and it would also not be smaller than {{tmath|q}} because {{tmath|q}} is assumed to be the smallest positive rational.

The first example argues that denial of the premise would result in a ridiculous conclusion, against the evidence of our senses (empirical evidence).<ref>{{Citation|last=DeLancey|first=Craig|title=8. Reductio ad Absurdum|date=2017-03-27|url=https://milnepublishing.geneseo.edu/concise-introduction-to-logic/chapter/8-reductio-ad-absurdum/|work=A Concise Introduction to Logic|publisher=Open SUNY Textbooks|language=en|access-date=2021-08-31}}</ref> The second example is a mathematical proof by contradiction (also known as an indirect proof<ref name=":1">{{Cite web|url=https://www.thoughtco.com/reductio-ad-absurdum-argument-1691903|title=Reductio Ad Absurdum in Argument|last=Nordquist|first=Richard|website=ThoughtCo|language=en|access-date=2019-11-27}}</ref>), which argues that the denial of the premise would result in a logical contradiction ({{tmath|q/2}} is both smaller and not smaller than {{tmath|q}}).<ref>{{cite book|last1=Howard-Snyder|first1=Frances|last2=Howard-Snyder|first2=Daniel|last3=Wasserman|first3=Ryan|title=The Power of Logic|date=30 March 2012|publisher=McGraw-Hill Higher Education|isbn=978-0078038198|edition=5th}}</ref>

A mathematical proof employing proof by contradiction usually proceeds as follows:

# The proposition to be proved is ''P''. # We assume ''P'' to be false, i.e., we assume ''¬P''. # It is then shown that ''¬P'' implies falsehood. This is typically accomplished by deriving two mutually contradictory assertions, ''Q'' and ''¬Q'', and appealing to the law of noncontradiction. # Since assuming ''P'' to be false leads to a contradiction, it is concluded that ''P'' is in fact true.

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.

==Greek philosophy== ''Reductio ad absurdum'' was used throughout Greek philosophy. The earliest example of a {{lang|la|reductio}} argument can be found in a satirical poem attributed to Xenophanes of Colophon (c. 570 – c. 475 BCE).<ref name="Daigle">{{cite web | last = Daigle | first = Robert W. | title = The reductio ad absurdum argument prior to Aristotle | work = Master's Thesis | publisher = San Jose State Univ. | date = 1991 | url = http://scholarworks.sjsu.edu/cgi/viewcontent.cgi?article=1228&context=etd_theses | access-date =August 22, 2012 }}</ref> Criticizing Homer'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.<ref>{{Cite web|date=2014-05-18|title=Reductio ad Absurdum - Definition & Examples|url=https://literarydevices.net/reductio-ad-absurdum/|access-date=2021-08-31|website=Literary Devices|language=en-US}}</ref> 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 using ''reductio ad absurdum''. Euclid of Alexandria (mid-4th – mid-3rd centuries BCE) and Archimedes of Syracuse (c. 287 – c. 212 BCE) are two very early examples.<ref name= "Euclid">{{cite web | last= Joyce | first= David |author-link=David E. Joyce (mathematician)| title = Euclid's Elements: Book I | work = Euclid's Elements | publisher = Department of Mathematics and Computer Science, Clark University | date = 1996 | url = https://mathcs.clarku.edu/~djoyce/elements/bookI/propI6.html | access-date = December 23, 2017}}</ref>

The earlier dialogues of Plato (424–348 BCE), relating the discourses of Socrates, raised the use of {{lang|la|reductio}} arguments to a formal dialectical method ({{lang|la|elenchus}}), also called the Socratic method.<ref name="Bobzien">{{cite encyclopedia | last = Bobzien | first = Susanne | title = Ancient Logic | encyclopedia = Stanford Encyclopedia of Philosophy | publisher = The Metaphysics Research Lab, Stanford University | date = 2006 | url = http://plato.stanford.edu/entries/logic-ancient/#NonModSyl | access-date = August 22, 2012}}</ref> 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 of aporia.<ref name=":1" />

Elenctic refutation depends on a dichotomous thesis, one that may be divided into exactly two mutually 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,<ref>Gregory Vlastos, 'The Socratic Elenchus', ''Oxford Studies in Ancient Philosophy I'', Oxford 1983, 27–58.</ref> the method has the following steps:

# Socrates' interlocutor asserts a thesis, for example, "Courage is endurance of the soul", which Socrates considers false and targets for refutation. # Socrates secures his interlocutor's agreement to further premises, for example, "Courage is a fine thing" and "Ignorant endurance is not a fine thing". # Socrates then argues, and the interlocutor agrees, that these further premises imply the contrary of the original thesis, in this case, it leads to: "courage is not endurance of the soul". # Socrates then claims that he has shown that his interlocutor's thesis is false and that its negation is true.

The technique was also a focus of the work of Aristotle (384–322 BCE), particularly in his ''Prior Analytics'' where he referred to it as demonstration to the impossible ({{langx|grc|ἡ εἰς τὸ ἀδύνατον ἀπόδειξις||demonstration to the impossible}}, 62b).<ref name="IEP" />

Another example of this technique is found in the sorites 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.{{sfn|Hyde|Raffman|2018}}

==Buddhist philosophy== Much of Madhyamaka Buddhist philosophy centers on showing how various essentialist ideas have absurd conclusions through ''reductio ad absurdum'' arguments (known as ''prasaṅga'', "consequence" in Sanskrit). In the Mūlamadhyamakakārikā, Nāgārjuna's ''reductio 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 Buddhist Abhidharma schools (mainly ''Vaibhasika'') which posited theories of ''svabhava'' (essential nature) and also the Hindu Nyāya and Vaiśeṣika schools which posited a theory of ontological substances (''dravyatas'').<ref>Wasler, Joseph. ''Nagarjuna in Context.'' New York: Columibia University Press. 2005, pgs. 225-263.</ref>

===Example from Nāgārjuna's Mūlamadhyamakakārikā=== 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.

====13:5==== : A thing itself does not change. : Something different does not change. : Because a young man does not grow old. : And because an old man does not grow old either.{{sfn|Garfield|1995|p=210}}

==Modern philosophy== Contemporary philosophers have also utilized appeals to the ''reductio ad absurdum'' argument within their respective scholarly works. Included among them are: * Lewis White Beck - in a criticism of the mechanism philosophy. (''The Actor and the Spectator'', 1974)<ref>{{cite book | last=Beck | first=Lewis White | title=The Actor and the Spectator | publisher=Yale University Press | publication-place=New Haven | date=1975 | isbn=0-300-01899-1 | page=}}</ref><ref>{{Cite web|url=https://philpapers.org/rec/BECTAA-2|title=The Actor and the Spectator|first=Lewis White|last=Beck|date=November 17, 1975|publisher=Yale University Press|via=PhilPapers}}</ref><ref>{{Cite journal|url=http://www.jstor.org/stable/2219438|title=''The Philosophical Quarterly'' (1950-), Vol. 27, No. 107 (Apr., 1977), Oxford University Press for the Scots Philosophical Association and the University of St. Andrews pp. 185-186 ''The Actor and the Spectator'' by Lewis White Beck, book reviewed by Mary Midgley on JSTOR.org|author=Midgley, Mary|year=1977|journal=The Philosophical Quarterly |volume=27|issue=107|pages=185–186|via=JSTOR|doi=10.2307/2219438}}</ref><ref>{{Cite journal|url=http://www.jstor.org/stable/2183800|title=''The Philosophical Review'', Duke University Press on behalf of Philosophical Review Jul., 1977, Vol. 86, No. 3 (Jul., 1977), pp. 418-421 ''The Actor and the Spectator'' by Lewis Beck, book reviewed by Stephen Griffith on JSTOR.org|author=Griffith, Stephen|year=1977|journal=The Philosophical Review|volume=86|issue=3|pages=418–421|via=JSTOR|doi=10.2307/2183800|url-access=subscription}}</ref> * Robert L. Holmes - in his criticism of deterrence theory based upon the deontological prima facie presumption against killing innocent life and the irrationality of any reliance upon a system of preventing war which is based exclusively upon the threat of waging war. (''On War and Morality'', 1989)<ref>{{Cite journal |last=Meyers |first=Diana T. |date=1992 |title=Reviewed work: On War and Morality, Robert L. Holmes |url=https://www.jstor.org/stable/pdf/2185583.pdf |journal=The Philosophical Review |volume=101 |issue=2 |pages=481–484 |doi=10.2307/2185583 |jstor=2185583}}</ref><ref>{{Cite journal |last=Rock |first=Stephen R. |date=1989 |title=Reviewed work: On War and Morality, Robert L. Holmes; Paths to Peace: Exploring the Feasibility of Sustainable Peace, Richard Smoke, Willis Harman |url=https://www.jstor.org/stable/pdf/1961738.pdf |journal=The American Political Science Review |volume=83 |issue=4 |pages=1447–1448 |doi=10.2307/1961738 |jstor=1961738}}</ref><ref>{{Cite journal |last=Lee |first=Steven |date=1992 |title=Reviewed work: On War and Morality., Robert L. Holmes |url=https://www.jstor.org/stable/pdf/2216042.pdf |journal=Noûs |volume=26 |issue=4 |pages=559–562 |doi=10.2307/2216042 |jstor=2216042}}</ref><ref>{{Cite book |last=Holmes |first=Robert L. |url=https://books.google.com/books?id=TBoABAAAQBAJ&q=Robert+L.+Holms |title=On War and Morality |date=14 July 2014 |publisher=Princeton University Press |isbn=978-1-4008-6014-2}}</ref>

==Relation to the principle of non-contradiction==

Aristotle clarified the connection between contradiction and falsity in his principle of non-contradiction, which states that a proposition cannot be both true and false.<ref name="Ziembiński">{{cite book | last1 = Ziembiński | first1 = Zygmunt | title = Practical Logic | publisher = Springer | date = 2013 | pages = 95 | url = https://books.google.com/books?id=LOfsCAAAQBAJ&q=%22principle+of+non-contradiction%22&pg=PA95 | isbn = 978-9401756044 }}</ref><ref name="Ferguson1">{{cite book | last1 = Ferguson | first1 = Thomas Macaulay | last2 = Priest | first2 = Graham | title = A Dictionary of Logic | publisher = Oxford University Press | date = 2016 | pages = 146 | url = https://books.google.com/books?id=2Q5nDAAAQBAJ&q=%22principle+of+non-contradiction%22&pg=PT146 | isbn = 978-0192511553 }}</ref> That is, a proposition <math>Q</math> and its negation <math>\lnot Q</math> (not-''Q'') cannot both be true. Therefore, if a proposition and its negation are both entailed by a premise, the premise is false. This technique is the most common way of reaching a contradiction in mathematical arguments.

== Formalization == The principle may be formally expressed as the propositional formula ¬¬''P'' ⇒ ''P'', equivalently (¬''P'' ⇒ ⊥) ⇒ ''P'', which reads: "If assuming ''P'' to be false implies falsehood, then ''P'' is true."

In natural deduction the principle takes the form of the rule of inference

: <math>\cfrac{\vdash \lnot \lnot P}{\vdash P}</math>

which reads: "If <math>\lnot\lnot P</math> is proved, then <math>P</math> may be concluded."

In sequent calculus the principle is expressed by the sequent

: <math>\Gamma, \lnot\lnot P \vdash P, \Delta</math>

which reads: "Hypotheses <math>\Gamma</math> ''and'' <math>\lnot\lnot P</math> entail the conclusion <math>P</math> ''or'' <math>\Delta</math>."

== Justification == In classical logic the principle may be justified by the examination of the truth table of the proposition ''¬¬P ⇒ P'', which demonstrates it to be a tautology: {| class="wikitable" style="margin:1em auto; text-align:center;" ! style="width:80px" |{{math|''P''}} ! style="width:80px" |{{math|''¬P''}} ! style="width:80px" |{{math|''¬¬P''}} ! style="width:80px" |{{math|''¬¬P ⇒ P''}} |- ! style="background:papayawhip" |T !F !T !T |- ! style="background:papayawhip" |F !T !F !T |} Another way to justify the principle is to derive it from the law of the excluded middle, as follows. We assume ''¬¬P'' and seek to prove ''P''. By the law of excluded middle ''P'' either holds or it does not:

# if ''P'' holds, then of course ''P'' holds. # if ''¬P'' holds, then we derive falsehood by applying the law of noncontradiction to ''¬P'' and ''¬¬P'', after which the principle of explosion allows us to conclude ''P''.

In either case, we established ''P''. It turns out that, conversely, proof by contradiction can be used to derive the law of excluded middle.

In classical sequent calculus LK proof by contradiction is derivable from the inference rules for negation:

: <math>\cfrac{\cfrac{\cfrac{\ }{\Gamma, P \vdash P, \Delta} \; (I)}{\Gamma, \vdash \lnot P, P, \Delta} \; ({\lnot}R)}{\Gamma, \lnot\lnot P \vdash P, \Delta} \; ({\lnot}L)</math>

== Relationship with other proof techniques ==

=== Refutation by contradiction === Proof by contradiction is similar to '''refutation by contradiction''',<ref>{{cite web |title=Proof by contradiction |url=https://ncatlab.org/nlab/show/refutation+by+contradiction |access-date=7 October 2022 |website=nLab}}</ref><ref>Richard Hammack, ''[https://www.people.vcu.edu/~rhammack/BookOfProof/ Book of Proof]'', 3rd edition, 2022, {{ISBN|978-0-9894721-2-8}}; see "Chapter 9: Disproof".</ref> also known as proof of negation, which states that ''¬P'' is proved as follows:

# The proposition to be proved is ''¬P''. # Assume ''P''. # Derive falsehood. # Conclude ''¬P''.

In contrast, proof by contradiction proceeds as follows:

# The proposition to be proved is ''P''. # Assume ''¬P''. # Derive falsehood. # Conclude ''P''.

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.<ref>{{cite web |last=Bauer |first=Andrej |date=29 March 2010 |title=Proof of negation and proof by contradiction |url=http://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/ |access-date=26 October 2021 |website=Mathematics and Computation}}</ref> In classical logic, where <math>P</math> and <math>\neg\neg P</math> may be freely interchanged, the distinction is largely obscured. Thus in mathematical practice, both principles are referred to as "proof by contradiction".

== Proof by contradiction in intuitionistic logic == In intuitionistic 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.<ref>{{Citation |last=Moschovakis |first=Joan |title=Intuitionistic Logic |date=2024 |work=The Stanford Encyclopedia of Philosophy |editor-last=Zalta |editor-first=Edward N. |url=https://plato.stanford.edu/archives/sum2024/entries/logic-intuitionistic/ |access-date=2025-04-05 |edition=Summer 2024 |publisher=Metaphysics Research Lab, Stanford University |editor2-last=Nodelman |editor2-first=Uri}}</ref>

Brouwer–Heyting–Kolmogorov interpretation of proof by contradiction gives the following intuitionistic validity condition: {{clarify span|if there is no method for establishing that a proposition is false, then there is a method for establishing that the proposition is true.|reason=This condition is particularly dubious, as discussed in the next paragraph. Moreover, I couldn't find the condition in the 'Brouwer–Heyting–Kolmogorov interpretation' article.|date=May 2024}}

If we take "method" to mean algorithm, then the condition is not acceptable, as it would allow us to solve the Halting problem. To see how, consider the statement ''H(M)'' stating "Turing machine ''M'' halts or does not halt". Its negation ''¬H(M)'' states that "''M'' neither halts nor does not halt", which is false by the law of noncontradiction (which is intuitionistically valid). If proof by contradiction were intuitionistically valid, we would obtain an algorithm for deciding whether an arbitrary Turing machine ''M'' halts, thereby violating the (intuitionistically valid) proof of non-solvability of the Halting problem.

A proposition ''P'' which satisfies <math>\lnot\lnot P \Rightarrow P</math> 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 <math>P \lor \lnot P</math>. 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 "<math>n</math> is prime" or "<math>a</math> divides <math>b</math>".

== Examples of proofs by contradiction ==

=== Euclid's Elements === An early occurrence of proof by contradiction can be found in Euclid's Elements, Book 1, Proposition 6:<ref>{{cite web |title=Euclid's Elements, Book 6, Proposition 1 |url=https://mathcs.clarku.edu/~djoyce/elements/bookI/propI6.html |access-date=2 October 2022}}</ref>

: If in a triangle two angles equal one another, then the sides opposite the equal angles also equal one another.

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:<ref>{{cite web |title=Euclid's Elements, Book 7, Proposition 33 |url=http://aleph0.clarku.edu/~djoyce/java/elements/bookVII/propVII33.html |access-date=2 October 2022}}</ref>

: If the side of the hexagon and that of the decagon inscribed in the same circle are added together, then the whole straight line has been cut in extreme and mean ratio, and its greater segment is the side of the hexagon.

=== Hilbert's Nullstellensatz === An influential proof by contradiction was given by David Hilbert. His Nullstellensatz states:

: If <math>f_1,\ldots,f_k</math> are polynomials in ''{{mvar|n}}'' indeterminates with complex coefficients, which have no common complex zeros, then there are polynomials <math>g_1,\ldots, g_k</math> such that <math>f_1g_1+\ldots +f_kg_k=1.</math>

Hilbert proved the statement by assuming that there are no such polynomials <math>g_1, \ldots, g_k</math> and derived a contradiction.<ref>{{Cite journal |last=Hilbert |first=David |author-link=David Hilbert |date=1893 |title=Ueber die vollen Invariantensysteme |url=https://resolver.sub.uni-goettingen.de/purl?PPN235181684_0042 |journal=Mathematische Annalen |volume=42 |issue=3 |pages=313–373 |doi=10.1007/BF01444162 |url-access=subscription}}</ref>

=== Infinitude of primes === Euclid's theorem states that there are infinitely many primes. In Euclid's Elements the theorem is stated in Book IX, Proposition 20:<ref name="mathcs_clarku_edu">{{cite web |title=Euclid's Elements, Book 9, Proposition 20 |url=https://mathcs.clarku.edu/~djoyce/elements/bookIX/propIX20.html |access-date=2 October 2022}}</ref>

: Prime numbers are more than any assigned multitude of prime numbers.

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 <math>n</math> there is a prime bigger than it, then we employ proof by contradiction, as follows.

Given any number <math>n</math>, we seek to prove that there is a prime larger than <math>n</math>. Suppose to the contrary that no such ''p'' exists (an application of proof by contradiction). Then all primes are smaller than or equal to <math>n</math>, and we may form the list <math>p_1, \ldots, p_k</math> of them all. Let <math>P = p_1 \cdot \ldots \cdot p_k</math> be the product of all primes and <math>Q = P + 1</math>. Because <math>Q</math> is larger than all prime numbers it is not prime, hence it must be divisible by one of them, say <math>p_i</math>. Now both <math>P</math> and <math>Q</math> are divisible by <math>p_i</math>, hence so is their difference <math>Q - P = 1</math>, 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 <math>n</math>.

== Examples of refutations by contradiction == The following examples are commonly referred to as proofs by contradiction, but formally employ refutation by contradiction (and therefore are intuitionistically valid).<ref>{{cite journal |last=Bauer |first=Andrej |date=2017 |title=Five stages of accepting constructive mathematics |journal=Bulletin of the American Mathematical Society |volume=54 |issue=3 |pages=481–498 |doi=10.1090/bull/1556 |doi-access=free}}</ref>

=== Infinitude of primes === Let us take a second look at Euclid's theorem – Book IX, Proposition 20:<ref name="mathcs_clarku_edu" />

: Prime numbers are more than any assigned multitude of prime numbers.

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 case Euclid's proof applies refutation by contradiction at one step, as follows.

Given any finite list of prime numbers <math>p_1, \ldots, p_n</math>, it will be shown that at least one additional prime number not in this list exists. Let <math>P = p_1 \cdot p_2 \cdots p_n</math> be the product of all the listed primes and <math>p</math> a prime factor of <math>P + 1</math>, possibly <math>P + 1</math> itself. We claim that <math>p</math> is not in the given list of primes. Suppose to the contrary that it were (an application of refutation by contradiction). Then <math>p</math> would divide both <math>P</math> and <math>P + 1</math>, therefore also their difference, which is <math>1</math>. This gives a contradiction, since no prime number divides 1.

=== Irrationality of the square root of 2 === The classic proof that the square root of 2 is irrational is a refutation by contradiction.<ref>{{cite web |last=Alfeld |first=Peter |date=16 August 1996 |title=Why is the square root of 2 irrational? |url=http://www.math.utah.edu/~pa/math/q1.html |access-date=6 February 2013 |work=Understanding Mathematics, a study guide |publisher=Department of Mathematics, University of Utah}}</ref> Indeed, we set out to prove the negation ''¬ ∃ a, b ∈ <math>\mathbb{N}</math> . a/b = {{sqrt|2}}'' by assuming that there exist natural numbers ''a'' and ''b'' whose ratio is the square root of two, and derive a contradiction.

Assume that √2 is rational,<ref name=":02">{{Cite web |last=Erik|date=January 16, 2026|title=irrational number|url=https://www.britannica.com/science/irrational-number|access-date=April 21, 2025|website=Encyclopedia Britannica|first=Gregersen}}</ref> so it can be written as a fraction a/b in lowest terms, where a and b are integers with no common factors. This assumption allows us to apply a proof by contradiction.<ref>{{Cite book |last=Velleman|first=Daniel J.|title=How to prove it: a structured approach|date=2019|publisher=Cambridge University Press|isbn=978-1-108-42418-9|edition=3rd|location=Cambridge ; New York, NY}}</ref> Squaring both sides gives 2 = a²/b², which implies that a² = 2b².<ref>{{Cite book |last=Rosen|first=Kenneth H.|title=Discrete mathematics and its applications|date=2019|publisher=McGraw-Hill education|isbn=978-1-259-67651-2|edition=8th|location=New York (N.Y.)}}</ref> Therefore, a² is even, and it follows that a must also be even. Let a = 2k for some integer k. Substituting back into the equation gives (2k)² = 2b², which simplifies to 4k² = 2b², or b² = 2k². Hence, b² is even, and therefore b must also be even. This shows that both a and b are even, which contradicts the assumption that a/b was in lowest terms. Therefore, the original assumption is false, and √2 is irrational.<ref name=":02" />

=== Proof by infinite descent === Proof by infinite descent is a method of proof whereby a smallest object with desired property is shown not to exist as follows:

* Assume that there is a smallest object with the desired property. * Demonstrate that an even smaller object with the desired property exists, thereby deriving a contradiction.

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 number ''q'' and derive a contradiction by observing that {{sfrac|''q''|2}} is even smaller than ''q'' and still positive.

=== Russell's paradox === 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.

== Notation ==<!--This section is linked from Hand of Eris.-->

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.<ref>{{cite web |title=Math Forum Discussions |url=http://mathforum.org/kb/message.jspa?messageID=1175481}}</ref> A graphical symbol sometimes used for contradictions is a downwards zigzag arrow "lightning" symbol (U+21AF: ↯), for example in Davey and Priestley.<ref>B. Davey and H.A. Priestley, ''Introduction to Lattices and Order'', Cambridge University Press, 2002; see "Notation Index", p. 286.</ref> Other symbols sometimes used include a pair of opposing arrows (as <math>\rightarrow\!\leftarrow</math>{{citation needed|reason=Give a reference for each notational variant.|date=October 2021}} or <math>\Rightarrow\!\Leftarrow</math>),{{citation needed|date=October 2021}} struck-out arrows (<math>\nleftrightarrow</math>),{{citation needed|date=October 2021}} a stylized form of hash (such as U+2A33: ⨳),{{citation needed|date=October 2021}} or the "reference mark" (U+203B: ※),{{citation needed|date=October 2021}} or <math>\times\!\!\!\!\times</math>.<ref>Gary Hardegree, ''Introduction to Modal Logic'', Chapter 2, pg. II–2. https://web.archive.org/web/20110607061046/http://people.umass.edu/gmhwww/511/pdf/c02.pdf</ref><ref>The Comprehensive LaTeX Symbol List, pg. 20. http://www.ctan.org/tex-archive/info/symbols/comprehensive/symbols-a4.pdf</ref>

== Automated theorem proving == 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.<ref>{{Citation |title=Linear Resolution |date=1994 |work=From Logic to Logic Programming |pages=93–120 |url=http://dx.doi.org/10.7551/mitpress/3133.003.0007 |access-date=2023-12-21 |publisher=The MIT Press |doi=10.7551/mitpress/3133.003.0007 |isbn=978-0-262-28847-7 |url-access=subscription}}</ref>

==See also== {{cols}} * List of Latin phrases * List of fallacies * {{annotated link|Ad hominem}} * {{annotated link|Appeal to ridicule}} * {{annotated link|Appeal to motive}} * {{annotated link|Argument from fallacy}} * {{annotated link|Contraposition}} * {{annotated link|DARVO}} * {{annotated link|Fundamental attribution error}} * {{annotated link|Gaslighting}} * {{annotated link|Mathematical proof}} * {{annotated link|Red-baiting}} * {{annotated link|Reductio ad Hitlerum}} * {{annotated link|Slippery slope}}

{{colend}}

==References== {{Reflist}}

== Sources == * {{cite SEP|last=Hyde|first=Dominic|title=Sorites Paradox|date=2018|url=https://plato.stanford.edu/archives/sum2018/entries/sorites-paradox/|work=The Stanford Encyclopedia of Philosophy|editor-last=Zalta|editor-first=Edward N.|edition=Summer 2018|last2=Raffman|first2=Diana|url-id=sorites-paradox}} * {{Citation | last =Garfield | first =Jay L. | year =1995 | title =The Fundamental Wisdom of the Middle Way | place =Oxford | publisher =Oxford University Press}} * Pasti, Mary. Reductio Ad Absurdum: An Exercise in the Study of Population Change. United States, Cornell University, Jan., 1977. * Daigle, Robert W.. The Reductio Ad Absurdum Argument Prior to Aristotle. N.p., San Jose State University, 1991.

==External links== *{{wiktionary-inline|reductio ad absurdum|per impossibile}} *{{cite IEP |url-id=reductio/ |title=Reductio ad absurdum}}

{{Philosophical skepticism}}

{{DEFAULTSORT:Reductio Ad Absurdum}} Category:Latin logical phrases Category:Latin philosophical phrases Category:Theorems in propositional logic Category:Madhyamaka Category:Arguments Category:Pyrrhonism Category:Greek philosophy Category:Buddhist philosophical concepts